题目

已知初始为空的队列 Q 的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若 Q 的入队序列是 1, 2, 3, 4, 5，则不能得到的出队序列是( )。

错因

A

误判 A 不能得到。看到 5 跑到最前、又出现 1, 2 这种保持原序的尾巴，会觉得是栈和队列两种行为同时出现，普通结构都解释不了。但本题恰好是双端队列，可以混合两种行为：把 1, 2 从"只入端"按原序入队（成为右端的尾），3, 4, 5 依次从"双向端"入队（5 在最前），出队全部从双向端，恰能得到 5, 4, 3, 1, 2。

构造路径（左端为双向端，右端为只入端）：右入 1 → 右入 2 → 左入 3 → 左入 4 → 左入 5，左到右形成 [5, 4, 3, 1, 2]，从左端依次出。

B

误判 B 不能得到。原因和 A 类似：5, 3, 1, 2, 4 看似交错混乱，其实可以通过合理选择"哪些元素从只入端入、哪些从双向端入"构造出来。

构造路径：右入 1 → 右入 2 → 左入 3 → 右入 4 → 左入 5，左到右形成 [5, 3, 1, 2, 4]，从左端依次出。

C

误判 C 不能得到。看到 4 突然冲到最前、然后 2, 1 反序、3 又顺位回到前面，会觉得需要"局部反转"普通结构办不到。其实双端队列的 push_front / push_back 任意组合可以拼出这种序列。

构造路径：左入 1 → 左入 2 → 右入 3 → 左入 4 → 右入 5，左到右形成 [4, 2, 1, 3, 5]，从左端依次出。

总解析

模型：把这种"一端只入、另一端可入可出"的结构视为输入受限的双端队列。每个元素到达时只有两种入队选择（push_front / push_back），出队只在"双向端"进行（pop_front）。判断一个出队序列是否合法 = 能否通过每步 2 选 1 的入队决策构造出该序列。

逐项验证（设左端为双向端，右端为只入端，标注每个元素从哪边入）：

序列	构造方案（→= 入队顺序，L = 左端入，R = 右端入）	最终左→右排列	可得？
A. 5,4,3,1,2	1R, 2R, 3L, 4L, 5L	[5, 4, 3, 1, 2]	✓
B. 5,3,1,2,4	1R, 2R, 3L, 4R, 5L	[5, 3, 1, 2, 4]	✓
C. 4,2,1,3,5	1L, 2L, 3R, 4L, 5R	[4, 2, 1, 3, 5]	✓
D. 4,1,3,2,5	——	——	✗

为什么 D 构造不出来：

观察 D = 4, 1, 3, 2, 5。要出 4 在最前，必须 4 push_front（左入）；要出 5 在最末，必须 5 push_back（右入）。中间段必须形成 [1, 3, 2]——即 1, 2, 3 三个元素入队后，左到右的顺序恰为 1, 3, 2。

枚举 1, 2, 3 三个元素只用 push_front / push_back 能构造的所有左到右序列：

• 先入 1 → [1]
  • push_front 2 → [2, 1]
    • push_front 3 → [3, 2, 1]
    • push_back 3 → [2, 1, 3]
  • push_back 2 → [1, 2]
    • push_front 3 → [3, 1, 2]
    • push_back 3 → [1, 2, 3]

四种结果：[3,2,1]、[2,1,3]、[3,1,2]、[1,2,3]，没有 [1, 3, 2]。原因是：要让 3 夹在 1 和 2 之间，只能通过"中间插入"，而双端队列两端入队恰恰做不到中间插入。

最终答案是 D（4, 1, 3, 2, 5）。

小结：输入受限双端队列做不到的事是"把后到的元素塞进已入队元素的中间"。任何要求 三者顺序为"先到的 a、最后到的 c、中间到的 b"这种"中间夹后"的中段，都不可达。