Implement Stack using Queues

Difficulty: Easy, Asked-in: Microsoft, Amazon, Adobe.

Key takeaway: An excellent problem to visualise the use case of stack and queue operations.

Let’s understand the problem

Write a program to implement a stack using the queues. The implemented stack should support standard push(x) and pop() operations.

• void push(int x): Insert an element x to the top of the stack.
• int pop(): Remove an element from the top of the stack and return it.

Problem notes

• Stack is a last-in-first-out (LIFO) data structure, in which elements are added and removed from the top end. In contrast, the queue is a first-in-first-out (FIFO) data structure, in which elements are added from one end (back) and removed from the other end(front).
• We must use only standard queue operations.

Discussed solution approaches

• Using two queues: O(n) pop operation and O(1) push operation
• Using two queues: O(1) pop operation and O(n) push operation
• Using a single queue: O(1) pop operation and O(n) push operation

Using two queues: O(n) pop operation and O(1) push operation

We can get the basic solution idea by understanding the order of insertion and deletion in both data structures. In stack, we insert and delete elements from one end only, but in a queue, we insert elements at the back and delete elements from the front. So, to simulate a stack using a queue, we need to keep track of the last element inserted and make sure that it is the first element to be deleted.

Suppose we use a single queue. In this case, we can perform push operation by simply inserting the new element at the back. But if we want to perform pop operation, we need to remove the last element inserted, which is at the back of the queue. The question is: how do we remove the element at the back?

One idea is to continuously remove elements from the queue until we reach the element at the back. This would mean removing all the elements in the queue except for the last element, which is the top element of the stack. But before removing the last element, we need to store and maintain the order of the removed elements for future use. To do this, we can use an extra queue to store the removed elements.

Suppose we use two queues, Q1 and Q2, to simulate stack operations and declare a variable stackSize to track the current size of the stack.

Implementation of the push operation

To add a new element to the stack, we enqueue it to Q1. This means we insert element x at the back of queue Q1, which will become the top of the stack. After inserting the element, we increment stackSize by 1.

We are performing only one enqueue operation. So time complexity = O(1).

Implementation of the pop operation

To perform the pop operation, our goal is to remove the last element inserted into queue Q1 using another queue Q2. To achieve this, we can follow the following steps.

• If Q1 is empty, we throw an error message "stack underflow" and return. Otherwise, we run a loop until there is one element left in Q1. In this loop, we dequeue each element from Q1 and enqueue it into Q2.
• We dequeue the last remaining element in Q1 and store it in a variable stackTop. We also decrement stackSize by 1 to reflect the new size of the stack.
• Now we run a loop until Q2 is empty and move all the elements from Q2 to Q1.
• Finally, we return the value stored in the variable stackTop.

Optimised implementation of the pop operation

In the 3rd step, do we really need to move all the elements from Q2 to Q1? If we observe, the answer is no: the Q1 will be empty at that stage and elements in Q2 are in the same order as earlier in Q1. So rather than moving elements from Q2 to Q1, we just swap the reference of Q1 with Q2.

The algorithm dequeues n elements from Q1 and enqueues n − 1 element to Q2, where n is the size of the stack. So total queue operations = 2n − 1 and time complexity = O(n).

Note: It's an exercise for you to design an efficient algorithm for the top() operation.

Implementation pseudocode

class StackUsingQueue
    private:
        queue Q1, Q2
        stackSize

    constructor
        stackSize = 0

    push(x)
        add x to the back of Q1
        stackSize = stackSize + 1

    pop()
        if Q1 is empty
            print "Stack Underflow!"
            return INT_MIN

        while Q1 contains more than one element
            temp = front element of Q1
            remove front element from Q1
            add temp to the back of Q2

        stackTop = front element of Q1
        remove front element from Q1
        stackSize = stackSize - 1

        swap Q1 and Q2
        return stackTop

Using two queues: O(1) pop operation and O(n) push operation

Now the critical question is: can we think of another implementation similar to the above approach but in a reverse way i.e. O(1) pop and O(n) push? Let's think!

Implementation of the pop operation

Here idea is to maintain the front element of the queue as the top element of the stack. So, for removing an element from the stack, we simply dequeue the front element from Q1.

We are performing a constant number of operations i.e. only one dequeue operation. So time complexity = O(1). We are using constant extra space. So space complexity = O(1).

Implementation of the push operation

The new element is always inserted at the back of the queue. But for maintaining the stack order, we need to position the new element at the front of the queue. How do we do it? Let's think!

• We first move all elements from Q1 to Q2.
• Then we enqueue the new element x to the Q1.
• Now move all elements from Q2 to Q1. This ensures that the new element would be in the front of Q1. When we perform the next pop operation, we can easily access the new element from the front of the Q1.

Optimised implementation of the push operation

In the 3rd step of the push operation, there is no need to copy all the elements from Q2 to Q1. We have already discussed a similar idea for the pop operation in the above approach.

• We enqueue new element x to the empty queue Q2.
• Now we move all elements from Q1 to Q2.
• After this, the new element will be present at the front of Q2 and Q1 is empty. So rather than copy elements from Q2 to Q1, we just swap the references of Q1 and Q2.

The algorithm removes n elements from Q1 and inserts n + 1 elements to Q2, where n is the size of the stack. So total number of queue operations = 2n + 1. Time complexity = O(n). Space complexity = O(1)

Implementation pseudocode

class StackUsingQueue
    private:
        queues Q1 and Q2
        stackSize

    constructor
        stackSize = 0

    push(x)
        add x to the back of Q2
        stackSize = stackSize + 1
        while Q1 is not empty
            temp = front element of Q1
            remove the front element from Q1
            add temp to the back of Q2

        swap Q1 and Q2

    pop()
        if Q1 is empty
            print "Stack Underflow!!"
            return -1

        stackTop = front element of Q1
        remove the front element from Q1
        stackSize = stackSize - 1

        return stackTop

Using a single queue: O(1) pop and O(n) push

The above approaches use two queues. Now the critical question is: Can we optimize the implementation using a single queue? Let's think!

Suppose for the pop operation, we remove elements from the front. Now for the push operation, if we insert an element in the queue, it will be stored at the back. But we need the last inserted element to the front of the queue, so that it can be removed in O(1) time during the next pop operation. One idea is: after pushing the new element, reverse the order of the remaining queue elements by repeatedly removing each element from the front (except for the last element which is the newly inserted element) and inserting it at the back.

In the push operation, we remove n elements and insert n + 1 elements to Q, where n is the stack size. So total number of queue operations = 2n + 1. Time complexity of push operation = O(n).

Implementation pseudocode

class StackUsingQueue
    private:
        queue Q
        stackSize

    constructor
        stackSize = 0

    push(x)
        queueSize = size of Q
        add x to the back of Q
        stackSize = stackSize + 1

        while queueSize > 1
            temp = front element of Q
            remove the front element from Q
            add temp to the back of Q
            queueSize = queueSize - 1

    pop()
        if Q is empty
            print "Stack Underflow!"
            return INT_MIN

        stackTop = front element of Q
        remove the front element from Q
        stackSize = stackSize - 1
        return stackTop

Critical ideas to think!

• Is it possible to implement a stack where each operation has an amortised time complexity of O(1)?
• How does the efficiency of the above approaches depend on the frequency of push and pop? If push operation is much more frequent than the pop, which approach should be followed?
• Can we use some other idea to implement a stack using queues?
• Based on the complexity of enqueue or dequeue, which type of queue implementation would be most suitable for the above implementations - an array-based implementation or a linked list implementation?
• How do we implement the top() and isEmpty() operations in all of the above approaches? Is it possible to design a strategy to get the top element with an O(1) time complexity?

Suggested coding problems to practice

• Implement queue using stacks
• Min-stack problem
• Implement Stack and Queue using Deque
• Implement stack using a priority queue
• Sort a stack using a temporary stack
• Reverse a Stack using another Stack
• Find maximum in a stack

Please write in the message below if you find anything incorrect, or you want to share more insight, or you know some different approaches to solve this problem. Enjoy learning, Enjoy algorithms!