leetcode232.Implement Queue using Stacks

题目要求

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

通过队列实现一个栈的功能。栈的api为push（压入栈顶），pop（出栈），peek（栈顶元素），empty（栈是否为空）。这道题和之前的使用栈实现队列功能是类似的，可以参考我的这篇博客。

思路与代码

因为栈本质上是将输入的元素逆序输出，因此如果我们通过两个栈对输入的元素进行两次逆序操作就可以保证按照最初的顺序输出。那么什么时候进行逆序的操作呢？

思路一：倒入再倒回。
将栈想象为两个桶，每次我都想获得第一个桶中最底下的东西，因此我将第一个桶倒入第二个桶，这时原来在第一个桶底的元素就在第二个桶的最上面。取完第二个桶中的内容后，我再把东西倒回。这样每次都只需要往第一个桶里面添加新元素，如果想要获得第一个桶桶底的元素，就把它倒到第二个桶里面去。重复上述的操作。图示如下：

1.输入[1,2,3,4,5]

2.获得捅底的元素1，则将1号桶导入2号桶，获取元素后再倒回

3.输入[6]

4.获得当前捅底的元素2，那么操作同第二步

这个方法其实增加许多不需要的倒出倒入操作，那么有没有可能我们只在需要的时候对这么大的数据量进行倒入倒出操作呢？

---

思路二：多次加入，一次倒出
从上一个例子我们可以看见，桶1中的内容一定是输入顺序的逆序，而桶2中的内容则一定和输入顺序相同。那么我们能不能保证无时无刻，桶1中的元素全部位于桶2之后，从而确保每次从桶2中获得的元素是正确的顺序。而当桶2中没有元素时，只要导入桶1的元素就可以了。

方法是每次添入元素时，仍然直接加入桶1。但是当需要弹出元素时，则从桶2弹出。如果桶2是空的话，那么就把桶1中的内容倒入桶2。这样，下次加入的元素必然全部位于桶2后的所有元素，而桶2中的元素也能保证位输入顺序。图例如下：

1.输入[1,2,3,4,5]

2.弹出1

3.弹出2

4.输入[6,7]

这样我们确保了每个元素只会入栈出栈再入栈出栈两次，即进入桶1，弹出桶1，进入桶2，弹出桶2。极大的减少了不必要的入栈出栈。代码如下：

public class ImplementQueueusingStacks_232 {
    Stack<Integer> s1 = new Stack<Integer>();
    Stack<Integer> s2 = new Stack<Integer>();
    /** Push element x to the back of queue. */
    public void push(int x) {
        s1.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if(s2.isEmpty()){
            while(!s1.isEmpty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return s1.empty() && s2.empty();
    }
}