链队列和循环队列

队列是一种先进先出（FIFO）的线性表，它只允许在表的一端进行插入，而在另一端删除元素。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。队列的结构图如下所示：

明白了队列之后，链队列就非常简单了，用链表表示的队列就简称为链队列。一个链队列显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)才能惟一确定。

图片转载

//链队列结构定义
//链队列节点
typedef struct LinkNode
{
	int data;
	struct LinkNode* next;
}*LinkNodePtr;
 
//链队列 
typedef struct LinkQueue
{
	LinkNodePtr front;
	LinkNodePtr rear;
 } *LinkQueuePtr;

 初始化和输出

//初始化
LinkQueuePtr initQueue() 
{
	LinkQueuePtr resultPtr = (LinkQueuePtr)malloc(sizeof(struct LinkQueue));
	LinkNodePtr headPtr = (LinkNodePtr)malloc(sizeof(struct LinkNode));
	headPtr->data = -1;
	headPtr->next = NULL;
	resultPtr->front = headPtr;
	resultPtr->rear = headPtr;
	return resultPtr;
 }//of initQuene

//打印
void outputQueue(LinkQueuePtr paraQueuePtr)
{
	LinkNodePtr tempPtr = paraQueuePtr->front->next;
	while(tempPtr != NULL)
	{
		printf("%d ",tempPtr->data);
		tempPtr = tempPtr->next;
	}
	printf("n");
 }//of outputQuene

 入队和出队

//入队
void enterQueue(LinkQueuePtr paraQueuePtr,int paraElem)
{
	LinkNodePtr tempPtr = (LinkNodePtr)malloc(sizeof(struct LinkNode));
	tempPtr->data = paraElem;
	tempPtr->next = NULL;
	
	paraQueuePtr->rear->next = tempPtr;
	paraQueuePtr->rear = tempPtr;	
 } //of enterQuene

//出队
int deleteQueue(LinkQueuePtr paraQueuePtr)
{
	int result;
	LinkNodePtr tempPtr;
	//判断队列是否为空
	if(paraQueuePtr->front == paraQueuePtr->rear)
	{
		printf("队列为空，无法删除n");
		return -1;
	 } 
	tempPtr = paraQueuePtr->front->next;
	result = tempPtr->data;
	paraQueuePtr->front->next = tempPtr->next;
	if(paraQueuePtr->rear == tempPtr)
	{
		paraQueuePtr->rear = paraQueuePtr->front;
	}
	free(tempPtr);
	return result;
 }of deleteQuene

循环队列使用的是数组，但是这个数组比较特别，为循环数组。为什么要使用循环数组呢？

可以想象一下，假如我们使用通常的数组。

那么在使用过程中，我们是从后面加入数据，从前面移除数据。那么随着出队和入队的进行，数组会整体向右平移，因为数组前面的元素因为出队变成了空白，变得不可使用。造成空间的浪费。

如果每出队一次，都将数组向左平移一次，又会很麻烦，造成时间上的浪费。综上，我们使用循环队列，就是将队首和队尾黏在一起。类似于一个⚪；

//定义
//循环队列
typedef struct CircleQueue
{
	int data[TOTAL_SPACE];
	int head;//队首 
	int tail;//队尾 
 } *CircleQueuePtr;

//初始化
//初始化
CircleQueuePtr initCircleQueue()
{
	CircleQueuePtr resultPtr = (CircleQueuePtr)malloc(sizeof(struct CircleQueue));
	resultPtr->head = 0;
	resultPtr->tail = 0;
	return resultPtr;
}//of initCircleQuene

//打印
void outputQueue(CircleQueuePtr paraPtr)
{
	int i;
	if(paraPtr->head == paraPtr->tail)
	{
		printf("队列为空.n");
		return;
	}
	printf("队列:");
	for(i = paraPtr->head;i < paraPtr->tail;i++)
	{
		printf("%d ",paraPtr->data[i % TOTAL_SPACE]);
	}
	printf("n");
 } //of outputQuene

//入队
void enterQueue(CircleQueuePtr paraPtr,int paraData)
{
	if((paraPtr->tail+1) % TOTAL_SPACE == paraPtr->head)
	{
		printf("队列已满.n");
		return;
	}
	paraPtr->data[paraPtr->tail%TOTAL_SPACE] = paraData;
	paraPtr->tail++;
 } //of enterQuene

//出队 
int deleteQueue(CircleQueuePtr paraPtr)
{
	int result;
	if(paraPtr->head == paraPtr->tail)
	{
		printf("队列为空，不能删除.n");
		return -1;
	}
	result = paraPtr->data[paraPtr->head % TOTAL_SPACE];
	paraPtr->head++;
	return result;
 } //of deleteQuene