Build Queue Using Stack

Hey buddy! In this article, I’m going to explain to you one of the most favorite questions asked by the interviewer. how can you build Queue using Stack?

What is Stack?

Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

Operation performed on Stack?

To build Queue using stack we will have to build Stack first right? :) So let’s do that. Below is the simple stack implementation and you will see the following operations performed in the stack

• push: It will add items to the top of the stack
• pop: It will remove the topmost item from the stack
• top: It will return the topmost item from the stack
• isEmpty: It will check either stack is empty or not

Here is the code for all the operations mentioned above.

class Stack:
    def __init__(self):
        self.stack = [] # take empty list

    def push(self, data):
        self.stack.append(data) # push element to the stack

    def pop(self):
        if not self.isEmpty():
            return self.stack.pop() # if stack is not empty then remove last pushed element
        return None

    def top(self):
        if not self.isEmpty():
            return self.stack[-1] # return last element
        return None

    def isEmpty(self):
        return 0 == len(self.stack) # if list length is 0 then return true

So as you can see our stack is ready. Now let’s implement Queue Using Stack. Here are our Queue API details

class QueueUsingTwoStack:

    def enqueue(self, data):
        ...

    def deque(self):
        ...

    def front(self):
        ...

    def isEmpty(self):
        ...
        

So to build queue using stack we have to use two stack. One stack to perform enqueue operation and another stack to perform front & deque operation. Now initialize both stack as follows

class QueueUsingTwoStack:
    def __init__(self):
        self.stack1 = Stack() # create new stack obj
        self.stack2 = Stack()

Now for enqueue operation, push elements only in the first stack

class QueueUsingTwoStack:

    ... 

    def enqueue(self, data):
        self.stack1.push(data)

To implement the front operation, we are going to use one trick, first check either stack2 is empty or not and if it’s empty then move everything from the stack1 to stack2 so by doing that we will be having items in reversed order of stack1 & that’s we want. Now our stack2 top element will be the very first element that we entered. Or if stack2 is not empty then return stack2 top element.

class QueueUsingTwoStack:

    ... 

    def front(self):
        if self.stack2.isEmpty():
            while not self.stack1.isEmpty():
                self.stack2.push(self.stack1.pop())
            return self.stack2.top()
        return self.stack2.top()

To perform deque operation first perform front operation to make sure we are having very first enqued element in the stack2. Now simply remove stack2 top element

class QueueUsingTwoStack:

    ... 
    def deque(self):
        self.front()
        return self.stack2.pop()

and lastly, perform **isEmplty operation to check either queue is empty or not. So, in this case, we will have to check isEmpty for both stacks if both stacks are empty then only we can be sure that the queue is empty.

class QueueUsingTwoStack:

    ... 

    def isEmpty(self):
        return self.stack1.isEmpty() and self.stack2.isEmpty()

Here is the final code for QueueUsingTwoStack

class QueueUsingTwoStack:
    def __init__(self):
        self.stack1 = Stack()
        self.stack2 = Stack()

    def enqueue(self, data):
        self.stack1.push(data)

    def front(self):
        if self.stack2.isEmpty():
            while not self.stack1.isEmpty():
                self.stack2.push(self.stack1.pop())
            return self.stack2.top()
        return self.stack2.top()

    def deque(self):
        self.front()
        return self.stack2.pop()

    def isEmpty(self):
        return self.stack1.isEmpty() and self.stack2.isEmpty()

Now let’s write driver class to test our code

if __name__ == "__main__":
    q2 = QueueUsingTwoStack()
    q2.enqueue(10)
    q2.enqueue(30)
    q2.enqueue(40)
    q2.enqueue(50)
    print('QueueUsingTwoStack front: {}'.format(q2.front()))
    q2.deque()
    q2.enqueue(300)
    print('QueueUsingTwoStack front: {}'.format(q2.front()))
    q2.enqueue(400)
    q2.deque()
    q2.deque()
    q2.enqueue(600)
    print('QueueUsingTwoStack front: {}'.format(q2.front()))
    q2.deque()
    print('QueueUsingTwoStack front: {}'.format(q2.front()))

Output:

QueueUsingTwoStack front: 10
QueueUsingTwoStack front: 30
QueueUsingTwoStack front: 50
QueueUsingTwoStack front: 300

Let me know your thoughts. Thanks for reading.