输入受限的双端队列是指元素只能从队列的一端输入、但可以从队列的两端输出,如下图所示。若有8、1、4

Question

输入受限的双端队列是指元素只能从队列的一端输入、但可以从队列的两端输出，如下图所示。若有8、1、4、2依次进入输入受限的双端队列，则得不到输出序列 （62） 。

A.2、8、1、4

B.1、4、8、2

C.4、2、1、8

D.2、1、4、8

Answer 1

正确答案：D
本题考查队列运算。对于输出序列2,8,1,4，其运算过程为：元素8,1,4,2依次进入队列，情形如下图所示。此时，元素2先出队列，元素8,1,4再依次出队，可得到输出序列2,8,1,4,但是在元素4和8出队列之前，元素1不能出队，所以得不到输出序列2,1,4,8。对于输出序列1、4、8、2，其运算过程为：元素8、1先进入队列，情形如下图所示。然后元素1出队，元素4入队并出队，元素2入队并出队，最后元素1出队，得到输出序列1、4、8、2。对于输出序列4、2、1、8，其运算过程为：元素8、1、4依次进入队列，如下图所示。然后元素4出队，元素2入队并出队，最后元素1和8依次出队，得到输出序列4、2、1、8。