为什么工程中常用 Deque 实现栈？

简化版

工程中常用 Deque，尤其 ArrayDeque，来实现栈，因为它支持同一端入栈、出栈、查看栈顶，操作均摊 O(1)，比旧的 Stack 类更现代，通常也避免了遗留同步开销。

详细版

把双端队列的一端固定为栈顶即可实现栈。例如用队头作为栈顶：push 对应 addFirst，pop 对应 removeFirst，peek 对应 peekFirst。Java 中推荐写接口类型 Deque<T>，实现用 ArrayDeque<T>。

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);      // addFirst
stack.push(2);
int top = stack.peek(); // 2
int x = stack.pop();    // 2

ArrayDeque 底层是可扩容循环数组，局部性好；Stack 继承自 Vector，属于较老设计，很多场景不推荐作为首选栈实现。

完整版教学

一、栈需要哪些操作

栈是后进先出结构，核心操作只有三个：入栈、出栈、查看栈顶。只要一个容器能在同一端高效插入、删除和读取，就可以作为栈的底层结构。

push(1), push(2), push(3)
栈顶 -> 3
pop() -> 3
下一个栈顶 -> 2

双端队列两端都能操作，所以固定一端当栈顶即可。

二、Deque 如何映射栈语义

Java 的 Deque 接口本身就提供栈风格方法：push、pop、peek。这些方法通常映射到队头操作。也可以显式使用 addFirst/removeFirst/peekFirst，语义更直接。

栈操作	Deque 方法	含义
push(x)	addFirst(x)	放到栈顶
pop()	removeFirst()	删除并返回栈顶
peek()	peekFirst()	查看栈顶

面试时要说明“固定同一端”，否则只说 Deque 两端能操作会显得没有落到栈语义上。

三、为什么常选 ArrayDeque

ArrayDeque 底层是循环数组，连续内存带来较好的缓存局部性；普通入栈出栈只移动头尾指针，均摊 O(1)。扩容时会复制数组，单次可能 O(n)，但摊到多次操作仍可认为均摊 O(1)。

容量 8，连续 push 8 次无需移动已有元素
第 9 次可能扩容复制
长期平均每次 push 仍接近 O(1)

相比链表实现，数组实现没有节点对象和前后指针开销，通常更适合作为纯栈。

四、为什么不首选 Stack

Java 的 Stack 是早期类，继承自 Vector，很多方法带有同步语义和历史包袱。现代 Java 更推荐使用 Deque 接口表达栈行为，用 ArrayDeque 作为默认实现。

选择	优点	缺点
Stack	老代码常见，API 直观	继承 Vector，设计较旧
ArrayDeque	快、轻量、可作栈和队列	不允许 null
LinkedList	也实现 Deque	节点开销大、局部性差

如果需要线程安全栈，要根据场景选择并发容器或外部同步，而不是盲目依赖 Stack。

五、空栈和 null 边界

pop/removeFirst 在空栈时会抛异常，pollFirst 会返回 null。如果元素类型允许 null，返回 null 会和“空”混淆，所以 ArrayDeque 不允许存 null。这反而让 API 语义更清晰。

Integer x = stack.pollFirst();
if (x == null) {
    // 表示没有元素，而不是弹出了一个 null
}

面试中可以补一句：业务代码里更倾向明确检查 isEmpty()，避免用异常控制正常流程。

六、常见误区与追问

记忆钩子：Deque 是容器能力，Stack 是使用方式；固定 Deque 的一端，就得到栈。

• 误区：Deque 和 Stack 是同一种东西。 Deque 是双端队列接口，栈只是它的一种受限用法。
• 误区：ArrayDeque 每次入栈都是严格 O(1)。 扩容时单次 O(n)，长期是均摊 O(1)。
• 误区：Stack 因为名字叫 Stack 就一定最好。 它是旧设计，现代 Java 通常推荐 Deque。
• 追问：为什么 ArrayDeque 不允许 null？ 避免 poll 返回值无法区分空队列和真实 null 元素。
• 追问：什么时候用 LinkedList？ 需要链表特性或持有节点做中间删除时才考虑；纯栈通常不如数组实现。
• 追问：多线程下怎么办？ 使用明确的并发结构或同步策略，不能把非线程安全的 ArrayDeque 直接共享写入。

七、加强记忆

工程里说“用 Deque 实现栈”，重点不是炫 API，而是三个判断：固定同一端满足 LIFO，ArrayDeque 均摊 O(1) 且局部性好，旧 Stack 有历史包袱。答题时把操作映射、复杂度和选型原因连起来，就是完整答案。