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]; /*返回队头元素的值*/ }
标签： 循环队列
