2015年7月6日星期一

[LeetCode] Implement Queue using Stacks

脑洞:做到150/216了。面试遇到过这道题了,当时有个follow up question想了很久才答上来,好像是:你现在push是O(1),pop的worse case是O(n)的,如果要保证pop是O(1),你要怎么做?(在push不必须是O(1)的情况下)


Problem:

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.

Java Code:

class MyQueue {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    // Push element x to the back of queue.
    public void push(int x) {
        stack1.push(x);
    }

    // Removes the element from in front of queue.
    public void pop() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        stack2.pop();
    }

    // Get the front element.
    public int peek() {
        if (stack2.empty()) {
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

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

2 条评论:

  1. 可以使用一个额外变量去记录front, 这样可以让peek时间复杂度到O(1)

    回复删除
    回复
    1. 谢谢分享啊,我当时是把 push 操作修改了,每次 push 一个新元素的时候先把 s1中的元素全部 pop 到s2里,然后 push 新元素到 s1,再把 s2 中的元素全部 push 回 s1。pop 的时候就直接从s1 pop。这样等于是把push的复杂度变成 O(n),pop 复杂度变成 O(1) 了。

      删除