Queue Data Structure Implementation Using Python
Last updated: September 13, 2024 By Sunil Shaw
A queue is a sequence of objects where you add elements from one end and remove them from the other end. The queues follow the principle of first in first out`. One end, called the Front, removes the items, and the other end, referred to as the Rear, also removes the items. So, just as in 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. Let’s see queue data structure implementation using Python
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 enqueue and dequeue.
Basic Queue Functions
Basic Queue functions are as follows:
- enqueue(i): Add element “i” to the queue.
- dequeue(): Removes the first elements from the queue and return its value.
- isEmpty(): Boolean function that returns “true” if the queue is empty else it will return false.
- size(): Returns length of the queue.
Implementation of Queue
Let’s write a program for implementation of queue.
Step 1: Define the class
class Queue:Step 2: Define the constructor
Here, we initialize an empty list queue:
def __init__(self):
self.queue = []Here, we initialize an empty list queue:
Step 3: Define isEmpty() function
As the name suggets, this method is called to check if the queue is empty or not. TheisEmpty() function checks the queue. If it is empty, it prints a message – Basically 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 the enqueue() function
Without a doubt this function takes an element as parameter and inserts it at index “0”. Therefore all elements in the queue shift by one position.
def enqueue(self,element):
self.queue.insert(0, element)Step 5: Define the equeue() function
In summary this function pops the oldest element from the queue.
def dequeue(self):
self.queue.pop()Step 6: Define the size() function
This function returns the length of the queue.
def size(self):
print("size of queue is", len(self.queue))Step 7: Write down the commands to execute the code
Code Execution
# Driver Code
q = Queue()
q.isEmpty()
# inserting elements
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()
# removing elements
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)Full 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))
# Driver Code
q = Queue()
q.isEmpty()
# inserting elements
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()
# removing elements
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']
[Finished in 14ms]Implementation of a Stack Using Single Queue
Before implementing the code, it is important to understand the logic behind it. In a word 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.
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(self.queue)-1):
x = self.dequeue()
print(x)
self.enqueue(x)
print("element removed is", self.dequeue())Execution – I
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()
sq.pop()
sq.pop()
sq.pop()
sq.isEmpty()Output – I
Queue is Empty
inserting element apple
inserting element banana
inserting element orange
inserting element 0
The queue elements are as follows:
['0', 'orange', 'banana', 'apple']
check if queue is empty?
Queue is not empty
remove the last in element
apple
banana
orange
element removed is 0
apple
banana
element removed is orange
apple
element removed is banana
element removed is apple
Queue is Empty
[Finished in 15ms]Execution – II
Queue is Empty
inserting element apple
inserting element banana
inserting element orange
inserting element 0
The queue elements are as follows:
['0', 'orange', 'banana', 'apple']
apple
banana
orange
element removed is 0
check if queue is empty?
Queue is not empty
remove the last in element
['orange', 'banana', 'apple']
The queue elements are as follows:
['orange', 'banana', 'apple']
apple
banana
element removed is orange
check if queue is empty?
Queue is not empty
remove the last in element
['banana', 'apple']
The queue elements are as follows:
['banana', 'apple']
apple
element removed is banana
check if queue is empty?
Queue is not empty
remove the last in element
['apple']
The queue elements are as follows:
['apple']
element removed is apple
check if queue is empty?
Queue is Empty
remove the last in element
[]
[Finished in 13ms]Implementation of a Queue Using Two Stacks
Let’s see how to implement a queue using two stacks.
Step 1:
Firstly 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 check wheather the output stack is empty. If it is empty, then elements will be popped out from inputStack one by one and pushed into the outputStack, so that the last in element is the first 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 enqueue function. Then, the input stack would be like this.
Overall when we call a dequeue function, the elements from inputStack are popped and pushed one by one on to the output stack till we reach the last element and that last element is poppedfrom the inputStack 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 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("poping out value =", self.outputStack.pop())Full 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("poping 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 7")
Q.enqueue(7)
Q.enqueue(8)
Q.dequeue()
Q.dequeue()
Q.dequeue()
Q.dequeue()Output
insert value 1
insert value 2
insert value 3
insert value 4
dequeue operation
popping out value = 1
poping out value = 2
insert value 7
poping out value = 3
poping out value = 4
popping out value = 7
poping out value = 8
[Finished in 18ms]Deque
A deque is more like a queue only that it is double ended. It has items positioned in ordered collection and has two ends, the front and the rear. In a word a deque is more flexible in nature, in the sense that the elements can be added or removed from front or rear. So, you get qualities of both stack and queue in this one linear data structure.
Write a code to implement a deque
Undoubtedly implementation of deque is easy. If you have to add an element from rear, you will have to add it at index 0 same way. Therefore you have to add it from the front, call the append() function. Similarly, if you have to remove from front, call the pop() function and if you want to pop it from the rear, call pop(0).
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 front the deque value is :", self.deque)
def removeRear(self):
self.deque.pop(0)
print("After removing from end the deque value is :", self.deque)Driver Code
d = Deque()
print("Adding from front")
d.addFront(1)
print("Adding from front")
d.addFront(2)
print("Adding from Rear")
d.addFront(3)
print("Adding from Rear")
d.addFront(4)
print("Removing from Front")
d.removeFront()
print("Removing from Rear")
d.removeRear()Output
Adding from front
After adding from front the deque value is : [1]
Adding from front
After adding from front the deque value is : [1, 2]
Adding from Rear
After adding from front the deque value is : [1, 2, 3]
Adding from Rear
After adding from front the deque value is : [1, 2, 3, 4]
Removing from Front
After removing from front the deque value is : [1, 2, 3]
Removing from Rear
After removing from end the deque value is : [2, 3]
[Finished in 13ms]Stack Data Structure Implementation Using Python
Conclusions
You have learned Queue Data Structure Implementation Using Python. I hope you enjoyed in this articles.
About Author
I am a Web Developer, Love to write code and explain in brief. I Worked on several projects and completed in no time.
View all posts by Sunil Shaw
