石嘴山市网站建设_网站建设公司_MongoDB_seo优化

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

核心原理

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

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

1. 获取队首（peek）：逻辑与poll类似，但仅获取stackOut的栈顶元素，不弹出。
2. 判空（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()); } }

代码说明

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

时间复杂度

• offer（入队）：O(1)（直接压栈）。
• poll/peek（出队/获取队首）：

• • 均摊复杂度 O(1)：每个元素最多被“压入stackIn→ 弹出stackIn→ 压入stackOut→ 弹出stackOut”四次，分摊到每个操作上为 O(1)；
  • 最坏复杂度 O(n)：当stackOut为空时，需要转移n个元素（n为入队栈的元素数）。

关键总结

• 双栈实现队列的核心是“分栈职责 + 按需转移”：入队只操作stackIn，出队只操作stackOut，仅当stackOut为空时才转移元素，避免重复转移。
• 与双队列实现栈相比，双栈实现队列的均摊时间复杂度更优（pop/peek 为均摊 O(1)），实际开发中更常用。