题目描述

解题思路

题目需求是使用栈（后进先出）来达到队列的效果（先进先出）。

对此我们可以使用两个栈来完成队列的操作，步骤如下：

1. 创建两个栈：输入栈和输出栈（输入栈用来传入元素push，输出栈用来输出元素pop）
2. 当需要入队时，输入栈push(x);
3. 当需要出队时，如果输出栈不为空直接pop()；如果输出栈为空，则现将输入栈的所有元素压入输出栈中，然后再输出栈pop；
4. 当输入栈和输出栈全部为空时，则队列为空。

代码实现

class MyQueue {

    Stack<Integer> inStack;
    Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<Integer>();
        outStack = new Stack<Integer>();
    }
    
    public void push(int x) {
        inStack.push(x);        //输入栈进栈x
    }
    
    public int pop() {
        if(outStack.isEmpty()){
            inToOut();      //将输入栈的元素，全部入栈输出栈
        }
        return outStack.pop();      //返回输出栈的栈顶元素
    }
    
    public int peek() {
        if(outStack.isEmpty()){
            inToOut();
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        if(inStack.isEmpty()&&outStack.isEmpty()){      //输入栈和输出栈都为空时，模拟队列为空
            return true;
        }
        return false;
    }

    public void inToOut(){
        while(!inStack.isEmpty()){
            outStack.push(inStack.pop());       //输入栈的元素全部出栈，并压入输出栈中
        }
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */class MyQueue {

    Stack<Integer> inStack;
    Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<Integer>();
        outStack = new Stack<Integer>();
    }
    
    public void push(int x) {
        inStack.push(x);        //输入栈进栈x
    }
    
    public int pop() {
        if(outStack.isEmpty()){
            inToOut();      //将输入栈的元素，全部入栈输出栈
        }
        return outStack.pop();      //返回输出栈的栈顶元素
    }
    
    public int peek() {
        if(outStack.isEmpty()){
            inToOut();
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        if(inStack.isEmpty()&&outStack.isEmpty()){      //输入栈和输出栈都为空时，模拟队列为空
            return true;
        }
        return false;
    }

    public void inToOut(){
        while(!inStack.isEmpty()){
            outStack.push(inStack.pop());       //输入栈的元素全部出栈，并压入输出栈中
        }
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */