author: Sergei Golitsyn
link: https://leetcode.com/problems/implement-queue-using-stacks/
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push
, peek
, pop
, and empty
).
Implement the MyQueue
class:
void push(int x)
Pushes element x to the back of the queue.int pop()
Removes the element from the front of the queue and returns it.int peek()
Returns the element at the front of the queue.boolean empty()
Returns true
if the queue is empty, false
otherwise.Notes:
push to top
, peek/pop from top
, size
, and is empty
operations are valid.
Example 1:
Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
In this problem, I will show you only one solution. The main trick will be in pop and peak operations. But hold on. Let’s do it step by step. First of all, we have to prepare a class and needed data structures:
static class MyQueue {
Stack<Integer> current;
Stack<Integer> tmp;
public MyQueue() {
current = new Stack<>();
tmp = new Stack<>();
}
static class MyQueue {
Stack<Integer> current;
Stack<Integer> tmp;
public MyQueue() {
current = new Stack<>();
tmp = new Stack<>();
}
}
And now, let’s add a push method:
public void push(int x) {
current.push(x);
}
Simple and clear, just add an element into the stack.
And what about pop? For pop operation, we
have to move all elements from the current stack to the tmp stack
And before it, we should check out tmp stack. If tmp stack contains an elements we can simply return an element from this stack.
public int pop() {
if (!tmp.isEmpty()) {
return tmp.pop();
}
while (!current.isEmpty()) {
tmp.push(current.pop());
}
return tmp.pop();
}
Let’s try to draw a picture.
push 1. → 1
push 2. → 2, 1
push 3. → 3, 2, 1
pop. → move to tmp -→ cur: 2, 1, tmp: 3
cur: 1, tmp: 2, 3
cur: tmp: 1, 2, 3
do you see it? after moving elements, all elements in the tmp stack are in the correct order.
Ahh, I was a bit shocked, but it is true. If you move elements from one stack into another, you will have elements in insert order, like in a queue.
Now, let’s implement peek function:
public int peek() {
if (!tmp.isEmpty()) {
return tmp.peek();
}
while (!current.isEmpty()) {
tmp.push(current.pop());
}
return tmp.peek();
}
Same logic as in the pop method.
And finally isEmpty method. Don’t forget that we have to check two queues.
public boolean empty() {
if (!tmp.isEmpty()) {
return tmp.isEmpty();
}
return current.isEmpty();
}
s2
is empty, the algorithm pops nn elements from stack s1 and pushes nn elements to s2
, where nn is the queue size. This gives 2n2n operations, which is O(n)O(n). But when stack s2
is not empty the algorithm has O(1)O(1) time complexity. So what does it mean by Amortized O(1)O(1)? Please see the next section on Amortized Analysis for more information.