用两个栈实现队列

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

思路

队列是先进先出的，而栈是后进先出的，如何用两个栈来实现队列的效果呢？

我们假设只用 stack1 来存放元素，这样的话，直接 stack1.pop 是行不通的。每次要弹出元素时，将 stack1 的元素全部弹出，依次存放到 stack2 中，这样原本在 stack1 最底下的元素，就来到了 stack2 的顶部，使用 stack2.pop 就可以得到我们想要的结果。

import java.util.Stack;
public class Solution {
    
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(stack1.empty() & stack2.empty()) {
            throw new RuntimeException("Queue is empty");
        }
        if(stack2.empty()) {
            while(!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

小结

熟悉栈后进先出的特点，说不定在有些题目会派上大用场。用一种数据结构模拟另一种数据结构，要结合其特性去思考。