剑指offer 5.用两个栈实现队列

时间限制：1秒 空间限制：32768K 本题知识点： 队列 栈

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

思路:
抽象的想象两个栈,调用push方法的时候在第一个栈中压入数据,然后在调用pop方法时,如果第二个栈为空,就从第一个栈中把数据倒入第二个栈,然后在第二个栈中取出顶部元素,等到取完的时候,再次倒入即可.

import java.util.Stack;

public class Solution5 {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
       /* while (!stack1.isEmpty()) { stack2.push(stack1.pop()); } int res = stack2.pop(); while (!stack2.isEmpty()) { stack1.push(stack2.pop()); } return res;*/
       if(stack1.empty() && stack2.empty()) {
           throw new RuntimeException("Queue is empty");
       }
       // 这种做法等于把stack2当作了队列的头,stack1当作尾部的部分,每次pop,都从头部pop,然后头部为空后,再把尾部的转换到头部,再pop,非常巧妙
       if(stack2.empty()) {
           while (!stack1.empty()) {
               stack2.push(stack1.pop());
           }
       }
       return stack2.pop();
    }

    public static void main(String[] args) {
        Solution5 s = new Solution5();
        s.push(1);
        s.push(2);
        s.push(3);
        s.pop();
        s.pop();
        s.push(4);
        s.pop();
        s.push(5);
        s.pop();
        s.pop();
    }
}