数据结构重读 – 循环队列

队列也可以用顺序存储表示。定义还是一样的:从队尾rear推入元素。从头部head拿出元素,是FIFO。

与链式存储一致,我们仍然需要附设两个指针front和rear分别表示队列头元素和队列元素的位置。初始时front=rear=0是队列空的条件。

每当插入新的队列元素时,尾指针将增1.删除队列头元素时,头指针增加1。即非空队列中:头元素总是指向队首元素,而尾指针总是指向队尾元素的下一个位置。

除了基本的顺序存储外,我们还可以使用循环数组来构造一个循环队列

在循环队列中,上述head+1,rear+1变为(head+1)%MAX, (rear+1)%MAX。

队列空的条件还是head==rear,但是满的条件变为(rear+1)%MAX==head。为了这个Full的判断,循环队列将浪费一个空间,即可使用的空间只有MAX-1个。

代码如下:

#include <stdio.h>

#define MAX 1000

struct Queue
{
	int data[MAX];
	int head;
	int rear;
};

void queue_init(struct Queue* q)
{
	q->head = q->rear = 0;	
}

int queue_is_empty(struct Queue* q)
{
	if(q->head==q->rear)	
	{
		return 1;
	}else
	{
		return 0;
	}
}

int queue_is_full(struct Queue* q)
{
	if((q->rear+1)%MAX==q->head)
	{
		return 1;
	}else
	{
		return 0;
	}
}

int queue_enqueue(struct Queue* q, int data)
{
	if(queue_is_full(q))
	{
		return -1;
	}
	q->data[q->rear] = data;
	q->rear = (q->rear+1) % MAX;
}

int queue_dequeue(struct Queue* q, int* data)
{
	if(queue_is_empty(q))
	{
		return -1;
	}
	*data = q->data[q->head];
	q->head = (q->head+1) % MAX;
}

int queue_print(struct Queue* q)
{
	int i;
	for(i=q->head;i!=q->rear;i=(i+1)%MAX)
	{
		printf("%d ", q->data[i]);
	}
	printf("\n");
}

int main()
{
	struct Queue q;
	int i;
	int data;
	queue_init(&q);
	// Would left 999 not enqueue
	for(i=0;i<1000;i++)
	{
		queue_enqueue(&q, i);
	}
	for(i=0;i<10;i++)
	{
		queue_dequeue(&q, &data);
	}
	for(i=0;i<10;i++)
	{
		queue_enqueue(&q, i);
	}
	printf("IsFull:%d\n", queue_is_full(&q));
	queue_print(&q);
	return 0;
}

Leave a Reply

Your email address will not be published.