Build Stack Using Queue

Build Stack Using Queue

Hey Buddy! in the last article I have implemented Queue Using Stack. So in this article, I’m going to discuss how can we build a stack using a queue.

What is the Queue?

A queue is an ordered collection of items where the addition of new items happens at one end, called the “rear,” and the removal of existing items occurs at the other end, commonly called the “front.” As an element enters the queue it starts at the rear and makes its way toward the front, waiting until that time when it is the next element to be removed. So basically queue perform FIFO (First in First Out operation).

Operation performed on Queue?

There are multiple operations performed on queue. Im enlisting it one by one below

  • enqueue(): add an item to the queue.
  • dequeue(): remove rear item from the queue
  • peek(): return rear item
  • isEmpty(): check if queue has items

So before moving forward let’s build a queue first then we will move to build stack using this queue. So I’m attaching my code for the queue below. Its self-explanatory code

class Queue:
    def __init__(self):
        self.queue = [] # initialize and empty array to store items

    def enqueue(self, data):
        self.queue.insert(0, data) # add items to the beggining of an array

    def deque(self):
        if not self.isEmpty(): # check if queue is not empty
            return self.queue.pop() # if its not empty then remove front item from queue
        return None # otherwise return None

    def front(self):
        if not self.isEmpty(): # check if queue is empty
            return self.queue[-1] # if queue is not empty then return very last element i.e. rear element
        return None # otherwise return None

    def isEmpty(self):
        return 0 == len(self.queue) # if array length is 0 then return True else return False

So you will ask where are Stack operations. So I have an answer to your question checkout my last article. How to Build Queue Using Stack.

Now let’s begin with stack implementation. So I will be going to implement it step by step so keep close eye on it.

Step 1:

Initializing Queue

Our very first step will be initializing the queue. So to do that I’m going to take one queue object, size params & one variable to maintain the topmost element.

class StackUsingQueue:
    def __init__(self):
        self.queue1 = Queue()
        self.size = 0
        self.topmost_item = None

Step 2:

Push Operation

Here I’m adding two variables to the push function one is item and another is for either its calling from the pop function or not. If it’s not pop then increment size by one. This function always puts an element to queue and update the topmost variable to the currently pushed item.

    ...

    def push(self, item, pop=False):
        self.queue1.enqueue(item)
        self.topmost_item = item
        if not pop:
            self.size += 1

Stem 3:

Pop Operation

In the pop operation, it performs dequeue operation till size > 2 and simultaneously appends the dequeued element to the queue. So after size - 2 operations the queue front element will be the rear element. So now you can remove that element. So it’s like we are removing the most recent added item from the queue which is basically FIFO of the stack.

    
    ...

    def pop(self):
        tmp = self.size
        while tmp > 2:
            self.push(self.queue1.deque(), True)
            tmp -= 1

        self.topmost_item = self.queue1.front()
        self.push(self.queue1.deque())
        self.size -= 1
        return self.queue1.deque()

Step 4:

Top operation

The top operation is very simple, it’s just returning the toppost_item variable which we were maintaining in the push operation.


    ...

    def top(self):
        return self.topmost_item

Now adding the whole code block at one place

class StackUsingQueue:
    def __init__(self):
        self.queue1 = Queue()
        self.size = 0
        self.topmost_item = None

    def push(self, item, pop=False):
        self.queue1.enqueue(item)
        self.topmost_item = item
        if not pop:
            self.size += 1

    def top(self):
        return self.topmost_item

    def pop(self):
        tmp = self.size
        while tmp > 2:
            self.push(self.queue1.deque(), True)
            tmp -= 1

        self.topmost_item = self.queue1.front()
        self.push(self.queue1.deque())
        self.size -= 1
        return self.queue1.deque()

Driver function to test this code

if __name__ == "__main__":
    q2 = StackUsingQueue()
    q2.push(10)
    q2.push(30)
    q2.push(40)
    q2.push(50)
    print('StackUsingQueue top: {}'.format(q2.top()))
    print(q2.pop())
    q2.push(300)
    print('StackUsingQueue top: {}'.format(q2.top()))
    q2.push(400)
    print(q2.pop())
    print(q2.pop())
    q2.push(600)
    print('StackUsingQueue top: {}'.format(q2.top()))
    print(q2.pop())
    print('StackUsingQueue top: {}'.format(q2.top()))

Output:

StackUsingQueue top: 50
50
StackUsingQueue top: 300
10
40
StackUsingQueue top: 600
30
StackUsingQueue top: 400