主要内容 #
- 循环队列
- 入队和出队
- 参考代码
1. 循环队列 #
前面讲到队列的时候提到,顺序队列的实现方案并不完美,存在一下两个弊端:
- 随着元素的入队和出队,队列整体向顺序表的尾部移动,队列左侧闲暇空间无法再次利用;
- 当队列移动到顺序表的尾部时,新元素无法入队。
采用循环队列可以彻底消除以上两个弊端。所谓循环队列,本质上使用顺序表模拟实现队列,只不过,在具体实现的过程中,会将顺序表想象成首尾相连的换装表来使用。
例如,下图左侧为一个空的“环状”顺序表,用它来模拟实现队列,队头(top)和队尾(rear)都位于a[0]处。下图右侧是一个存有{1,2,3,4}的循环队列,它的队头位于a[2]处,队尾位于a[6]处。
再次强调我们只是将顺序表想象成环状表来用,实际用C/C++语言程序实现循环队列时,建立的仍是普通的顺序表,后续将会讲解将循序表当作环状表使用的方法。
2. 入队和出队 #
循环队列的入队操作
循环队列的入队操作过程和顺序队列类似,完成以下两种操作即可:
- 将新元素添加到rear指向的空闲空间;
- rear指向下一位,指向下一个空闲空间,为下一次入队新元素做准备。
例如,在上图的基础上,向队列添加一个新元素5,实现过程如下图所示:
可以看到,当顺序表还有空间时,由于我们将它想象成“首尾相连”的状态,a[6]和a[0]挨着,rear变量会向后移一位会指向a[0]的位置。这意味着,队列左侧的空闲空间可以再次利用起来。
需要注意的是,循环队列判断“已满”的方式比较特殊。当我们根据上图尝试将6、7分别入队时,最终的存储状态会变成下图所示:
在第一个图中我们可以用top==rear作为空队列的判断标志,但第三张图中,队列已满的状态也是top==rear,明显它们是冲突的。解决冲突的常用方法是:仍用top==rear作为空队列的判断标志,将队列已满的判断方法改为(rear+1)%MAX_LEN==top,其中MAX_LEN为顺序表(数组)的长度。
例如,在第2张图片的基础上,尝试将元素6入队,此时rear的值为0,(rear+1)%MAX_LEN的值为1,而top的值为2,所以等式不成立,意味着队列不满,元素6就成功存储到了a[0]处。
在第4张图片的基础上,尝试将元素7入队,此时rear的值为1,(rear+1)%MAX_LEN的值为2,而top的值为2,所以等式成立,意味着循环队列已满,元素7就无法入队。
如上图所示,顺序表中明明还有一块空间没有利用呢?是的,这就是循环队列判断“已满”的方法,浪费一块存储空间,避免和“队列为空”的状态发生冲突。
循环队列实现入队的C++语言的代码如下:
int enQueue(int* a, int top, int rear, int data){ //添加判断语句,如果rear超过max,则直接从a[0]开始存储,如果rear+1和top重合,则表示顺序表已满 if((rear+1)%MAX_LEN == top){ cout <<"空间已满" << endl; return rear; } //将新元素入队 a[rear%MAX_LEN] = data; cout << "新元素" << data <<"成功入队" << endl; rear = (rear + 1) % MAX_LEN; return rear; }
程序当中没有将data直接存储到a[rear]中,而是将其存储到a[rear%MAX_LEN]中,这样就可以将顺序表当作环表来使用。
循环队列的出队操作
循环队列的出队操作过程和顺序队列类似,完成以下两种操作即可:
- 将top记录的队头元素出队;
- 将top向后移动一位,记录新队头元素的位置。
因此循环队列实现出队操作的C++语言代码为:
int deQueue(int* a, int top, int rear){ //如果top==rear,表示队列为空 if(rear == top){ cout <<"队列为空" << endl; return rear; } cout << "元素" << a[top]<< "成功出队" << endl; //top向后移动一个位置,记录新的队头 top = (top + 1) % MAX_LEN; return top; }
3. 参考代码 #
为了加深各位同学对循环队列理解,下面给出C++实现循环队列的完成代码:
#include<iostream> using namespace std; #define MAX_LEN 5 //表示申请空间的大小 int enQueue(int* a, int top, int rear, int data){ //添加判断语句,如果rear超过max,则直接从a[0]开始存储,如果rear+1和top重合,则表示顺序表已满 if((rear+1)%MAX_LEN == top){ cout <<"空间已满" << endl; return rear; } //将新元素入队 a[rear%MAX_LEN] = data; cout << "新元素" << data <<"成功入队" << endl; rear = (rear + 1) % MAX_LEN; return rear; } int deQueue(int* a, int top, int rear){ //如果top==rear,表示队列为空 if(rear == top){ cout <<"队列为空" << endl; return rear; } cout << "元素" << a[top]<< "成功出队" << endl; //top向后移动一个位置,记录新的队头 top = (top + 1) % MAX_LEN; return top; } int main(){ int a[MAX_LEN] = {0}; int top = 0, rear = 0; rear = enQueue(a, top, rear, 1); rear = enQueue(a, top, rear, 2); rear = enQueue(a, top, rear, 3); rear = enQueue(a, top, rear, 4); //元素5入队会失败 rear = enQueue(a, top, rear, 5); top = deQueue(a, top, rear); //元素5再入队会成功 rear = enQueue(a, top, rear, 5); top = deQueue(a, top, rear); top = deQueue(a, top, rear); top = deQueue(a, top, rear); top = deQueue(a, top, rear); //队列为空时,出队操作失败 top = deQueue(a, top, rear); return 0; }