当前位置：首页 > news >正文

使用两个栈来实现一个队列

news 2026/6/13 10:31:11

在 Java 中，利用两个栈实现队列的核心思路是通过栈的“后进先出”特性模拟队列的“先进先出”特性：将一个栈（stackIn）作为“入队栈”，专门处理入队操作；另一个栈（stackOut）作为“出队栈”，专门处理出队/获取队首操作。只有当stackOut为空时，才将stackIn的所有元素转移到stackOut，从而实现“先进先出”。

核心原理

入队（offer）：直接将元素压入stackIn（O(1) 时间复杂度）。
出队（poll）：

- 若stackOut为空，将stackIn中所有元素依次弹出并压入stackOut（此时stackOut的栈顶就是队列的队首元素）；
- 弹出stackOut的栈顶元素（即队列的队首元素）。

获取队首（peek）：逻辑与poll类似，但仅获取stackOut的栈顶元素，不弹出。
判空（isEmpty）：当stackIn和stackOut都为空时，队列为空。

完整代码实现

import java.util.Stack; /** * 用两个栈实现队列 */ public class QueueByTwoStacks { // 入队栈：专门处理入队操作 private Stack<Integer> stackIn; // 出队栈：专门处理出队/获取队首操作 private Stack<Integer> stackOut; // 初始化 public QueueByTwoStacks() { stackIn = new Stack<>(); stackOut = new Stack<>(); } /** * 入队操作：直接压入入队栈 * @param x 要入队的元素 */ public void offer(int x) { stackIn.push(x); } /** * 出队操作：弹出队首元素 * @return 队首元素 * @throws RuntimeException 队列为空时抛出异常 */ public int poll() { // 先检查出队栈是否为空，为空则转移入队栈的元素 transferIfNeeded(); // 若仍为空，说明队列为空 if (stackOut.isEmpty()) { throw new RuntimeException("队列为空，无法执行poll操作"); } // 弹出出队栈的栈顶（队列的队首） return stackOut.pop(); } /** * 获取队首元素（不弹出） * @return 队首元素 * @throws RuntimeException 队列为空时抛出异常 */ public int peek() { // 先检查出队栈是否为空，为空则转移入队栈的元素 transferIfNeeded(); // 若仍为空，说明队列为空 if (stackOut.isEmpty()) { throw new RuntimeException("队列为空，无法执行peek操作"); } // 获取出队栈的栈顶（队列的队首） return stackOut.peek(); } /** * 判断队列是否为空 * @return 空返回true，否则返回false */ public boolean isEmpty() { return stackIn.isEmpty() && stackOut.isEmpty(); } /** * 辅助方法：当出队栈为空时，将入队栈的所有元素转移到出队栈 */ private void transferIfNeeded() { if (stackOut.isEmpty()) { while (!stackIn.isEmpty()) { stackOut.push(stackIn.pop()); } } } // 测试示例 public static void main(String[] args) { QueueByTwoStacks queue = new QueueByTwoStacks(); // 入队：1 -> 2 -> 3 queue.offer(1); queue.offer(2); queue.offer(3); // 输出队首：1 System.out.println("队首元素：" + queue.peek()); // 出队：1 System.out.println("出队元素：" + queue.poll()); // 输出队首：2 System.out.println("队首元素：" + queue.peek()); // 出队：2 System.out.println("出队元素：" + queue.poll()); // 入队：4 queue.offer(4); // 出队：3 System.out.println("出队元素：" + queue.poll()); // 出队：4 System.out.println("出队元素：" + queue.poll()); // 判空：true System.out.println("队列是否为空：" + queue.isEmpty()); } }

代码说明

栈的选择：直接使用 Java 内置的Stack类（也可使用Deque接口的LinkedList实现，Deque是栈的推荐替代方案，Stack是旧版类）。
核心辅助方法：transferIfNeeded()封装了“入队栈转出队栈”的逻辑，避免代码冗余，仅在stackOut为空时触发转移，保证效率。
异常处理：poll和peek操作时，若队列为空则抛出运行时异常，符合队列的常规行为。
判空逻辑：必须同时判断stackIn和stackOut，因为可能存在“入队栈有元素但出队栈为空”的中间状态。