数据结构第7讲循环队列

痛定思痛。 2022-05-27 01:05 255阅读 0赞

**数据结构 第7讲 循环队列**

过了一段时间，小张再也受不了这种"起早贪黑"的有车生活。为了解决胡同停车问题，小张跑了无数次居委会，终于将挡在胡同口的建筑清除，这样住在胡同尽头的小张，就可以早早回家停在家门口，每天第一个开车上班去了。

![20180409095204232][]

现在胡同打通了，但仍然很窄，只能通过一辆车，但是可以从一端进，另一端出，画图：

![20180409095212430][]

小汽车是线性排列，而且只能从一端进，另一端出，这就是"队列"，队列也是一种线性表，只不过它是操作受限的线性表，只能在两端操作，先进先出（First In First Out，FIFO）。

进的一端称为队尾（rear），出的一端称为队头（front）。队列可以用顺序存储，也可以用链式存储。

1. 顺序队列

队列的顺序存储形式，可以用一个一维数组存储数据元素，用两个整型变量记录队头和队尾元素的下标。

顺序存储方式：

![2018040909522111][]

**顺序队列的结构体定义：**

![20180409095227671][]

**2. 完美图解**

接下来看看顺序队列的入队和出队情况：

假设现在顺序队列Q分配了6个空间，然后进行入队出队操作，过程如图所示：

(1) 开始时为空队，Q.front=Q.rear，如图所示：

![20180409095234392][]

(2) 元素*a*1进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：

![20180409095240242][]

(3) 元素*a*2进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：

![20180409095246640][]

(4) 元素*a*3，*a*4，*a*5分别按顺序进队，尾指针Q.rear依次后移，如图所示：

![20180409095253497][]

(5) 元素*a*1出队，头指针Q.front（整型下标）后移一位，如图所示：

![20180409095259805][]

(6) 元素*a*2出队，头指针Q.front（整型下标）后移一位，如图所示：

![20180409095305666][]

(7) 元素*a*6进队，放入尾指针rear（整型下标）的位置，rear后移一位，如图所示：

![20180409095314201][]

(8) 元素*a*7进队，此时尾指针Q.rear已经超过了数组的下标，无法再存储进队，但是我们发现前面明明有2个空间，却出现了队满的情况，这种情况称为"假溢出"。

那么如何解决该问题呢？

**能否利用前面的空间继续存储入队呢？**

试试看…～

上面第（7）步元素*a*6进队之后，尾指针Q.rear要后移一个位置，此时已经超过了数组的下标，即Q.rear+1=Maxsize（最大空间数6），那么如果前面有空闲，Q.rear可以转向前面0的位置，如图所示：

![20180409095320683][]

然后元素*a*7进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：

![20180409095327724][]

元素*a*8进队，放入尾指针Q.rear（整型下标）的位置，Q.rear后移一位，如图所示：

![20180409095334875][]

这时候虽然队列空间存满了，但是出现了一个大问题，队满时Q.front=Q.rear，这和队空的条件一模一样，无法区分队空还是队满，如何解决呢？有两种办法：一是设置一个标志，标记队空和队满；另一种办法是浪费一个空间，当尾指针Q.rear的下一个位置Q.front是时，就认为是队满。如图所示：

![20180409095340994][]

3. 循环队列

上述到达尾部又向前存储的队列称为循环队列，为了避免"假溢出"，我们通常采用**循环队列。**

循环队列无论入队还是出队，队尾、队头加1后都要取模运算，例如入队后队尾后移一位：Q.rear =(Q.rear+1)%Maxsize。

**为什么要%Maxsize呢？**

主要是为了处理临界状态，即Q.rear向后移动一个位置Q.rear+1后，很有可能超出了数组的下标，这时它的下一个位置其实是0，如果将一维数组画成环形图，如图所示：

![20180409095352153][]

队空 队满

上图中最大空间Maxsize，当Q.rear=Maxsize-1时，(Q.rear+1)%Maxsize=0，而且Q.front=0，正好满足队满的条件：(Q.rear+1) %Maxsize= Q.front，此时为队满。

因此无论是front还是rear向后移动一个位置时，都要加1与最大空间Maxsize取模运算，处理临界问题。

**总结：**

**队空**：Q.front=Q.rear; // Q.rear和Q.front指向同一个位置

**队满**： (Q.rear+1) %Maxsize=Q.front; // Q.rear向后移一位正好是Q.front

**入队**：

Q.base\[Q.rear\]=x; //将元素放入Q.rear所指空间，

Q.rear =( Q.rear+1) %Maxsize; // Q.rear向后移一位

**出队**：

e= Q.base\[Q.front\]; //用变量记录Q.front所指元素，

Q.front=(Q.front+1) %Maxsize // Q. front向后移一位

**循环队列中到底存了多少个元素呢？**

因为队列是循环的，所以存在两种情况：

（1）Q.rear>= Q.front，如下图所示：

![20180409095400393][]

这种情况队列中元素个数为：Q.rear-Q.front=4-1=3。

（2）Q.rear< Q.front，如下图所示：

![20180409095406839][]

此时，Q.rear=4，Q.front=Maxsize-2，Q.rear-Q.front=6-Maxsize。但是我们可以看到循环队列中的元素实际上为6个，那怎么办呢？当两者之差为负数时，可以将差值+Maxsize计算元素个数，即：Q.rear-Q.front+Maxsize=6-Maxsize+Maxsize =6，元素个数为6。

那么在计算元素个数时，可以分两种情况判断：

*  Q.rear>= Q.front：元素个数为Q.rear-Q.front；
 *  Q.rear<Q.front：元素个数为Q.rear-Q.front+ Maxsize；

也可以采用取模的方法把两种情况统一为一个语句：

**队列中元素个数**：(Q.rear-Q.front+Maxsize)% Maxsize

当Q.rear-Q.front为负数时，加上Maxsize再取余正好是元素个数，如(-2+6)%6=4；当Q.rear-Q.front为正数时，加上Maxsize超过了最大空间数，取余后正好是元素个数，如(3+6)%6=3。

![2018040909563414][]

4. 队列的基本操作

队列的基本操作包括初始化、入队、出队、取队头元素、求队列长度。

(1)初始化

//循环队列的初始化
    bool InitQueue(SqQueue &Q)//注意使用引用参数，否则出了函数，其改变无效
    {
    	Q.base=new int[Maxsize];//分配空间
    	if(!Q.base) return false;
    	Q.front=Q.rear=0; //头指针和尾指针置为零，队列为空
    	return true;
    }

(2)入队

bool EnQueue(SqQueue &Q,int e)//将元素e放入Q的队尾
    
    {
    
        if((Q.rear+1)%Maxsize==Q.front) //尾指针后移一位等于头指针，表明队满
    
            return false;
    
        Q.base [Q.rear]=e; //新元素插入队尾
    
        Q.rear=(Q.rear+1)%Maxsize; //队尾指针后移一位
    
        return true;
    
    }

(3)出队

bool DeQueue(SqQueue &Q, int &e) //删除Q的队头元素，用e返回其值
    
    {
    
        if (Q.front==Q.rear)
    
            return false; //队空
    
        e=Q.base[Q.front]; //保存队头元素
    
        Q.front=(Q.front+1)%Maxsize; //队头指针后移一位
    
        return true;
    
    }

(4)取队头元素

int GetHead(SqQueue Q)//返回Q的队头元素，不修改队头指针
    
    {
    
        if (Q.front!=Q.rear) //队列非空
    
            return Q.base[Q.front];
    
    return -1;
    
    }

(5)循环队列的长度

int QueueLength(SqQueue Q)
    
    {
    
        return (Q.rear-Q.front+Maxsize)%Maxsize;
    
    }

本文来自《趣学数据结构》，让数据结构变得简单有趣。

[20180409095204232]: /images/20220527/5bca8b4583d348debb54190802bf7938.png
[20180409095212430]: /images/20220527/95b26501ef3c4d52bfedd64658d66c1f.png
[2018040909522111]: /images/20220527/86ef4a7e59ab48eeaa970bf90549054e.png
[20180409095227671]: /images/20220527/153a496353c64b38971120aa1d9ebd03.png
[20180409095234392]: /images/20220527/e8be1d945146438e90eeed8425da27cd.png
[20180409095240242]: /images/20220527/a850941d43bf491fa91f4f59b05e5f51.png
[20180409095246640]: /images/20220527/01e760ed72f74352bbd2baace968cea1.png
[20180409095253497]: /images/20220527/cbd0df70b57c4fb48732cab34c3e1ec6.png
[20180409095259805]: /images/20220527/42007ab0671a419ba0d0f5b1305defc7.png
[20180409095305666]: /images/20220527/0b49e29e672f430bbbcf1fb2e47f2dd1.png
[20180409095314201]: /images/20220527/87289d24efb146b8b52d363079788662.png
[20180409095320683]: /images/20220527/c78c9985b1ee4d658f7362e23063b94e.png
[20180409095327724]: /images/20220527/e7607ea34912473ca87b5230bd2b1edb.png
[20180409095334875]: /images/20220527/428a388bcadd41caba61396e72341a2b.png
[20180409095340994]: /images/20220527/74f81295cb254086bf45bfbc5c068b7a.png
[20180409095352153]: /images/20220527/9e191bdc759c4416b00caba336c32c46.png
[20180409095400393]: /images/20220527/2aea3d6db0204d09a1854d801fa34f37.png
[20180409095406839]: /images/20220527/3cdfb7a0916b4618b00d4f2bebcd84ff.png
[2018040909563414]: /images/20220527/f7a157d143a9486bb1f09b2fb5954afd.png