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.
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).
There are multiple operations performed on queue. Im enlisting it one by one below
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:
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:
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:
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:
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