ImplementQueueUsingStacks [source code]

public class ImplementQueueUsingStacks {
static
/******************************************************************************/
public class MyQueue {
    private Integer head = null;
    private Stack<Integer> stack;
    private int size = 0;

    /** Initialize your data structure here. */
    public MyQueue() {
        stack = new Stack<Integer>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        if (size++ == 0) head = x;
        stack.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (size - 1 == 0) head = null;
        Stack<Integer> tmp = new Stack<>();
        for (int i = 0; i < size - 1; i++) {
            tmp.push(stack.pop());
        }
        int res = stack.pop();
        size--;
        for (int i = 0; i < size; i++) {
            if (i == 0) head = tmp.peek();
            stack.push(tmp.pop());
        }
        return res;
    }

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

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return size == 0;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ImplementQueueUsingStacks.MyQueue tester = new ImplementQueueUsingStacks.MyQueue();
        tester.push(1);
        tester.push(2);
        tester.push(3);
        System.out.println("peeking: " + tester.peek());
        for (int i = 0; i < 3; i++) System.out.println("popped: " + tester.pop());
        System.out.println(tester.empty());
    }
}

这个题目总体的思路还是非常简单的, 就是一个很基础的东西, 就是有少数的小技巧:

• peek 需要专门用一个 instance var 来保存, 因为 peek 可能被大量使用, 所以把它单独存住可能会大幅度的提高aggregate performance.
• size也是专门用一个 int 来保存, 而不是依赖 Stack 本身的 API; 这个在 Sedgwick 的书上已经见识过了, 这个是一个可以大幅提升速度的技巧, 却很容易实现;

可以看到上面最后一个注释里面给出的, pop 和 peek 返回的都是 int, 所以这里估计不用考虑 generic;

这个问题上唯一一个调了半天的一个 bug, 就是这个:

for (int i = 0; i < tmp.size(); i++) {  
    if (i == 0) head = tmp.peek();  
    stack.push(tmp.pop());  
}

这个刚开始死活半天都想不出来, 后来其实这个的原因就跟之前写 BFS 的时候, 每一个 level 的 iteration 里面要先专门把 queue 的 size 存下来一样; 因为你 tmp 的 size 是一直在改变的;
借此总结的一个教训就是, 不要在 loop 的 header 里面使用除了 array 以外的其他的 collection 的 size API 作为 range; 这个是一个新手很容易上当的地方;

Integer的 null 是可以直接 print, 不需要自己再专门判断一下;

最后的速度是94ms (83%), 还算可以;

editorial给出了两种思路, 第一种是 push 的时候完成我这里的这个O(n) 的操作(用一个 temp Stack 完成一个把 newest 放到 bottom 的操作), 这样 pop 就可以做到O(1);
第二种思路就是我这里的思路, 把 push 做成O(1);
看起来好像没有什么神奇的地方, 不过他这个 editorial 给出一个观点, 就是第二种思路, 其实可以做到最后的amortized performance是O(1), 这个是一个很有意思的事情, 而且事实上这种问题感觉是很容易在面试的时候被问到的. 我当时也不知道为什么就选择让 push 成为O(1).
好像我这个做法并不能做到O(1)的 amortized;

回头重新看了一下, 他这个方法实际上比我的复杂, 他是维护两个 stack: s1 and s2; 然后当第一次 pop 的时候, 直接s1的全都倒序 push 到 s2里面去; 然后 pop 的默认 stack 是 s2, 只有当 s2空了以后, 才重新做一次 s1倒灌. 他这样做确实是可以做到O(1)的 amortized 的; 很聪明;

private Stack<Integer> s1 = new Stack<>();  
private Stack<Integer> s2 = new Stack<>();  

// Push element x to the back of queue.  
public void push(int x) {  
    if (s1.empty())  
        front = x;  
    s1.push(x);  
}  
// Removes the element from in front of queue.  
public void pop() {  
    if (s2.isEmpty()) {  
        while (!s1.isEmpty())  
            s2.push(s1.pop());  
    }  
    s2.pop();      
}  
// Return whether the queue is empty.  
public boolean empty() {  
    return s1.isEmpty() && s2.isEmpty();  
}  
// Get the front element.  
public int peek() {  
    if (!s2.isEmpty()) {  
            return s2.peek();  
    }  
    return front;  
}

不过他这个代码写的好像有点问题; pop 的返回值写了个 void;

Problem Description

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).
Difficulty:Easy
Category:Algorithms
Acceptance:36.40%
Contributor: LeetCode
Companies
microsoft bloomberg
Related Topics
stack design
Similar Questions
Implement Stack using Queues

/**

• 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();
  */