LeetCode 用两个栈实现队列

Question

题目描述

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。 队列中的元素为 int 类型。

问题分析

先来回顾一下栈和队列的基本特点：

栈： 后进先出（LIFO）
队列： 先进先出

很明显我们需要根据 JDK 给我们提供的栈的一些基本方法来实现。先来看一下 Stack 类的一些基本方法：

既然题目给了我们两个栈，我们可以这样考虑当 push 的时候将元素 push 进 stack1，pop 的时候我们先把 stack1 的元素 pop 到 stack2，然后再对 stack2 执行 pop 操作，这样就可以保证是先进先出的。（负[pop]负[pop]得正[先进先出]）

考察内容

队列+栈

示例代码：

//左程云的《程序员代码面试指南》的答案
import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    //当执行 push 操作时，将元素添加到 stack1
    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        //如果两个队列都为空则抛出异常,说明用户没有 push 进任何元素
        if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        //如果 stack2 不为空直接对 stack2 执行 pop 操作，
        if(stack2.empty()){
            while(!stack1.empty()){
                //将 stack1 的元素按后进先出 push 进 stack2 里面
                stack2.push(stack1.pop());
            }
        }
          return stack2.pop();
    }
}