用两个栈来实现队列

楚天乐 89 0 条

用两个栈来实现队列

算法思想

  1. 什么是栈,后进先出
  2. 什么是队列,先进先出
  3. 如果有两个栈,如何模拟队列先进先出?假设有三个元素ABC进入栈1,我们按照队列的要求,pop操作应该弹出A。但此时栈1的数据弹出顺序是CBA。解决方法:需要出栈的时候,先把栈1所有数据逐个pop,并push到栈2。最后从栈2出栈,那么我们就可以得到A了
  4. 我们把栈1数据全部弹到栈2,那么要入栈如何破?自然是把栈2数据逐个pop,并push进入栈1。最后在把当前数据push进栈1,就好了不是么

上代码

import java.util.Stack;

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

    public void push(int node) {
        int val;
        // stack2 => stacl1
        while(!stack2.empty()){
            val = stack2.pop();
            stack1.push(val);
        }
        // push
        stack1.push(node);
    }

    public int pop() {
        int val;

        while(!stack1.empty()){
            val = stack1.pop();
            stack2.push(val);
        }

        return stack2.pop(); 
    }
}


发表我的评论
昵称 (必填)
邮箱 (必填)
网址
执行时间: 53.483963012695 毫秒