题20

题20

题目

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

分析

题20 2024-08-25 20.19.00.excalidraw

解

C
本题的队列实际上是一个输出受限的双端队列,如图 3.11 所示。
A 操作: 左入 (或右入)、 左入、 右入、 右入、 右入。
操作: 左入 (或右入)、 左入、 右入、 左入、 右入。
D 操作: 左入 (或右入)、 左入、 左入、 右入、 左入。
C 操作: 左入 (或右入)、 右入、 因 未出,此时只能进队, 怎么进都不可能在 和 之间。
【另解】初始时队列为空,第 1 个元素 左入 (或右入) 后,第 2 个元素 无论是左入还是右入都必与 相邻,而选项 中 与 不相邻,不合题意。