1.循环队列的概念

为了克服顺序队列的“假上溢”现象，充分利用队列的存储空间，我们可以把队列想象成一个首尾相接的圆环，即将队列中的第一个元素接在最后一个元素的后面，我们称这样的队列为循环队列（Circular Queue），如图3-7所示。

循环队列入队、出队操作示意图

图3-7（a）为队列初始状态,front=0,rear=0。图3-7（b）中，A、B、C、D、E五个元素依次入队，front=0,rear=5。如果元素F继续入队，则队列空间就会被占满，变成如图3-7（c）所示的状态，此时，front=rear。若A、B、C、D、E、F相继出队，则队空，如图3-7（d）所示，此时，front=rear。

因此，在循环队列中，仅根据front=rear无法有效地判断队空还是队满，解决的方法是少用一个元素空间，约定当尾指针加1等于头指针时，认为是队满，可用求模运算来实现，即当(rear+1)%MaxSize=front时，称为队满，如图3-7（b），此时，循环队列中能装入的元素个数为MaxSize-1。当front=rear时，称为队空。

循环队列的基本操作

循环队列判队空算法

	int QueueEmpty(struct SeqQueue *sq)	{	if(sq->rear==sq->front) return 1; else return 0;	}

（2）入队

算法要点：

1.首先判断队列是否已满，若队满，则进行“溢出”错误处理；

2.当队列不满时，将元素x赋给队尾指针指向的单元；

3.将队尾指针加1。

循环队列入队算法

	void InQueue(struct SeqQueue *sq, int x)	{	if((sq->rear+1)%MaxSize==sq->front) { /*判循环队列是否已满*/	printf("循环队列已满\n");	exit(1); /*入队失败，退出函数运行*/ 	}	sq->data[sq->rear]=x; /*数据送给队尾指针所指单元*/ 	sq->rear=(sq->rear+1)%MaxSize; /*利用模运算将队尾指针加1*/ 	}

（3）出队

算法要点：

1.首先判断队列是否已空，若队空，则进行“下溢出”错误处理；

2.否则，暂存队头元素；

3.将队头指针加1；

4.返回原队头元素的值。

循环队列出队算法

	void OutQueue(struct SeqQueue *sq, int x)	{	if (sq->rear==sq->front) { /*判断循环队列是否为空*/	printf("循环队列已空，不能进行出队操作\n");	exit(1); /*出队失败，退出函数运行*/	}	else {	x=sq->data[sq->front]; /*暂存队头元素以便返回*/	sq->front=(sq->front+1)%MaxSize; /*将队头指针加1*/	return x; /*返回原队头元素的值*/	}	}

（4）取队头元素

算法要点：

1.首先判断队列是否已空，若队空，则进行“下溢”错误处理；

2.否则，返回原队头元素的值。

循环队列取队头元素算法

	void GetQueue(struct SeqQueue *sq, int x)	{	if (sq->rear==sq->front) { /*判断队是否为空*/	printf("队列已空，不能进行出队操作\n");	exit(1); /*出队失败，退出函数运行*/	}	return sq->data[sq->front]; /*返回队头元素的值*/ 	}