Implement Queue Using Two Stacks

Difficulty: Easy, Asked-in: Facebook, Microsoft, Amazon, Adobe, Goldman Sachs, Morgan Stanley, Walmart, Flipkart

Key takeaway: An excellent problem to learn use cases of stack and queue operations in problem-solving.

Let’s understand the problem

Write a program to implement a queue using two stacks. The implemented queue should support standard enqueue and dequeue operations.

• void enqueue(int x): Insert element x to the back of queue.
• int dequeue(): Remove an element from the front of queue.

Problem Note

• Stack is last-in-first-out (LIFO) data structure, in which elements are added and removed from the same end, called top. In contrast, queue is a first-in-first-out (FIFO) data structure, where elements are added from the back end and removed from the front end.
• We must use only standard stack operations like push(x), pop(), top(), size(), and isEmpty() for implementing queue.

Discussed solution approaches

• Using two stacks: dequeue O(1) and enqueue O(n)
• Using two stacks: enqueue O(1) and dequeue O(1) average

Using two stacks: dequeue O(1) and enqueue O(n)

Let's visualize difference between order of elements in stack and queue.

Understanding stack order: Suppose we first push 1, 2, 3, 4, 5 into stack and pop them one by one. The order of popped output will be 5, 4, 3, 2, 1. Here 5 is the last inserted element that is coming first, and 1 is the first inserted element that is coming last.

Understanding queue order: Suppose we first enqueue 1, 2, 3, 4, 5 into queue and dequeue them one by one. The order of dequeued output will be 1, 2, 3, 4, 5. Here 5 is the last inserted element that is coming last, and 1 is the first inserted element that is coming first.

From above observation, the final stack output (5, 4, 3, 2, 1) is in the reverse order of the final queue output (1, 2, 3, 4, 5). So before popping elements from stack, if we reverse the order of elements, we will get popped output in queue order. How do we implement this? Let's think!

One idea would be to keep newly arrived element at the bottom of stack during push operation. In other words, we can keep the oldest element at the top of stack. Let's visualize this via example.

Suppose we push 1, 2, 3, 4, 5 into stack. Based on above strategy, the most recent element 5 will be at the bottom and the oldest element 1 will be at the top. The final order of elements in the stack will be 5, 4, 3, 2, 1. If we pop stack elements, they will come out in queue order: 1, 2, 3, 4, 5.

Enqueue operation idea: For enqueue operation, we need to insert new element at the bottom of stack. For this, we can use another auxiliary stack to maintain the oder of elements.

Step1: First transfer stack elements to auxiliary stack.

Step 2: Now push new element on top of auxiliary stack.

Step 3: Again transfer all auxiliary stack elements to main stack. 

After this process, new element will go to the bottom of main stack, which will come last during the dequeue operation. In other words, the oldest element will be on the top of main stack, which will come first during dequeue operation.

Dequeue operation idea: We simply remove elements from the top of main stack.

Our queue model will use two stacks: one for dequeue operation and two for enqueue operation. Suppose we use mainStack and tempStack to simulate queue process. Note: Assume that the size of each stack is unlimited.

Implementation of dequeue operation

If mainStack is empty, throw an empty error and return. Otherwise, pop the top element from mainStack and return it. We also decrement the queue size by 1.

int deQueue() 
{ 
    if (mainStack.empty()) 
    { 
        print("Queue is Empty!")
        return INT_MIN
    } 
    int stackTop = mainStack.pop() 
    queueSize = queueSize - 1
    return stackTop
} 

Constant number of stack operations will be performed, so time complexity = O(1). We are not using extra space, so space complexity = O(1)

Implementation of enqueue operation

• If mainStack is not empty, pop each element from mainStack and push it to tempStack.
• Push new element to the top of tempStack.
• Finally, push every element back to mainStack from tempStack.
• Increment the queue size value by 1.

Implementation pseudocode

void enQueue(int x) 
{ 
    int stackTop
    while (!mainStack.empty()) 
    { 
        stackTop = mainStack.pop()
        tempStack.push(stackTop)
    }
    tempStack.push(x)
    queueSize = queueSize + 1
    while (!tempStack.empty()) 
    { 
        stackTop = tempStack.pop()
        mainStack.push(stackTop)
    } 
} 

Suppose we have n elements in main stack when new element arrived. So each element except new element is pushed and popped twice, and new element is popped and pushed once. 

Total stack operations = Total number of push operations + Total number of pop operations = 2n + 1 + 2n + 1 = 4n + 2. Time complexity = Total stack operations * O(1) = (4n + 2)* O(1) = O(n)

We are using O(n) extra space for tempStack. Space complexity = O(n). Note: It's an exercise for you to design an efficient algorithm for the front() operation.

Implementation code C++

class QueueUsingStack
{ 
    int queueSize;
    stack<int> mainStack, tempStack;

public:
    QueueUsingStack()
    {
        queueSize = 0;
    }

    void enQueue(int x) 
    { 
        int stackTop;
        while (!mainStack.empty()) 
        { 
            stackTop = mainStack.top();
            mainStack.pop();
            tempStack.push(stackTop);
        }
        tempStack.push(x);
        queueSize = queueSize + 1;
        while (!tempStack.empty()) 
        { 
            stackTop = tempStack.top();
            tempStack.pop();
            mainStack.push(stackTop);
        } 
    } 

    int deQueue() 
    { 
        if (mainStack.empty()) 
        { 
            cout << "Queue is Empty!" << endl;
            return INT_MIN;
        } 
        int stackTop = mainStack.top(); 
        mainStack.pop();
        queueSize = queueSize - 1;
        return stackTop;
    } 
};

Implementation code Python

class QueueUsingStack:
    def __init__(self):
        self.queueSize = 0
        self.mainStack = []
        self.tempStack = []

    def enQueue(self, x):
        stackTop = None
        while self.mainStack:
            stackTop = self.mainStack.pop()
            self.tempStack.append(stackTop)
        self.tempStack.append(x)
        self.queueSize = self.queueSize + 1
        while self.tempStack:
            stackTop = self.tempStack.pop()
            self.mainStack.append(stackTop)

    def deQueue(self):
        if not self.mainStack:
            print("Queue is Empty!")
            return -sys.maxsize
        stackTop = self.mainStack.pop()
        self.queueSize = sel.queueSize - 1
        return stackTop

Implementation code Java

public class QueueUsingStack 
{
    private int queueSize;
    private Stack<Integer> mainStack;
    private Stack<Integer> tempStack;

    public QueueUsingStack() 
    {
        queueSize = 0;
        mainStack = new Stack<>();
        tempStack = new Stack<>();
    }

    public void enQueue(int x) 
    {
        int stackTop;
        while (!mainStack.empty()) 
        {
            stackTop = mainStack.pop();
            tempStack.push(stackTop);
        }
        tempStack.push(x);
        queueSize = queueSize + 1;
        while (!tempStack.empty()) 
        {
            stackTop = tempStack.pop();
            mainStack.push(stackTop);
        }
    }

    public int deQueue() 
    {
        if (mainStack.empty()) 
        {
            System.out.println("Queue is Empty!");
            return Integer.MIN_VALUE;
        }
        int stackTop = mainStack.pop();
        queueSize = queueSize - 1;
        return stackTop;
    }
}

Using two stacks: enqueue O(1) and dequeue O(1) average

Another implementation idea would be thinking in a reverse way: We can keep newly arrived element at the top of stack and the oldest element at the bottom of stack.

Enqueue operation implementation

Here enqueue operation is simple: We add new element to the top of mainStack and increment queue size value by 1.

void enQueue(int x) 
{ 
    mainStack.push(x)
    queueSize = queueSize + 1
}

Constant number of stack operations will be performed, so time complexity = O(1). We are not using extra space, so space complexity = O(1).

Dequeue operation implementation

For dequeue operation, we need to remove the bottom element of mainStack, which will be the oldest element.

Case 1 (When tempStack is empty): We pop all elements from mainStack and push them to tempStack, which helps us to store elements of mainStack in reverse order. Now, bottom element of mainStack will be at the top of tempStack. So pop the top element from tempStack to perform dequeue operation.

Case 2 (When tempStack is not empty): There is no need to transfer elements from one stack to another and we just pop the top element of tempStack. Why? Think! When tempStack is empty after sequence of dequeue operations, we follow the same procedure: Transfer data from mainStack to tempStack.

Implementation steps

• If both stacks are empty, we throw an error and return.
• If mainStack is not empty and tempStack is empty, we pop each element from mainStack and push it to tempStack. Now we pop the top element from tempStack and return it.
• If both stacks are not empty, we pop the top element from tempStack and return it.
• We also decrement the value of queue size by 1.

Implementation pseudocode dequeue operation

int deQueue()
{ 
    int stackTop
    if (mainStack.empty() && tempStack.empty()) 
    { 
        print("Queue is empty!") 
        return
    }
    if (tempStack.empty()) 
    { 
        while (!mainStack.empty()) 
        { 
            stackTop = mainStack.pop()
            tempStack.push(stackTop)
        }
    }
    stackTop = tempStack.pop()
    queueSize = queueSize - 1
    return stackTop
}

Implementation code C++

class QueueUsingStack
{ 
    int queueSize;
    stack<int> mainStack, tempStack;

public:
    QueueUsingStack()
    {
        queueSize = 0;
    }

    void enQueue(int x) 
    { 
        mainStack.push(x);
        queueSize = queueSize + 1;
    }

    int deQueue()
    { 
        int stackTop;
        if (mainStack.empty() && tempStack.empty()) 
        { 
            cout << "Queue is empty!" << std::endl; 
            return INT_MIN;
        }
        if (tempStack.empty()) 
        { 
            while (!mainStack.empty()) 
            { 
                stackTop = mainStack.top();
                mainStack.pop();
                tempStack.push(stackTop);
            }
        }
        stackTop = tempStack.top();
        tempStack.pop();
        queueSize = queueSize - 1;
        return stackTop;
    }
};

Implementation code Python

class QueueUsingStack:
    def __init__(self):
        self.queueSize = 0
        self.mainStack = []
        self.tempStack = []

    def enQueue(self, x):
        self.mainStack.append(x)
        self.queueSize = self.queueSize + 1

    def deQueue(self):
        stackTop = None
        if not self.mainStack and not self.tempStack:
            print("Queue is empty!")
            return -sys.maxsize
        if not self.tempStack:
            while self.mainStack:
                stackTop = self.mainStack.pop()
                self.tempStack.append(stackTop)
        stackTop = self.tempStack.pop()
        self.queueSize = self.queueSize - 1
        return stackTop

Implementation code Java

public class QueueUsingStack 
{
    private int queueSize;
    private Stack<Integer> mainStack;
    private Stack<Integer> tempStack;

    public QueueUsingStack() 
    {
        queueSize = 0;
        mainStack = new Stack<>();
        tempStack = new Stack<>();
    }

    public void enQueue(int x) 
    {
        mainStack.push(x);
        queueSize = queueSize + 1;
    }

    public int deQueue() 
    {
        int stackTop;
        if (mainStack.empty() && tempStack.empty()) 
        {
            System.out.println("Queue is empty!");
            return Integer.MIN_VALUE;
        }
        
        if (tempStack.empty()) 
        {
            while (!mainStack.empty()) 
            {
                stackTop = mainStack.pop();
                tempStack.push(stackTop);
            }
        }
        
        stackTop = tempStack.pop();
        queueSize = queueSize - 1;
        return stackTop;
    }
}

Time and space complexity of dequeue operation

When tempStack is not empty: Above algorithm performs only one pop operation. So time complexity of dequeue operation is O(1), which is the best-case scenario.

When tempStack is empty: Above algorithm pop n elements from mainStack, then push n elements to tempStack and finally pop the top element from tempStack (n is the queue size). Total stack operations = n + n + 1 = 2n + 1. So time complexity of dequeue operation is O(n), which is the worst-case scenario.

However, in a sequence of dequeue operations, the worst case will not occur frequently: Some dequeue operations will be O(1), and some will be O(n). For example, this is just like the situation of a dynamic array where logn number of insertions takes linear time, and other insertions take constant time.

In above code, dequeue operation can be costly only when tempStack is empty and there is a need for data transfer between mainStack and tempStack. Suppose an ideal picture: There is n number of enqueue operations followed by n number of dequeue operations. Total stack operations = Total stack operations for n enqueue operations + Total stack operations for 1st dequeue operation + Total stack operations for remaining n - 1 dequeue operation = n + 2n + 1 + n - 1 = 4n

For 2n queue operations, code will perform 4n stack operations. So for each queue operation, on average, code will perform two stack operations. So average or amortised case time complexity of each queue operation is O(1).

What is amortised analysis?

The amortised analysis gives the average performance of each operation in the worst case. In other words, when chances of worst cases are very low compared to best cases, a traditional worst-case analysis will not give a clear picture of time complexity. In such situations, average-case time complexity analysis will give a better picture.

Critical ideas to think about!

• Can we think to implement a queue using recursion and one additional stack?
• When tempStack is not empty in the second approach, why are we not transferring elements from mainStack to tempStack?
• How does the efficiency of the above approaches depend on the frequency of enqueue and dequeue operations? Which approach should be followed if the frequency of enqueue operation is very high in comparison to the dequeue operation?
• Can we think of solving this problem using some other strategies?
• What type of queue implementation would be perfect for the above implementations? Array implementation or linked list implementation?
• How do we implement front() and isEmpty() operations in all the above approaches? Can we design a strategy to get the front element in O(1) time complexity?

Suggested coding questions to practice

• Implement stack using queues
• Reverse a queue using another queue
• Check if the two given stacks are the same
• 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 the maximum in a stack

Enjoy learning, Enjoy Algorithms!