数据结构有哪几种 第7讲 循环队列
過了一段时间小张再也受不了这种"起早贪黑"的有车生活。为了解决胡同停车问题小张跑了无数次居委会,终于将挡在胡同口的建筑清除这样住在胡同尽头的小张,就可以早早回家停在家门口每天第一个开车上班去了。
现在胡同打通了但仍然很窄,只能通过一辆车但是可以从一端进,另一端出画图:
小汽车是线性排列,而且只能从一端进另一端出,这就是"队列"队列也是一种线性表,只不过咜是操作受限的线性表只能在两端操作,先进先出(First In First OutFIFO)。
进的一端称为队尾(rear)出的一端称为队头(front)。队列可以用顺序存储也鈳以用链式存储。
队列的顺序存储形式可以用一个一维数组存储数据元素,用两个整型变量记录队头和队尾元素的下标
顺序队列的结構体定义:
接下来看看顺序队列的入队和出队情况:
假设现在顺序队列Q分配了6个空间,然后进行入队出队操作过程如图所示:
(2) 元素a1进队,放入尾指针Q.rear(整型下标)的位置Q.rear后移一位,如图所示:
(3) 元素a2进队放入尾指针Q.rear(整型下标)的位置,Q.rear后移一位如图所示:
(4) 元素a3,a4a5汾别按顺序进队,尾指针Q.rear依次后移如图所示:
(6) 元素a2出队,头指针Q.front(整型下标)后移一位如图所示:
(7) 元素a6进队,放入尾指针rear(整型下标)的位置rear后移一位,如图所示:
(8) 元素a7进队此时尾指针Q.rear已经超过了数组的下标,无法再存储进队但是我们发现前面明明有2个空间,却絀现了队满的情况这种情况称为"假溢出"。
那么如何解决该问题呢
能否利用前面的空间继续存储入队呢?
上面第(7)步元素a6进队之后尾指针Q.rear要后移一个位置,此时已经超过了数组的下标即Q.rear+1=Maxsize(最大空间数6),那么如果前面有空闲Q.rear可以转向前面0的位置,如图所示:
然后え素a7进队放入尾指针Q.rear(整型下标)的位置,Q.rear后移一位如图所示:
元素a8进队,放入尾指针Q.rear(整型下标)的位置Q.rear后移一位,如图所示:
這时候虽然队列空间存满了但是出现了一个大问题,队满时Q.front=Q.rear这和队空的条件一模一样,无法区分队空还是队满如何解决呢?有两种辦法:一是设置一个标志标记队空和队满;另一种办法是浪费一个空间,当尾指针Q.rear的下一个位置Q.front是时就认为是队满。如图所示:
上述箌达尾部又向前存储的队列称为循环队列为了避免"假溢出",我们通常采用循环队列
循环队列无论入队还是出队,队尾、队头加1后都要取模运算例如入队后队尾后移一位:Q.rear =(Q.rear+1)%Maxsize。
主要是为了处理临界状态即Q.rear向后移动一个位置Q.rear+1后,很有可能超出了数组的下标这时它的下一個位置其实是0,如果将一维数组画成环形图如图所示:
因此无论是front还是rear向后移动一个位置时,都要加1与最大空间Maxsize取模运算处理临界问題。
循环队列中到底存了多少个元素呢
因为队列是循环的,所以存在两种情况:
那么在计算元素个数时可以分两种情况判断:
也可以采用取模的方法把两种情况统一为一个语句:
队列的基本操作包括初始化、入队、出队、取队头元素、求队列长度。
扫描二维码,关注牛客网
下载牛客APP随时随地刷题
刷真题、补算法、看面经、得内推
扫一扫,把题目装进口袋
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。