设有一个双端队列，元素进入该队列的顺序是1, 2, 3, 4。试分别求出满足下列条件的输出序列。(1)能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列;(2)能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列:(3)既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。
解 允许在一-进行插入和删除,但在另一端只允许插入的双端队列叫做输出受限的双端队列，允许在一端进行插入和删除，但在另一端只允许删除的双端队列叫做输入受限的双端队列。输出受限双端队列不能得到的输出序列有: 4132 423 1输人受限双端队列不能得到的输出序列有: 4213 423 1所以有:(1)4132(2)4213(3)4231[img=322x216]17ae0b8652daab4.png[/img]
举一反三
- 若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。
- 若以1234作为双端队列的输入序列,则既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是。【西安电子科技大学 1996 一、5(2分)】
- 设一个双端队列，元素进入该队列的次序为a，b，c，d。求既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列。【中山大学1999 一、4 （3分）】
- 青书学堂: (单选题) 已知输入序列是abcd,经过输出受限的双端队列后能得到的输出序列是( )。
- 已知输入序列是1234，则输入受限(仅允许由一端输入)但输出不受限(两端均可输出)的双端队列不可能得到的输出序列是______。 A: 4231 B: 1324 C: 3214 D: 2341
内容
- 0
已知输入序列是abcd，则经过输出受限的双端队列后能得到的输出序列是______。 A: dacb B: cadb C: dbca D: dbac
- 1
输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如下图所示。若有8、1、4、2依次进入输入受限的双端队列，则得不到输出序列(57)。 A: 2、8、 1、4 B: 1、4、8、2 C: 4、2、 1、8 D: 2、1、4、8
- 2
己知输入序列为1234，则输入受限仅由一端输入但输出不受限两端均可输出的双端队列不可以得到（）输出序列。 A: 4231 B: 1324 C: 3214 D: 4213 E: 2341
- 3
●输出受限的双端队列是指只有一端可以进行出队操作而从两端都可以进行入队操作的队列，如下图所示。对于输入序列abcd，经过一个初始为空且输出受限的双端队列后，不能得到的输出序列为(42)。 A: dabc B: dcba C: dcab D: dacb
- 4
已知输入序列为abcd，经过输出受限的双端队列后，能得到的输出序列是( )。 A: daeb B: cadb C: dbca D: 以上答案都不对