跳转到内容
veyliss

队列、栈与 ArrayDeque 面试题整理

约 7 分钟阅读发布于 2024/5/29

· 约 7 分钟阅读

队列和栈是数据结构里最基础、也最容易在面试中被追问的两个概念。

它们看起来都像是“存放一组元素的容器”，但核心区别在于元素进出顺序和操作位置限制。如果再放到 Java 集合体系里，还会涉及 Queue、Deque、List、Stack、ArrayDeque 这些类和接口的关系。

这篇文章按面试回答的方式整理一遍。

一、规则不同

Section titled “一、规则不同”

队列遵循 先进先出：

Queue: First In First Out, FIFO

也就是说，先进入队列的元素，会先被取出。

入队顺序：A -> B -> C
出队顺序：A -> B -> C

栈遵循 先进后出：

Stack: First In Last Out, FILO

也可以说是 后进先出：

Last In First Out, LIFO

也就是说，最后进入栈的元素，会最先被取出。

入栈顺序：A -> B -> C
出栈顺序：C -> B -> A

这是队列和栈最核心的区别。

二、插入和删除位置不同

Section titled “二、插入和删除位置不同”

队列的插入和删除发生在不同端：

  • 在一端插入元素，通常称为入队。
  • 在另一端删除元素，通常称为出队。

可以理解成排队买票：

队尾入队 -> [A, B, C] -> 队头出队

栈的插入和删除发生在同一端：

  • 插入元素叫入栈。
  • 删除元素叫出栈。
  • 能直接操作的一端叫栈顶。

可以理解成往桌上叠盘子：

栈顶
 C
 B
 A
栈底

新盘子放在最上面，拿的时候也只能从最上面拿。

三、遍历和访问方式不同

Section titled “三、遍历和访问方式不同”

队列通常适合按顺序处理任务，例如消息队列、线程池任务队列、广度优先搜索等场景。

队列在逻辑上更强调“从头部取、从尾部放”。如果底层是链表结构，可以通过节点指针向后遍历；如果底层是数组结构，也可以通过下标或循环数组逻辑访问。

栈更强调“只看栈顶”。如果要取出最早进入栈底的元素，就必须先把上面的元素依次弹出。

例如：

栈顶 -> C
       B
栈底 -> A

如果想拿到 A，就要先处理 C 和 B。

需要注意的是，面试里有时会说“队列遍历比栈快”。这个说法不能绝对化，因为遍历速度还取决于底层实现：

  • ArrayDeque 基于数组实现，访问和扩容方式与链表不同。
  • LinkedList 基于链表实现，遍历依赖节点引用。
  • Stack 继承自 Vector，底层也是数组结构，并且很多方法带同步开销。

所以更准确的说法是：队列和栈限制的是操作语义，不是简单决定遍历速度。具体性能要看底层实现。

四、Java 中接口实现不同

Section titled “四、Java 中接口实现不同”

从 Java 集合体系看，队列和栈并不是完全对称的两个接口。

队列通常使用 Queue 接口：

Queue<Integer> queue = new ArrayDeque<>();

Queue 继承自 Collection，常见方法包括：

offer(e)  // 入队，失败时通常返回 false
poll()    // 出队，队列为空时返回 null
peek()    // 查看队头，队列为空时返回 null

栈在早期可以使用 Stack 类：

Stack<Integer> stack = new Stack<>();

但在现代 Java 代码里，通常更推荐用 Deque 来模拟栈：

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

常见方法包括：

push(e)   // 入栈
pop()     // 出栈
peek()    // 查看栈顶

原因是 Stack 是一个比较旧的类，它继承自 Vector。Vector 的很多方法带同步机制，在大多数普通场景下并不是首选。

因此，面试里可以这样回答：

Java 中队列通常使用 Queue 或 Deque；栈不一定要用 Stack 类，实际开发中更推荐使用 Deque，常见实现是 ArrayDeque。

五、ArrayDeque 为什么常见

Section titled “五、ArrayDeque 为什么常见”

ArrayDeque 是 Deque 接口的一个常用实现。

Deque 的全称是 double-ended queue，也就是双端队列。它允许在两端插入和删除元素，因此既可以当队列用，也可以当栈用。

当作队列：

Deque<String> queue = new ArrayDeque<>();


queue.offer("A");
queue.offer("B");
queue.offer("C");


System.out.println(queue.poll()); // A
System.out.println(queue.poll()); // B
System.out.println(queue.poll()); // C

当作栈：

Deque<String> stack = new ArrayDeque<>();


stack.push("A");
stack.push("B");
stack.push("C");


System.out.println(stack.pop()); // C
System.out.println(stack.pop()); // B
System.out.println(stack.pop()); // A

可以看到，同样是 ArrayDeque，只要使用的方法不同，就可以表达不同的数据结构语义。

六、面试回答模板

Section titled “六、面试回答模板”

如果面试官问“队列和栈有什么区别”，可以按这几个点回答：

  1. 规则不同：队列是 FIFO，栈是 FILO/LIFO。
  2. 操作位置不同：队列一端插入、另一端删除；栈只在栈顶插入和删除。
  3. 使用场景不同：队列适合按顺序处理任务；栈适合回退、括号匹配、函数调用、深度优先搜索等场景。
  4. Java 实现不同：队列常用 Queue、Deque；栈可以用 Stack，但更推荐用 Deque 的实现类 ArrayDeque。
  5. 性能不能只按“队列快、栈慢”简单判断，要结合底层结构，例如数组、链表、同步开销和扩容机制。

七、小结

Section titled “七、小结”

队列和栈的区别可以先抓住一句话：

队列：先进先出，像排队。
栈：先进后出，像叠盘子。

在 Java 中，还要补充一句：

需要队列或栈语义时，优先考虑 Queue、Deque 和 ArrayDeque；不要一看到栈就只想到 Stack。

这样回答既覆盖了基础概念，也能体现出对 Java 集合体系的理解。

标签：