循环队列

为了解决顺序队列中的“假溢出”现象，充分利用数组的存储空间，可 将顺序队列的头尾相连，构成一个循环队列 。循环队列一般都是 用数组来实现 的。 在循环队列中，front和rear都是可以移动的。 当队列为空或满时，front = rear都成立，所以不能用这个条件来判断队列是空的还是满的。 为了解决这个问题，在循环队列中有一个约定： 少用一个元素空间，当队尾标识rear在队头标识front的上一个位置时，队列为满。此时，判断队列空和满的条件为： 队空：front == rear 对满：（rear+1）%MAXNUM == front  (MAXNUM为队列容量的大小) 循环队列中front和rear的移动不再是简单的加1，因为原本是循环的，所以可能原本指在末尾，前进一个单位就是又一个循环的开始，故每次移动都要对MAXNUM取模： front = (front+1)%MAXNUM     rear = (rear+1)%MAXNUM 求队列长度也不是简单的front和rear相减，因为rear的值有可能比front小。 循环队列求队列长度的方法：（rear+MAXNUM-front）%MAXNUM

循环队列的C语言实现：（codeblocks完美运行）

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXNUM 50 //队列结构体 typedef struct queue { int front; int rear; int data[MAXNUM]; }seqqueue; //创建队列 seqqueue *create() { seqqueue* sq = (seqqueue *)malloc(sizeof(seqqueue)); sq->front = -1; sq->rear = -1; memset(sq->data,0,MAXNUM); return sq; } //获取队列长度 int getsize(seqqueue *sq) { return (sq->rear+MAXNUM-sq->front)%MAXNUM; } //判断队列是否为空 int IsEmpty(seqqueue *sq) { if(sq->rear == sq->front) return 1; return 0; } //判断队列是否满 int IsFull(seqqueue *sq) { if((sq->rear+1)%MAXNUM == sq->front) return 1; return 0; } //入队 int insert(seqqueue *sq,int val) { if(IsFull(sq)) { printf("队列已满!\n"); return 0; } if(IsEmpty(sq))//如果队列为空 { sq->front = sq->rear = 0; sq->data[sq->rear] = val; sq->rear++; } else { sq->data[sq->rear] = val; sq->rear = (sq->rear+1)%MAXNUM; } } //出队 int del(seqqueue *sq) { if(IsEmpty(sq)) { printf("队列已空！\n"); return 0; } int temp = sq->data[sq->front]; sq->front = (sq->front+1)%MAXNUM ; return temp; } //获取队头元素 int getfront(seqqueue *sq) { if(IsEmpty(sq)) { printf("队列已空！\n"); return 0; } return sq->data[sq->front]; } //清空队列 void clear(seqqueue *sq) { sq->front = sq->rear = -1; printf("队列已清空！\n"); } //销毁队列 void destroy(seqqueue *sq) { free(sq); printf("队列已销毁！\n"); } int main() { srand((unsigned)time(0)); seqqueue *sq = create(); //创建队列 int i; printf("入队30个元素！(从队尾插入)\n"); for(i=0;i<30;i++) { insert(sq,rand()00); } printf("队头为：%d\n",getfront(sq)); printf("打印队列（同时是出队操作）\n"); for(i=0;i<30;i++) { if(i%6 == 0) printf("\n"); printf("= ",del(sq)); } printf("\n此时队列长度：%d\n",getsize(sq)); clear(sq); destroy(sq); return 0; } 运行界面：