1 题目
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).
接口: 实现4个方法
2 思路
用2个stack，inbox和outbox
Queue:
- Push the new element onto inbox
Dequeue:
- If outbox is empty, refill it by popping each element from inbox and pushing it onto outbox
- Pop and return the top element from outbox
each element will be in each stack exactly once - meaning each element will be pushed twice and popped twice, giving amortized constant time operations.(用这个方法，每个元素只在两个stack中存储一份，每个元素将会被push pop两次，MyQueue的pop操作的时间复杂度是分摊的时间常数，最好O(1)，最坏O(n)).
复杂度:push O(1); pop O(1) or O(n); peek O(1) or O(n); empty O(1)
3 代码
MyQueue.java
import java.util.LinkedList;
// Java编程思想推荐在使用stack的时候，用LinkedList替代。
class MyQueue {
LinkedList<Integer> inbox = new LinkedList<Integer>();
LinkedList<Integer> outbox = new LinkedList<Integer>();
// Push element x to the back of queue.
public void push(int x) {
inbox.push(x);
}
// Removes the element from in front of queue.
public void pop() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
outbox.pop();
}
// Get the front element.
public int peek() {
if (outbox.isEmpty()) {
while (!inbox.isEmpty()) {
outbox.push(inbox.pop());
}
}
return outbox.peek();
}
// Return whether the queue is empty.
public boolean empty() {
return inbox.isEmpty() && outbox.isEmpty();
}
}
4 总结
- 巧妙的用两个
statck实现queue,数据只存储一份，很好的考察基本的数据结构能力。 - 由于题目假设
pop和peek都不会在队列为空的时候执行，避免了Null Pointer Exception.