双端队列

学习目标

本节学习双端队列，也就是 deque。

双端队列允许在两端插入和删除元素。它比普通队列更灵活，既可以模拟栈，也可以模拟队列，还常用于一些滑动窗口类问题。

---

什么是双端队列

普通队列只能从队尾入队、从队头出队。双端队列则允许两端都进行插入和删除。

左端                      右端
 ↓                        ↓
 A  <->  B  <->  C  <->  D

双端队列通常支持：

• 从左端插入。
• 从右端插入。
• 从左端删除。
• 从右端删除。
• 查看左端元素。
• 查看右端元素。

因为两端都能操作，所以它的使用范围比普通队列更广。

---

用双端队列模拟栈

如果只从同一端插入和删除，双端队列就可以模拟栈。

C++

deque<int> values;

values.push_back(10);
values.push_back(20);

int top = values.back();
values.pop_back();

Java

Deque<Integer> values = new ArrayDeque<>();

values.addLast(10);
values.addLast(20);

int top = values.removeLast();

Python

from collections import deque

values = deque()

values.append(10)
values.append(20)

top = values.pop()

C#

LinkedList<int> values = new LinkedList<int>();

values.AddLast(10);
values.AddLast(20);

int top = values.Last.Value;
values.RemoveLast();

这里所有元素都从右端进入，也从右端离开，因此符合后进先出规则。

---

用双端队列模拟队列

如果从一端插入、另一端删除，双端队列就可以模拟普通队列。

C++

deque<int> values;

values.push_back(10);
values.push_back(20);

int first = values.front();
values.pop_front();

Java

Deque<Integer> values = new ArrayDeque<>();

values.addLast(10);
values.addLast(20);

int first = values.removeFirst();

Python

from collections import deque

values = deque()

values.append(10)
values.append(20)

first = values.popleft()

C#

LinkedList<int> values = new LinkedList<int>();

values.AddLast(10);
values.AddLast(20);

int first = values.First.Value;
values.RemoveFirst();

这里元素从右端进入，从左端离开，因此符合先进先出规则。

---

双端队列适合什么场景

双端队列适合需要灵活处理两端元素的场景。

例如：

• 需要同时支持头部和尾部插入删除。
• 需要模拟栈或队列。
• 滑动窗口中需要维护窗口两端。
• 某些算法中需要从两端选择候选元素。

在 Python 中，collections.deque 是常用的双端队列结构。在 Java 中，ArrayDeque 经常用于栈和队列。在 C++ 中，deque 是标准库容器之一。C# 标准库没有直接同名的 Deque，简单场景可用 Queue、Stack 或 LinkedList 根据需求替代。

---

双端队列不是随便替代所有结构

双端队列很灵活，但并不意味着它永远优于栈和队列。

如果问题只需要后进先出，使用栈能让意图更清晰。如果问题只需要先进先出，使用队列也更直接。双端队列适合两端都可能操作的场景，而不是为了“功能更多”就到处使用。

---

本节小结

双端队列允许在两端插入和删除元素，因此可以模拟栈，也可以模拟队列。

它的优势是灵活，适合两端都需要操作的场景。选择时仍然要看问题本身的规则：只需要后进先出就用栈，只需要先进先出就用队列，两端都需要操作时再考虑双端队列。