双端队列 (Double-Ended Queue)

双端队列是指允许两端都可以进行入队和出队操作的线性表。

1. 核心操作演示

双端队列在逻辑上可以看作是栈和队列的结合体。

• 前端操作 (Front)：对应 push_front 和 pop_front (绿色按钮)
• 后端操作 (Rear)：对应 push_back 和 pop_back (橙色按钮)

双端队列 (Deque)

双端队列就绪

Front End

Rear End

10

Front

20

30

Rear

---

2. 特殊的双端队列 (考研重点)

在实际应用或考试中，常考两个受限的变种：

(1) 输入受限的双端队列

定义：允许一端进行插入和删除，另一端只允许删除。

你可以把上面的演示想象成：禁用了右侧的“入队”按钮。

(2) 输出受限的双端队列

定义：允许一端进行插入和删除，另一端只允许插入。

你可以把上面的演示想象成：禁用了右侧的“出队”按钮。

思考题

如果输入序列是 1, 2, 3, 4，输出受限的双端队列能否得到 4, 1, 3, 2 的输出序列？