Stack and queue in python: We have compiled most frequently asked Python Interview Questions which will help you with different expertise levels.
Python Interview Questions on Stacks, Queues, and Deque
Stack, Queues, and Deque are linear structures in Python.
Stack
Stack is an ordered collection of items where the addition and removal of items take place at the same end which is also known as the TOP. The other end of the stack is known as the BASE. The base of the stack is significant because the items that are closer to the base represent those that have been in the stack, for the longest time.
The most recently added item is the one that is in the top position so that it can bebe removed first.
This principle of order is known as LIFO-that stands for Last -in-first- out, where the newer items are near the top, while older items are near the base.
- Stack Data Structure in Python
- Python Interview Questions and Answers for Freshers & Experienced
- How to use Queue: A beginner’s guide
Stacks are important because they are required whenever there is a need to reverse the order of items as the order of removal is reverse of the order of insertion.
Example:
1. Pushing the back button on the browser while surfing on the internet.
2. Ctrl+Z (undo) in Microsoft applications.
3. Remove recently used objects from the cache.
Stacks are commonly used by software programmers; it may not be quite noticeable while using a program as these operations generally take place in the background. However, many times you may come across a Stack overflow error. This happens when a stack actually runs out of memory.
Stacks seem to be very simple. Yet they are one of the most important data structures as you will see very soon. Stacks serve as a very important element of several data structures and algorithms.
Question 1.
Explain, how would you implement a stack in Python.
Answer:
We will implement Stack using lists.
Step 1:
Define the Stack Class
#Define Stack Class class Stack:
Step 2:
Create constructor
Create a constructor that takes self and size (n) of the stack. In the method, we declare that self. stack is an empty list([ ]) and self. size is equal to n i.e. the size provided.
#Define Stack Class
def__init__(self, n):
self.stack = [ ]
self.size = n
Step 3:
Define Push Function
A push function will have two arguments self and the element that we want to push in the list. In this function, we first check if the length of the stack is equal to the size provided as input (n). If yes, then it means that the stack is full and prints the message that no more elements can be appended as the stack is full. However, if that is not the case then we can call the append method to push the element to the stack.
def push(self,element):
if(len(self.stack)== self.size):
print("no more elements can be appended as the stack is full")
else:
self.stack.append(element)
Step 4:
Define POP Function
Check the stack. If it is empty, then print: Stack is empty. Nothing to POP!!. If it is not empty pop the last item from the stack.
def pop(self):
if self.stack == [ ]:
print("Stack is empty. Nothing to POP!!")
else:
return self.stack.pop( )
The complete code will be as follows:
Code
#Define Stack
Class class Stack:
#declare constructor
def__init__(self, n):
self.stack = [ ]
self.size = n
#push operation
def push(self,element):
if(len(self.stack)== self.size):
print("no more elements can be appended as the stack is full")
else:
self.stack.append(element)
#pop operation
def pop(self):
if self.stack == [ ]:
print("Stack is empty. Nothing to POP!!")
else:
self.stack.pop( )
Execution
s = Stack(3) s.push(6) s.push(2) print(s.stack) s.pop( ) print(s.stack)
Output
[6, 2] [6] >>>
Question 2.
Write a program to check if a given string has a balanced set of parenthesis or not.
Balanced parenthesis: ( ), { }, [ ], {[( )]}, [ ][ ], etc.
Answer:
Here we have to check if pairs of brackets exist in the right format in a string. Expressions such as “[ ]{( )}” are correct. However, if the opening bracket does not find the corresponding closing bracket then the parenthesis is a mismatch. For example: “[ }”or “{ }[ ))”• To solve this problem we will follow the following steps:
Step 1
Define class paranthesis_match
class paranthesis_match:
Step 2
Defining lists for opening and closing brackets
We now define two lists such that the index of an opening bracket matches with the index of the corresponding closing bracket:
1. List opening_brackets will have all types of opening brackets as elements -[“(“,{“,”[“]
2. List closing_brackets will have all types of closing brackets as elements – [“(“,”{“,”[“]
Here is how we define the lists:
opening_brackets = ["(",{","["]
closing_brackets = [")","}"/"]"]
Step 3
Defining Constructor, Push, and Pop functions
Constructor:
The constructor takes an expression as a parameter which is the string provided for validation of parameters.
We also initialize the list for stacking purposes. The push( ) and pop( ) functions will be applied on this list.
def__init__(self, expression): self-expression = expression self.stack = [ ]
Push( ) and Pop( ) Functions
Since we are implementing this using a stack it is quite obvious that we would require push( ) and pop functions.
The push( ) function when called, will add an element to the stack.
def push(self,element): self.stack.append(element)
The pop( ) element on the other hand will pop the last element from the stack.
#pop operation
def pop(self):
if self.stack == [ ]:
print("Unbalanced Paranthesis")
else:
self.stack.pop( )
Step 4
Defining the function to do the analysis
We will now write the code to analyze the string.
In this function we will perform the following steps:
- First, we check the length of the expression. A string of balanced parenthesis will always have even number of characters. So, if the length of the expression is divisible by two only then we would move ahead with the analysis. So, an if.. .else loop forms the outer structure of this function.
if len(self.expression)%2 == 0:
---- we analyse .......... .
else:
print("Unbalanced Paranthesis")
- Now, considering that we have received a length of even number. We can move ahead with analysis and we can write our code in the “if’ block. We will now traverse through the list element by element. If we encounter an opening bracket we will push it onto the stack, if it is not an opening bracket then we check if the element is in the closing bracket list. If yes then we pop the last element from the stack and see if the index of the elements in the opening_brackets and closing_brackets list is of the same bracket. If yes, then there is a match else the list is unbalanced.
if element in self.opening_brackets:
self.push(element)
elif element in self.closing_brackets:
x = self.stack.pop( )
if self.opening_brackets.index(x)== self.
closing_brackets.index(element):
print("Match Found")
else:
print("Match not found -check prarnthesis")
return;
- So, the final code will be as follows, to make things easier for the end user, print commands have been added:
class paranthesis_match:
opening_brackets = ["(","{","["]
closing_orackets = [")","}","]"}
#declare constructor
def__init__(self, expression):
self-expression = expression
self.stack = [ ]
#push operation
def push(self,element):
self.stack.append(element)
#pop operation
def pop(self):
if self.stack == [ ]:
print ("Unbalanced Paranthesis")
else:
self.stack.pop( )
def is_match(self):
print ("expression is = ", self.expression)
if len (self.expression)%2 == 0:
for element in self-expression:
print("evaluating ", element)
if element in self.opening_brackets:
print("it is an opening bracket - ", element, "pushing to stack")
self.push(element)
print("pushed", element, " on to stack the stack is ", self.stack)
elif element in self. closing_brackets:
x = self.stack.pop( )
print("time to pop element is ", x)
if self.opening_brackets.
index(x)== self.closing_brackets.index(element):
print("Match Found")
else:
print("Match not found - check prarnthesis")
return;
else :
print("Unbalanced Paranthesis")
Execution
pm = paranthesis match("( [{ }])")
pm.is_match( )
Output
expression is = ([{ }])
evaluating (
it is an opening bracket - ( pushing to stack pushed ( on evaluating to stack the [ stack is [ ' ( ' ]
evaluating [
it is an opening bracket - [ pushing to stack pushed [ on to stack the stack is [ ' ( ' , ' [ ']
evaluating {
it is an opening bracket - { pushing to stack pushed { on to stack the stack is [ ' ( ' , ' ] ' , ' { ' ]
evaluating }
time to pop element is {
Match Found
evaluating ]
time to pop element is [
Match Found
evaluating )
time to pop element is (
Match Found
Queue
A queue is a sequence of objects where elements are added from one end and removed from the other. The queues follow the principle of first in first out. The removal of items is done from one end called the Front and the items are removed from another end that’s referred to as the rear. So, just as in the case of any queue in real life, the items enter the queue from the rear and start moving towards the front as the items are removed one by one.
So, in Queue the item at the front is the one that has been in the sequence for the longest and the most recently added item must wait at the end. The insert and delete operations are also called en queue and de queue.
Basic Queue functions are as follows:
- enqueue(i): Add element “i” to the queue.
- dequeue( ): Removes the first element from the queue and returns its value.
- isEmpty( ): Boolean function that returns “true” if the queue is empty else it will return false.
- size( ): Returns length of the queue.
Question 3.
Write a code for implementation of Queue.
Answer:
The implementation of the queue is as follows: Step1
Define the class
class Queue:
Step 2
Define the constructor
Here, we initialize an empty list queue:
def__init__(self): self.queue =[ ]
Step 3
Define isEmpty( ) function
As the name suggests, this method is called to check if the queue is empty or not. The function check the queue. If it is empty, it prints a message – Queue is Empty or else it will print a message – Queue is not Empty
def isEmpty(self):
if self.queue ==[ ]:
print("Queue is Empty")
else:
print("Queue is not Empty")
Step 4
Define enqueue( ) function
This function takes an element as parameter and inserts it at index “0”. All elements in the queue shift by one position.
def enqueue(self,element):
self.queue.insert(0, element)
Step 5
Define dequeue( ) function
This function pops the oldest element from the queue.
def dequeue(self): self.queue.pop( )
Step 6
Define size ( ) function
This function returns the length of the queue.
def size (self) :
print ("size of queue is",len(self.queue))
Code
class Queue:
def__init__(self):
self.queue =[ ]
def isEmpty(self):
if self.queue ==[ ]:
print ("Queue is Empty")
else :
print("Queue is not empty")
def enqueue(self,element):
self.queue.insert(0,element)
def dequeue(self) :
self.queue.pop( )
def size(self):
print("size of queue is",len(self.queue))
Code Execution
q = Queue ( )
q.isEmpty( )
print("inserting element no.1")
q.enqueue("apple")
print("inserting element no.2")
q.enqueue("banana")
print("inserting element no.3")
q.enqueue("orange")
print("The queue elements are as follows:")
print(q.queue)
print("check if queue is empty?")
q.isEmpty()
print ("remove first element")
q.dequeue()
print("what is the size of the queue?")
q.size ()
print("print contents of the queue")
print(q.queue)
Output
Queue is Empty inserting element no.1 inserting element no.2 inserting element no.3 The queue elements are as follows: ['orange', 'banana', 'apple'] check if queue is empty? Queue is not empty remove first element what is the size of the queue? size of queue is 2 print contents of the queue ['orange', 'banana']
Question 4.
Write a code to implement a stack using a single queue. What is the time complexity for pushful and pop( ) functions?
Answer:
Before implementing the code it is important to understand the logic behind it. The question demands that you make a queue work like a stack. A queue works on the principle of First-In-First-Out whereas a stack works on the principle of Last In First Out.
Code
class Stack from Queue:
def__init__(self):
self.queue =[ ]
def isEmpty(self):
if self.queue ==[ ]:
print("Queue is Empty")
else :
print("Queue is not empty")
def enqueue(self,element):
self.queue.insert(0,element)
def dequeue(self):
return self.queue.pop( )
def size(self):
print("size of queue is ",len(self.queue))
def pop(self):
for i in range(len(seif.queue)-1):
x = self.dequeue( )
print(x)
self.enqueue(x)
print("element removed is",self.dequeue( ))
Execution -1
sq = Stack_from_Queue( )
sq.isEmpty( )
print("inserting element apple")
sq.enqueue("apple")
print("inserting element banana")
sq.enqueue("banana")
print("inserting element orange")
sq.enqueue("orange" )
print("inserting element 0")
sq.enqueue("0")
print("The queue elements are as follows:")
print (sq. queue)
print ("check if queue is empty?")
sq.isEmpty( )
print("remove the last in element")
sq.pop( )
print(sq.queue)
Output -1
Queue is Empty inserting element apple inserting element banana inserting element orange inserting element 0 The queue elements are as follows: ['O', 'orange', 'banana', 'apple'] check if queue is empty? Queue is not empty remove the last in element apple banana orange element removed is 0 ['orange', 'banana', 'apple']
Execution – II
sq = Stack_from_Queue ( )
sq.isEmpty ( )
print("inserting element apple")
sq.enqueue("apple")
print("inserting element banana")
sq.enqueue("banana")
print("inserting element orange")
sq.enqueue("orange")
print("inserting element 0")
sq.enqueue("0")
for i in range(len(sq.queue)):
print("The queue elements are as follows:")
print(sq.queue)
print("check if queue is empty?")
sq.isEmpty()
print("remove the last in element")
print(sq.queue)
Output -II
Queue is Empty inserting element apple inserting element banana inserting element orange inserting element 0 The queue elements are as follows: ['O', 'orange', 'banana', 'apple'] check if queue is empty? Queue is not empty remove the last in element apple banana orange element removed is 0 ['orange', 'banana', 'apple'] The queue elements are as follows: ['orange', 'banana', 'apple'] check if queue is empty? Queue is not empty remove the last in element apple banana element removed is orange [ 'banana', 'apple'] The queue elements are as follows: [ 'banana', 'apple'] check if queue is empty? Queue is not empty remove the last in element apple element removed is banana ['apple'] The queue elements are as follows: ['apple'] check if queue is empty? Queue is not empty remove the last in element element removed is apple [ ] >>>
Time complexity for push( ) and pop( ) function is O(1)
Time complexity for push is O(1).
Time complexity for pop is O(n) because we have to iterate through the
loop and rearrange elements before retrieving the element.
Question 5.
How can a queue be implemented using two stacks?
Answer:
Step 1:
Create a basic Stack( ) class with push( ), pop( ), and isEmpty( ) functions.
class Stack:
def__init__(self) :
self.stack = [ ]
def push(self,element):
self.stack.append(element)
def pop(self):
return self.stack.pop( )
def isEmpty(self):
return self.stack == [ ]
Step 2:
Define the Queue class
class Queue:
Step 3:
Define the constructor
Since the requirement here is of two stacks, we initialize two stack objects.
def__init__(self) : self.inputStack = Stack( ) self.outputStack = Stack( )
Step 4:
Define the enqueue function
This function will push the elements into the first stack.
def enqueue(self,element): self.inputStack.push(element)
Step 5:
Define the dequeue( ) function
This function checks if the output stack is empty or not. If it is empty then elements will be popped out from the input stack one by one and pushed into the output stack, so that the last element is the first one to be out. However, if the output stack is not empty, then the elements can be popped directly from it.
Now suppose we insert 4 values: 1,2,3,4 calling the en queue function. Then the input stack would be like this:
When we call the dequeue function, the elements from the input stack are popped and pushed one by one onto the output stack till we reach the last element and that last element is popped from the input stack and returned. If the output stack is not empty then it means that it already has elements in the right order and they can be popped in that order.
def dequeue(self):
#if not self.inputStack.isEmpty( ):
if self.outputStack.isEmpty( ):
for i in range(len(self.inputStack.
stack)-1):
x = self.inputStack.pop( )
self.outputStack.push(x)
print("popping out value =", self. inputStack.pop( ))
else:
print("popping out value =", self.
outputStack.pop( ))
Code
class Queue:
def__init__(self):
self . inputStack = Stack( )
self . outputStack = Stack( )
def enqueue(self,element):
self.inputStack.push(element)
def dequeue(self):
if self.outputStack.isEmpty( ):
for i in range(len(self.inputStack.stack)-1):
x = self.inputStack.pop( )
self.outputStack.push(x)
print("popping out value , self. inputStack.pop( ))
else:
print("popping out value =", self.
outputStack.pop( ))
#Define Stack Class
class Stack:
def__init__(self):
self.stack = [ ]
def push(self,element):
self.stack.append(element)
def pop(self):
return self.stack.pop( )
def isEmpty(self):
return self.stack == [ ]
Execution
Q = Queue( )
print("insert value 1")
Q.enqueue(1)
print("insert value 2")
Q.enqueue(2)
print("insert value 3")
Q.enqueue(3)
print("insert value 4")
Q.enqueue(4)
print("dequeue operation")
Q.dequeue( )
Q.dequeue( )
print("insert value 1")
Q.enqueue(7)
Q.enqueue(8)
Q.dequeue( )
Q.dequeue( )
Q.dequeue( )
Q.dequeue( )
Output
Q = Queue( )
print("insert value 1")
Q.enqueue(1)
print ("insert value 2")
Q.enqueue(2)
print ("insert value 3")
Q.enqueue(3)
print("insert valu? 4")
Q.enqueue(4)
print("dequeue operation")
Q.dequeue()
Q.dequeue()
print("insert value 1")
Q.enqueue(7)
Q.enqueue(8)
Q.dequeue( )
Q.dequeue( )
Q.dequeue( )
Q.dequeue( )
Deques
A deque is more like a queue only that it is double-ended. It has items positioned in the ordered collection and has two ends, the front, and the rear. A deque is more flexible in nature in the sense that the elements can be added or removed from the front or rear. So you get the qualities of both stack and queue in this one linear data structure.
Question:
Write a code to implement a deque.
Answer.
Implementation of the deque is easy. If you have to add an element from the rear, you will have to add it at index 0 the same way if you have to add it from the front, call the append( ) function. Similarly, if you have to remove the front call pop( ) function and if you want to pop it from the rear call pop(o).
Code
class Deque:
def__init__(self):
self.deque =[ ]
def addFront(self,element):
self.deque.append(element)
print("After adding from front the deque value is : ", self.deque)
def addRear(self,element):
self.deque.insert(0,element)
print("After adding from end the deque value is : ", self.deque)
def removeFront(self):
self.deque.pop( )
print("After removing from the front the deque value is : ", self.deque)
def removeRear(self):
self.deque.pop(0)
print("After removing from the end the deque value is : ", self.deque)
Execution
D = Deque()
print("Adding from front")
D.addFront(1)
print("Adding from front")
D.addFront(2)
print("Adding from Rear")
D.addRear(3)
print("Adding from Rear")
D.addRear(4)
print("Removing from Front")
D.removeFront()
print("Removing from Rear")
D.removeRear( )
Output
After adding from front the deque value is : [1] After adding from the front the deque value is : [1, 2] After adding from the end the deque value is : [3, 1,2] After adding from the end the deque value is : [4, 3,1, 2] After removing from the front the deque value is : [4, 3, 1] After removing from the end the deque value is : [3, 1] >>>