Leetcode 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).

解题思路：

方法一：

与Implement Stacks using Queue 类似，栈和队列的核心不同点就是栈是先进后出，而队列是先进先出，那么我们要用栈的先进后出的特性来模拟出队列的先进先出。那么怎么做呢，其实很简单，只要我们在插入元素的时候每次都都从前面插入即可，比如如果一个队列是1,2,3,4，那么我们在栈中保存为4,3,2,1，那么返回栈顶元素1，也就是队列的首元素，则问题迎刃而解。所以此题的难度是push函数，我们需要一个辅助栈tmp，把s的元素也逆着顺序存入tmp中，此时加入新元素x，再把tmp中的元素存回来，这样就是我们要的顺序了，其他三个操作也就直接调用栈的操作即可。

方法二：

上面那个解法虽然简单，但是效率不高，因为每次在push的时候，都要翻转两边栈，下面这个方法使用了两个栈_new和_old，其中新进栈的都先缓存在_new中，入股要pop和peek的时候，才将_new中所有元素移到_old中操作，提高了效率。但奇怪的是提交到Leetcode中运行时，run time 第一种比第二种好得多。

Java Code:

Method1:

import java.util.Stack;

class MyQueue {
     private Stack<Integer> s = new Stack<Integer>();
    // Push element x to the back of queue.
    public void push(int x) {
        Stack<Integer> temp = new Stack<Integer>();
        while(!s.empty()) {
            temp.push(s.pop());
        }
        s.push(x);
        while(!temp.empty()) {
            s.push(temp.pop());
        }
    }

    // Removes the element from in front of queue.
    public void pop() {
        s.pop();
    }

    // Get the front element.
    public int peek() {
        return s.peek();
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return s.empty();
    }
}

Method2:

import java.util.Stack;

class MyQueue {
    private Stack<Integer> _new = new Stack<Integer>();
    private Stack<Integer> _old = new Stack<Integer>();
    // Push element x to the back of queue.
    public void push(int x) {
        _new.push(x);
    }
    
    void shiftStack() {
        if (_old.empty()) {
            while (!_new.empty()) {
                _old.push(_new.peek());
                _new.pop();
            }
        }
    }

    // Removes the element from in front of queue.
    public void pop() {
     shiftStack();
        if(!_old.empty()) {
            _old.pop();
        }
    }

    // Get the front element.
    public int peek() {
     shiftStack();
        if(!_old.empty()) {
            return _old.peek();
        }
        return 0;
    }

    // Return whether the queue is empty.
    public boolean empty() {
        return _old.empty() && _new.empty();
    }
}

Reference:

1.http://www.cnblogs.com/grandyang/p/4626238.html