软考——队列与双端对列

朱雀 2021-05-12 11:54 470阅读 0赞

**        这两天做题的时候遇到了双端对列的题，和大家分享一下。**

# 一、队列和栈 #

队列和栈我们都不陌生，学过数据结构的同学应该都知道在顺序结构中有这么两中存放数据的容器。

**队列：**在队列中，数据的进出方法是先进先出的，就像是一个管道一样，顺流而下，一灌到底，出口和入口不同。

![SouthEast][]

栈：在栈中数据进出的顺序是先进后出，就像一个桶一样，对于数据的存储为填塞式，并且出口和入口是一个。

![SouthEast 1][]        如图为两种数据存储结构的形象表示方法，这里面对于数据的进出方式的不同时他们的最大的不同之处，在这里还有一点要注意的是利用栈的这种特性可以使数据的排列顺序发生改变，如1,2,3,4,5,6 这几个数，我们在这里按序入列，无论如何都是一样的输出，而入栈就不同了，比如1,2先入栈 ，然后出栈就成了2,1，之后的如3入栈之后立刻出栈结果就是2,1,3，这个里面就有了一个问题，就是利用栈可以进行数据位置的调换，这个特点还可以用于对于递归调用的地址保存等作用。

上面两种存储结构各有各的好处，现在又有一种新的存储方式，就是双端队列，它集合了两种结构的优缺点。

# 二、双端队列 #

双端队列顾名思义，他有两个端，什么端呢，一般的队列也是有两个端，一个输入，一个输出。双端队列也有连个端，但是这两个端是输入输出均可的：

![SouthEast 2][]        这个队列有的好处很多，首先他每个段都可以出也可以如，如果只是用一个端出另一个端入，那么他的作用就和队列是一样的，如果是只用一个端输入输出，那么他又和栈的作用是一样的。

这里呢，我们要理解双端队列的使用方法决定了里面数据的排列顺序以及输出顺序。

我们遇到的问题是一个只能从一端输出的双端队列，如下图，一个双端队列，其中有e1,e2,e3,e4依次进入输出受限的双端队列，则得不到输出的序列是：

**A.** e4、e3、e2、e1       **B.** e4、e2、e1、e3    **C.** e4、e3、e1、e2    **D.** e4、e2、e3、e1

![SouthEast 3][]

首先我们但看左面，就是一个栈的模式，所以栈的输入输出形式这个肯定有，其次再看左面输出，右面输入，队列的模式也有，只是进入的方式有限制，所以我们来看选项，首先A就是把整个都倒序了，所以是栈的形式，正确。其次是C，e4e3是倒序，e1e2是正序，所以也是对的，因为是从两个地方进入队列的。看D和B选项，可能没有什么头绪，这个时候就要发挥想象了，首先他们的差别就是e1e3的位置不同，然后在这里我们的顺序是从1到4排列的，然而输出又是从左面开始的，我们可以想象，前面的进入顺序是e1从右入，e2从左入，e3再从右入，e4最后从左入才可以得到e4e2的顺序，所以显然选项D是错误的。

这里我们要牢记队列和栈的性质，结合选项的提示，就可以轻易的做出这样的题了。

[SouthEast]: /images/20210511/2e3f8a28559643d2a03308d360adafdf.png
[SouthEast 1]: /images/20210511/51f132ebd238437b88cb7f851009a903.png
[SouthEast 2]: /images/20210511/a94c87c5902d4a45917cd21a01b90d43.png
[SouthEast 3]: /images/20210511/13f18cf5903044d9b6427be17d13e510.png