循环队列的实现

队列是一种先入先出的数据结构(first in first out)，普通队列的实现通常采用单链表。入队相当于对链表进行尾部插入元素，出队相当于删除链表头部的元素。

普通队列的基本结构和操作：

typedef int QueueDatatype;
//组成队列的结点
typedef struct QueueNode
{
	struct QueueNode* next;
	QueueDatatype data;
}QueueNode;
//队列只需要一个头指针和尾指针维护即可
typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;
//入队：尾部插入元素
void QueuePush(Queue* pq, QueueDatatype x)
{
	QueueNode* tmp = (QueueNode*)malloc(sizeof(QueueNode));
	assert(tmp);
	tmp->data = x;
	tmp->next = NULL;
	if (pq->tail == NULL)//说明原队列没有元素
	{
		pq->head = pq->tail = tmp;
	}
	else
	{
		pq->tail->next = tmp;
		pq->tail = tmp;
	}
}
//出队，队头删除元素
void QueuePop(Queue* pq)
{
	assert(pq);
	if (pq->head == NULL)//没有元素可以删除
		return;
	else//有元素可以删除
	{
		//只有一个元素的话，删除之后要将tail置为NULL
		if (pq->head == pq->tail)
		{
			free(pq->head);
			pq->head = pq->tail = NULL;
		}
		else
		{
			QueueNode* next = pq->head->next;
			free(pq->head);
			pq->head = next;
			//只有一个元素的话，不能采用else的方法，否则tail变为野指针
		}

	}
}

普通队列的基本操作是尾部插入与头部删除，结构比较简单。

循环队列的基本操作也是尾部插入与头部删除，但其结构相对于普通队列要稍微复杂一些。

循环队列可以通过链表或者数组实现，与普通队列不同的是，循环队列可以容纳的元素大小是确定的，不容易实现扩容的操作。

1.通过数组实现循环队列

假设该循环队列可以存放4个元素

初始时，设置一个数组，那么该数组的大小应该为5，要比循环队列中可以容纳的元素个数大1.这样设计可以判断循环队列是否已满。

#define CAPACITY 4
typedef struct CircleQueue
{
	int head;
	int tail;
	int* data;
}CircleQueue;
void CircleQueueInit(CircleQueue* pc)
{
	pc->head = pc->tail = 0;
	pc->data = (int*)malloc((CAPACITY+1) * sizeof(int));//队列存储n个元素，需要n+1个空间
}

 当整个队列为空时，tail和head都为0，每当有元素入队，tail++,每当有元素出队，head++.设计队列时，n=4,表示队列容量是4，也对应数组的最大下标。

当队列满时，可能有下面的情况：

即tail-head=n。这种情况下如果把5下标看做是0下标的对应，也就相当于建立了循环

也有可能是这种情况

即经过多次入队和出队操作，tail

判断循环队列是否已满：

bool CircleQueueIsFull(CircleQueue* pc)
{
	//n=CAPACITY
	int next = pc->tail + 1;
	if (next == CAPACITY + 1)
		next = 0;
	return next == pc->head;
}

循环队列的入队和出队

void CircleQueuePush(CircleQueue* pc,int x)
{
	if (CircleQueueIsFull(pc))
		return;
	else
	{
		int next = pc->tail + 1;
		if (next == CAPACITY + 1)
			next = 0;
		pc->data[pc->tail] = x;
		pc->tail = next;
	}
}
void CircleQueuePop(CircleQueue* pc)
{
	if (pc->tail == pc->head)//队列为空
		return;
	else
	{
		int next = pc->head + 1;
		if (next == CAPACITY + 1)
			next = 0;
		pc->head = next;//出队不需要删除head位置的元素，因为队列中的元素是靠head和tail维护
	}
}

2.通过单链表实现循环队列

 提前设置好结点的个数，假设循环链表的容量还是4，n=4,那么单链表的结点个数为n+1=5,为了保证循环，还应该将单链表设置为循环结构，最后一个结点的next指向第一个结点。

入队操作：tail=tail->next,出队操作:head=head->next

判断队列是否满：

因为每一次入队都是tail=tail->next,判断队列是否满只需要判断tail->next==head 

判断队列是否为空只需判断head==tail

#define CAPACITY 4//n=CAPACITY
typedef struct QueueNode
{
	int data;
	QueueNode* next;
}QueueNode;
typedef struct CircleQueue
{
	QueueNode* head;
	QueueNode*tail
}CircleQueue;
void CircleQueueInit(CircleQueue* pc)
{
	QueueNode** ppNode = (QueueNode**)malloc((CAPACITY + 1) * sizeof(QueueNode*));
	assert(ppNode);
	for (int i = 0; i < CAPACITY + 1; i++)
	{
		ppNode[i] = (QueueNode*)malloc(sizeof(QueueNode));
	}
	for (int i = 0; i < CAPACITY; i++)
	{
		ppNode[i]->next = ppNode[i + 1];
	}
	ppNode[CAPACITY]->next = ppNode[0];
	pc->head = pc->tail = ppNode[0];
}
bool CircleQueueIsFull(CircleQueue* pc)
{
	return pc->tail->next == pc->head;
}
bool CircleQueueIsEmpty(CircleQueue* pc)
{
	return pc->tail == pc->head;
}
void CircleQueueIsPush(CircleQueue* pc, int x)
{
	if (CircleQueueIsFull(pc))
		return;
	else
	{
		pc->tail->data = x;
		pc->tail = pc->tail->next;
	}
}
void CircleQueueIsPop(CircleQueue* pc)
{
	if (CircleQueueIsEmpty(pc))
		return;
	else
	{
		pc->head = pc->head->next;
	}
}