脑洞:做到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());
}
}
可以使用一个额外变量去记录front, 这样可以让peek时间复杂度到O(1)
回复删除谢谢分享啊,我当时是把 push 操作修改了,每次 push 一个新元素的时候先把 s1中的元素全部 pop 到s2里,然后 push 新元素到 s1,再把 s2 中的元素全部 push 回 s1。pop 的时候就直接从s1 pop。这样等于是把push的复杂度变成 O(n),pop 复杂度变成 O(1) 了。
删除