题目

• 概述：设计一个类，使用栈完成队列的主要功能：

1. push(x)：将x放入队尾
2. pop()：将队首元素移除并返回该元素
3. peek()：返回队首元素
4. empty()：队列为空返回true，反之false

只允许使用栈的标准操作：push(x)， pop()，peek()，empty()，size()

假设所给出的操作都是合理的

• 出处：https://leetcode-cn.com/problems/implement-queue-using-stacks/

思路

• 由于栈和队列的功能是相反的，想只使用一个栈实现队列的功能是不科学的，不妨试试用两个栈

• 每次执行队列的pop()操作都把一个栈的所有元素都pop()出来并依次push(x)到另一个栈中，则另一个栈栈顶元素即为原来那个栈栈底的元素，获取该元素后，将其pop()，再把剩下的元素pop()出来并依次push(x)到原先那个栈中即可，队列的push(x)和empty()的操作和栈的操作一致

• 由于peek()操作只是想要获取队首元素，而不需要移除元素，所以没必要将所有元素从一个栈移动到另一个栈，只需要在适当的时机存储队首的元素即可：

1. 执行push(x)操作前队列为空时
2. 执行pop()操作中将得到的元素返回时
3. 执行pop()操作中将另一个栈栈顶元素pop()后存储此时另一个栈的栈顶元素

特别注意：存储队首元素的元素类型应为包装类型，否则可能导致null类型拆箱时报空指针异常

代码

class MyQueue {
    private Integer mTopValue; //must be Integer avoid unboxing leading to NullException
    private LinkedList<Integer> mStack = new LinkedList<>();
    private LinkedList<Integer> mTempStack = new LinkedList<>();

    /** Initialize your data structure here. */
    public MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        if (mStack.isEmpty()) {
            mTopValue = x;
        }
        mStack.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        while (!mStack.isEmpty()) {
            mTempStack.push(mStack.pop());
        }
        int temp = mTempStack.pop();
        mTopValue = mTempStack.peek(); //must store after pop
        while (!mTempStack.isEmpty()) {
            mStack.push(mTempStack.pop());
        }
        return temp;
    }
    
    /** Get the front element. */
    public int peek() {
        return mTopValue;
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return mStack.isEmpty();
    }
}