算法:用两个栈实现队列

题目描述

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

解题思路

我们使用两个栈，in栈用来处理入栈操作，out栈用来处理出栈操作。一个元素进入in栈之后，出栈的顺序被反转，当元素需要出栈的时候，需要先进入out栈，此时元素出栈顺序再次反转，这样就和队列出栈的顺序一致了。

解题代码

Stack<Integer> in = new Stack<Integer>();
   Stack<Integer> out = new Stack<Integer>();

   public void push(int node) {

       in.push(node);
   }

   public int pop() {
       if(out.isEmpty()){
           while (!in.isEmpty()){
               //将in栈中的数据，加入到out栈，此时out栈的顺序就是出队列顺序
               out.push(in.pop());
           }

       }
       if(out.isEmpty()){
           throw new RuntimeException("队列空");
       }
       return out.pop();

   }