Problem

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:

  • 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, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

This problem is opposite of Implement stack using queues.

Follow Up

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

Solution

Method 1 - Using 2 Stacks (Making costly dequeue)

We’ll implement a FIFO queue using two stacks. Lets call the stacks Instack and Outstack.

Logic

Enqueue
  • An element is inserted in the queue by pushing it into the Instack.
Dequeue
  • An element is extracted from the queue by popping it from the Outstack.
  • If the Outstack is empty then all elements currently in Instack are transferred to Outstack but in the reverse order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class MyQueue {
    private Queue<Integer> inStack = new LinkedList();
    private Queue<Integer> outStack = new LinkedList();

    public void push(int x) {
        inStack.push(value);
    }
    public int pop() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
        return outStack.pop();
    }

    public int peek() {
        if (outStack.isEmpty()) {
	        while (!inStack.isEmpty()) {
		        outStack.push(inStack.pop());
	        }
	        return outStack.peek();        
        }
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

Complexity

Time Complexity:

  • Push - O(1)
  • Pop - O(N)
  • Top -  O(1)
  • Stack Size -  O(1)

Dry Run

  1. Enqueue 3, 4,
  2. Dequeue
  3. Enqueue 5, 6
  4. Dequeue
  5. Dequeue

At step 1, InStack={4, 3} , OutStack = {}. Top in stack points to 4. At step 2, InStack={} , OutStack{3, 4}, note that order is reversed. Top points to 3. Now, we pop the item, hence we pop out 3. OutStack={4} At Step 3, InStack={6, 5}, OutStack={4} At Step 4,   InStack={6, 5}, OutStack={}, 4 is popped out of OutStack At Step 5, again, InStack={}, OutStack={5, 6} = OutStack{6} , and 5 is popped out.

Method 2 - Using 2 Stacks (with costly enqueue)

Logic

Enqueue
1
2
3
4

enqueue(x)
 1) While inStack is not empty, push everything to outStack.
 2) Push x to inStack (assuming size of stacks is unlimited).
 3) Push everything back from outStack to inStack.
Dequeue
1
2

dequeue()
 1) Pop from inStack

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    public void push(int x) {
        while (!inStack.empty()) {
            outStack.push(inStack.pop());
        }
        inStack.push(x);
        while (!outStack.empty()) {
            inStack.push(outStack.pop());
        }
    }

    public int pop() {
        return inStack.pop();
    }

    public int peek() {
        return inStack.peek();
    }

    public boolean empty() {
        return inStack.empty();
    }
}

Complexity

Time Complexity:

  • Push - O(N)
  • Pop - O(1)
  • Top -  O(1)
  • Stack Size -  O(1)

Method 3 - Using 1 Stack (and Another Recursion stack)

But can we implement queue, using 1 stack only? Answer is yes, We can have 1 primary stack. We can get another temporary stack using call stack of recursion.

Steps remain the same:

  • You need to transfer elements from one stack to another temporary stack, to reverse their order.
  • Then push the new element to be inserted, onto the temporary stack
  • Then transfer the elements back to the original stack
  • The new element will be on the bottom of the stack, and the oldest element is on top (first to be popped)

Here is the code in java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public class MyQueue {
    private Stack<Integer> stack = new Stack <> ();

    public void push(int x) {
        if (!stack.empty()) {
            int topElem = stack.pop();
            insert(x);
            stack.push(topElem);
        } else
            stack.push(x);
    }

    public int pop() {
        return stack.pop();
    }

    public int peek() {
        return inStack.peek();
    }

    public boolean empty() {
        return inStack.empty();
    }
}