2.2

在前面的篇章中咱们详细介绍了队列这种新的数据结构现在我们简单的回顾一下队列的三要素——数据的逻辑结构、数据的存储结构以及数据的运算。

队列的数据元素在逻辑上是呈现线性结构也就是说队列也是一种线性表只不过是一种操作受限的线性表。

队列中的数据元素在内存空间中可以通过顺序存储和链式存储两种方式进行存储。

通过顺序存储实现的队列我们称之为循环队列循环队列的空间大小是不可改变的循环的实现是通过取模运算实现数组下标的循环通过链式存储实现的队列我们称之为链队列链队列是通过队头指针与队尾指针分别指向单链表的表头与表尾进行实现

在逻辑结构上队列是属于一种操作受限的线性表队列中的元素只能从一端已进行插入从另一端进行删除因此我们可以定义在队列上的基本操作有

创建、销毁、从队尾进行增加、从队头进行删除、判空、查找队头元素

顺序存储在顺序存储中我们进行增加与删除的操作是通过队头指针与队尾指针存储的数组下标的修改来实现的因为数组的大小是预先申请好的因此在顺序存储中我们还需要对队列进行判满的操作根据不同的满队条件我们可以进行三种方式来实现队列——空间置换法、队长法以及标志法链式存储在链式存储中队列对空间的使用更加的灵活理论上将只要内存空间足够大队列就不会出现满队的情况。

在链式存储的实现中我们在定义数据类型时要将队列中各个结点的数据类型与队列的数据类型分开定义确保我们创建的队列是通过头尾指针指向各个结点的队列。

在今天的内容中我们将介绍一个武艺高超的队列——双端队列。

它的武艺究竟高超在什么地方呢下面我们一下来看一下吧

一、双端队列

双端队列指的是运行在两端进行入队与出队操作的队列其元素的逻辑结构依然是线性结构。

在双端队列中我们将队列的两端分别称为前端和后端两端都可以进行入队和出队。

如下所示

在双端队列中由于它的前端与后端都能进行入队和出队因此进行出队入队的元素满足下面的规则

从前端进的元素排列在队列后端进的元素的前面从后端进的元素排列在队列前端进的元素的后面无论是前端还是后端出队先出的元素排列在后出的元素的前面。

在双端队列中因为它的前端和后端都能够实现入队和出队所以他会有不同的操作形式

当我们只看前端或者只看后端的话我们就会发现它其实是一个栈因为只从一端进行入队和出队时元素满足后进先出(LIFO)的操作特性当我们只要求元素从前端进后端出或者从后端进前端出的话它此时就是一个队列因为此时的双端队列满足先进先出(FIFO)的操作特性

也就是说双端队列我们可以看做是栈和队列的结合体那如果我们限制双端队列一端的输入或输出会是怎么样呢下面我们一起来探讨一下

1.2

当我们只允许双端队列的一端进行输入时此时双端队列就会变成如下结构

在这种情况下队列中的元素在入队时是只能从一端入队但是出队不受限制所以这种形式的双端队列满足以下操作特性

对于允许入队的一端来说元素满足后入先出(LIFO)的操作特性对于入队受限的一端来说元素满足先入先出(FIFO)的操作特性

1.3

当我们只允许双端队列的一端输出时此时的双端队列就会变成如下结构

在这种情况下双端队列只能从一端进行出队入队不受影响因此这种形式的双端队列满足以下操作特性

在允许出队的一端元素满足LIFO的操作特性在出队受限的一端元素满足FIFO的操作特性

1.5

当我们只允许双端队列中的元素从哪一端进就从哪一端出的话此时的双端队列就会变成两个栈底相邻的栈如下所示

在这种情况下不管是从前端入队的元素还是从后端入队的元素都满足LIFO的操作特性。

这时可能有朋友会说我能不能限制只能从一端进从另一端出呢就如下面这样

从上图可以看到如果只能限制从一端进另一端出的话我们会发现此时的双端队列如果两个端都有元素入队的话此时是没办法出队的因此我们在双端队列中不能限制元素只能从一端进、从另一端出。

1.6

双端队列也是一种操作受限的线性表它同时具有栈和队列的操作特性当双端队列的一端的输入/输出受限时受限制的一端的满足队列的操作特性另一端满足栈的操作特性当双端队列的输入和输出都受限时此时的双端队列就会变成两个栈底相邻的栈。

介绍到这里可能会有朋友有疑问了我既然已经有了栈和队列这两种数据结构现在将它们组合在一起是为什么呢双端队列究竟有什么作用呢下面我们就一起来探讨一下

在数据结构这门科目中目前我对双端队列的理解是——双端队列主要出现在元素的排序上考试中一般也只是出现在选择题中题目会要求我们判断四个选项中哪个选项符合双端队列的操作特性或者不符合双端队列的操作特性。

【2010统考真题】某队列允许在其两端进行入队操作但仅允许在一端进行出队操作若元素a、b、c、d、e依次入此队列后再进行出队操作则不可能得到的出队序列是。

A.b,a,c,d,e

对于这一道题我们应该如何来求解呢下面我将自己的解题思路分享给大家

2.1

首先我先介绍的是一种比较基础的解法——暴力求解何为暴力呢就是将双端队列中的元素的所有情况全部列出来比如我要求解abcd四个元素在双端队列中的出队序列如果我们要对4个元素进行排列组合的话我就可以得到4!种如下所示

a,b,c,d

d,c,b,a那是不是说这24中序列都是有效序列呢下面我们就来逐个分析在不同形式的双端队列的情况下它们所能进行的排列组合的情况

2.1.1

对于双端队列而言既然它是栈和队列的结合体那么栈所满足的出队序列双端队列一定满足因此我们先来分析一下根据栈的特性它能够得到哪些出队序列

栈的操作特性是后入先出那么对栈而言我们在保证abcd这四个元素时按顺序依次入栈的条件下要想使元素d第一个出栈那么abc的出栈顺序必然是cba如下所示

也就是说如果我要让元素d第一个出栈那么只会存在一种出栈序列——d,c,b,a

同理当我需要让元素c第一个出栈时那对于元素b和元素a而言它们的次序肯定是b先出栈a再出栈那我们就能得到3种序列——c,d,b,a/c,b,d,a/c,b,a,d

当我们要让元素b先出栈时此时第二个出栈的元素可以是a、c、d任意一个当第二个出栈元素为d时那么对于元素c和元素a来说它们的出栈次序肯定是c先出a后出如下所示

因此当以元素d先出栈时我们可以得到5个出栈序列——b,a,c,d/b,a,d,c/b,c,a,d/b,c,d,a/b,d,c,a

同理当我们让a先出栈d第二个出栈时元素b和元素c的出栈顺序肯定是c,b这里我就不演示了也就是说此时我们也同样可以得到5个出栈序列——a,b,c,d/a,b,d,c/a,c,b,d/a,c,d,b/a,d,c,b

a,d,b,c/b,d,a,c/c,d,a,b/c,a,b,d/c,a,d,b/d,a,b,c/d,a,c,b/d,b,a,c/d,b,c,a/d,c,a,b

之所以不满足就是因为出栈和入栈受到了限制那如果在双端队列中这些序列又会如何呢

2.1.2

当在输入受限的双端队列中输出是不受影响的因此对于a,d,b,c这个序列而言它则可行起来了如下所示

因为两端都能出队所以我只要按顺序进行入队那么对于以a开始出队的序列是全部可行的同样此时以d开头的序列也会多出以下三种情况——d,a,b,c/d,a,c,b/d,c,a,b

这是因为我们只能从一端输入而要想使d先出队的话那元素a,b,c肯定已经入队之后我们才能开始进行出队操作

同理当我们想要让c先出队时那元素a、b肯定已经入队之后我们再进行出队操作的话那对于序列c,a,b,c/c,a,d,b/c,d,a,b而言都是可以实现的了

当我们想要让元素b先出队时那对于b,d,a,c这个出队序列也是可以实现的了

因此在输入受限的双端队列中只有d,b,a,c/d,b,c,a是无法实现的

2.1.3

当在输出受限的双端队列中我们要想得到对应的输出序列只能够通过输入的方式来将其顺序进行排列那在下面这些不满足栈的出栈序列中又会有哪些是符合要求的呢我们一起来看一下

a,d,b,c/b,d,a,c/c,d,a,b/c,a,b,d/c,a,d,b/d,a,b,c/d,a,c,b/d,b,a,c/d,b,c,a/d,c,a,b

对于序列a,d,b,c而言我们可以通过两端入队的方式来实现如下所示

同理当b要先输出的话那我们的输入输出顺序就是a入队-b入队-b出队-c从受限制的一端入队-d入队——此时队列里的排列顺序是d,a,c。

之后我们只需要依次执行出队就能得到b,d,a,c的出队次序了

当c要先输出时也就是说a和b已经入队了下面我们来看一下如何实现c,d,a,b/c,a,b,d/c,a,d,b这三种情况的排序

可以看到只要我们保证dab入队后的排列顺序就能完成对应的出队序列

可以看到在这种情况下我们可以通过输入端的不同完成对应的元素的排列顺序然后依次出队即可

可以看到不管我们怎么进行输入只要是c入队了那a和b就肯定是已经入队了因此a和b的出队顺序可以颠倒但是不可能会被隔开因此在输出受限的双端队列中这个出队序列是无法实现的。

同理当d先出队时我们只需要观察能不能通过入队的先后顺序来完成出队时的次序。

此时有

d,a,b,c/d,a,c,b/d,b,a,c/d,b,c,a/d,c,a,b这五种情况等待我们验证当d要第一个出队的话那势必a,b,c都以完成了入队也就是说a和b的位置关系肯定是紧邻着的那么我们就可以直接排除d,a,c,b和d,b,c,a这两种情况了。

因此在输出受限的双端队列中c,a,d,b/d,a,c,b/d,b,c,a这三种情况是无法实现的

2.1.4

当输入和输出都受限时不管元素是从哪端进入都是满足LIFO这个操作特性。

在这种情况下

a,d,b,c/b,d,a,c/c,d,a,b/c,a,b,d/c,a,d,b/d,a,b,c/d,a,c,b/d,b,a,c/d,b,c,a/d,c,a,b这些输出序列又能不能实现呢我们继续来看一下

可以看到此时我们是可以通过不同端的输入来完成对应的出队次序的排列的接下来只需要按照对应的次序进行出队即可

下面我们再来看看b,d,a,c这种情况对应的出入队情况如下所示

下面我们再看看c,d,a,b/c,a,b,d/c,a,d,b这三种情况如下所示

可以看到此时我们只要完成了前面两个元素的出队之后后面两个元素的次序是可以颠倒的因此以c为第一个出队元素的所有情况都是可以实现的

接下来就是最关键的d了因为d要先出队的话那必须要将abc都先完成入队在d,a,b,c/d,a,c,b/d,b,a,c/d,b,c,a/d,c,a,b这五种情况中我们将其拆分成3种情况——da、db和dc它们对应的出入队情况如下所示

可以看到当要确保a是第二个出队时那么b和c就不能和a在同一边因此b和c的出队顺序是一定的所以对于d,a,b,c这种情况就不可能发生

当第二个出队元素为b或者c时此时我们都可以通过调整abc的入队位置来实现对应的出队序列因此d,b,a,c/d,b,c,a/d,c,a,b这三种情况都是可以实现的

那如果我们不对输入和输出进行限制的话我们会发现d,a,b,c也是可以实现的如下所示

2.1.5

现在我们已经介绍完了不同情况下的双端队列可能出现的出队次序如果给这些元素的入队顺序进行编号的话那么a,b,c,d的入队序号依次是1,2,3,4现在我们可以根据这个入队序号做个总结

在输入输出不受限制的双端队列中元素可以以任意次序完成出队在输入受限的双端队列中4号元素要先出队的话1号元素与2号元素的出队一定是紧邻的在输出受限的双端队列中当3号元素和4号元素要完成先出队的话那么1号元素和2号的出队一定是紧邻的在输入输出都受限的双端队列中当4号元素与1号元素要完成先后出队的话那么2号元素和3号元素的出队顺序一定是32在栈中当4号元素要在第一或者第二个进行出栈时剩下的两个元素的出栈次序一定是满足LIFO

现在对于4个元素的出入队情况我们就已经分析完了可以看到如果是元素比较少的情况下这种暴力求解的方式也是不错的但是如果遇到了如10年的真题卷一样的有5个元素时我们如果使用这种方法的话明显是不合理的那我们又应该如何处理呢下面我就要介绍第二种方法——经验法

2.2

经验法是根据暴力求解法的归纳总结在介绍我的结论之前我们先要思考一个问题为什么会有这些不符合条件的情况发生

我相信有朋友已经想到了因为栈和队列操作特性的约束栈中的元素要满足LIFO而队列中的元素要满足FIFO因此当元素是从一端入队同一端出队时元素的出队符合LIFO当元素从一端入队另一端出队时元素的出队符合FIFO

对于栈而言越是入栈次序靠后的元素要先完成出栈时它前面元素的出栈顺序一定是按照LIFO对于输入受限的双端队列入队次序越靠后的元素要先完成出队那次序越靠前的元素在进行出队时一定与入队次序紧跟它的元素相邻对于输出受限的双端队列入队次序靠后的元素要先完成出队那次序靠前的元素一定是紧邻的对于输入输出都受限的双端队列入队次序越靠后的元素与入队次序越靠前的元素进行先后出队时中间的元素的出队次序一定是遵循LIFO

【2010统考真题】某队列允许在其两端进行入队操作但仅允许在一端进行出队操作若元素a、b、c、d、e依次入此队列后再进行出队操作则不可能得到的出队序列是。

A.b,a,c,d,e

从题目中我们可以得到结论这是一个输出受限的双端队列根据我们的结论越是靠后的元素要先完成出队次序靠前的元素一定是紧邻的。

下面我们再来看选项

A选项中是以b为第一个出队元素进行的出队那么这个序列肯定是存在的直接跳过B和C选项都是以d为第一个出队元素按照我们的结论靠前的元素一定时紧邻的也就是说a和b一定是先后进行出队的顺序可以改变但位置关系不能变因此C选项是错误的D选项中是以e为第一个出队元素那么a和b一定是紧邻的b和c一定是紧邻的可以看到它的出队次序是没问题的

可以看到在C选项中不管c元素从哪端入队都不可能在a和b的中间因此C选项错误。

PS:

这里分享的经验纯属我个人的一个思考总结不一定完全正确所以希望大家在做题时可以通过画图法来验证一下答案是否正确。

在今天的篇章中我们详细的探讨了一下不同形态的双端队列以及双端队列的使用并且今天还将我自己压箱底的经验分享了出来希望能够帮助各位更好的理解双端队列以及它的使用如果对于相关的知识点还有疑问的话可以在评论区进行提问我会尽快给大家进行答疑的哦