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.
Example:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false
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)
分析：
The idea behind using two stacks is simple. Whenever you enqueue an element, it goes in the right stack.
When you need to dequeue an element, you reverse the right stack and place it in the left stack so that you can retrieve the elements using FIFO order.
empty():
To check if the queue is empty, simply check that both the left and right stack are empty. This means that there >are no elements left to dequeue and no new elements have been enqueued.
peek():
If the left stack is not empty, the element on top of this stack is at the front of the queue.
If the left stack is empty, the right stack will be reversed and placed in the left stack.
enqueue():
Recall that the right stack is used to enqueue elements.
dequeue():
Remove the top of the left stack.
class MyQueue {
public:
/** Initialize your data structure here. */
stack<int> left, right;
/** Push element x to the back of queue. */
void push(int x) {
right.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
peek();
int first = left.top();
left.pop();
return first;
}
/** Get the front element. */
int peek() {
if (left.empty()) {
while (!right.empty()) {
left.push(right.top());
right.pop();
}
}
return left.top();
}
/** Returns whether the queue is empty. */
bool empty() {
return left.empty() && right.empty();
}
};
/**
* 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();
* bool param_4 = obj->empty();
*/
时间复杂度o(1),空间复杂度o(n)