队列篇之循环队列和双端队列-讲解

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

前面已经介绍了队列性质以及在图中的应用，下面我们来介绍一下队列的另外两种形式，循环队列和双端队列。这两个知识点也是北工大考研经常出现的试题，多以填空选择题的形式出现。

一、顺序队列

顺序队列删除分为两种，一种在删除的时候，数据整体向前移，如图1所示；一种是移动队首的位置，并未真正删除元素，如图2所示。

图1

在图1中，每次删除元素都需要把剩余的元素整体前移，时间复杂度较高。

图2

在图2中，每次删除元素队首位置后移，需要删除的元素没有真正删除，而删除的元素的位置不能再利用，当入队的元素比较多的时候，会造成队列溢出。

假溢出：由于多次入队、出队，出现空余的存储空间而不能使用。

真溢出：队列存储已满，想要进行入队操作，造成队列溢出。

二、循环队列

为了解决顺序队列中的假溢出现象，引入循环队列，如下图所示。

循环队列可以充分利用已删除数据元素尚未释放的内存空间，并保持队列的连续性。

循环队列在执行入队操作的时候可以判定队列是否已满：（rear + 1）%maxSize == front。

三、双端队列

性质：双端队列具有队列和栈性质的数据结构，双端队列可进行两端访问及两端进行插入和删除操作。

还可使用受限的双端队列，即一端能够插入、删除，一端只能插入；一端能够插入、删除，一端只能删除。

四、真题解读

北京工业大学2016年硕士研究生入学考试试题--896

（1）单项选择题

   一个输入受限的双端队列（即仅允许一端输入，但两端都可以输出），当输入的序列是（1,2,3,4），不可能得到的输出序列是（）

A. （1,3,2,4）    B.（1,4,2,3）   C. （4,2,3,1）     D.（4,3,2,1）

【解题思路】：

受限的双端队列（允许一端输入，两端输出），已知输入的序列是（1,2,3,4）我们可以试探法的形式解决该问题。设入队操作为S，出队操作为X

A：SXSSXXSX

B：SXSSSXXX

D：SSSSXXXX

排除法可得C是不可能得到的输出序列。

（2）填空题

顺序队列实现时，通常会将数组看做一个首尾相连的环，这样做的好处______

【解题思路】：

如题所述，数组可以通过对数组下标进行取模操作，这样就可以循环操作数组，形成循环队列，从而可以防止队列元素溢出，充分利用数组空间，故答案为：防止队列元素溢出，充分利用空间。

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

欢迎小伙伴们点赞👍、收藏⭐、留言💬