题目描述

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

答案

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(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

解答

本题简单的考察了队列与栈的特性,队列是先进先出,栈是先进后出。
可以将队列理解为一个中空的管道,栈是一个开口的瓶子。

现在我们需要用两个栈来模拟队列,首先假设我们要输入四个数字,分别为1,2,3,4.

我们将这四个数字注入到第一个栈中(简称A栈),里面的构造就变成了4,3,2,1的一个反转结构,如果这时我们再出栈,顺序就变成了4,3,2,1。

所以我们需要再把A栈里的东西出栈到第二个栈里(简称B栈),再放进B栈就变成了1,2,3,4。这时我们再输出就是正常的顺序了。

但是等一等,这样就完成了吗?

让我们想另一种情况,如果我们将1,2,3,4出栈的途中,比如1刚出栈,这时我们又要进栈一个5,会发生什么?

5进到A栈,然后再按照我们的规定进入了B栈,变成了5,2,3,4,显然后进来的5压倒了先进来的2,3,4的上面,这是不对的。

所以我们需要判断,如果在出栈的时候,B栈内部有东西,我们就不要把A栈里的东西放进B栈,如果B栈没东西,我们就把A栈的东西放进B栈再出栈即可


醉后不知天在水,满船清梦压星河