Queue Data Structure is commonly used in any operation that requires tasks to be executed in order of their arrival or priority. Queues in Python can be implemented using Python List and Built-in Class. A user defined class can also be created to understand and implement working of Queues in Python.
Queue is a linearly connected collection of elements of same kind. A queue works on the technique of FIFO(First-In First-Out). In its simplest implementation, deletion of elements is done at one end called Front. The operation of deletion is also called dequeue. Insertion of elements is done at other end called Rear. The operation of insertion is also called enqueue. A queue implementation does not allow insertion or deletion operations at any other location than these two.
The concept of Queues can be understood by these real-life examples
The print commands sent to a printer are an implementation of a Queue data structure. The print commands of documents are stored in printer’s buffer in form of a queue. The documents submitted earlier will be printed first and ones that are sent to printer later will be printed later.
When you order online for food , your order is queued up at the vendor’s computer / device. It will be prepared and delivered in the order of arrival of food orders.
If you book a cab for a trip to your nearby museum, you have to wait for a few moments before you get a confirmation signal. Your request for cab is queued up. As soon a cab is available, it is passed on your request and then you can track the location of the cab.
Performance of a Queue
The algorithmic complexity of queue as a data structure can be easily understood by its two operations enqueue(Insertion) and dequeue(Deletion)
Insertion always takes place at one end called the Rear. Unlike arrays or linked list, no movement of elements is involved. No iteration is required to move elements downward to create place for new element. The complexity is O(1).
Same is the case with deletion. It is always done at Front. Again no need to shift elements after an element is deleted. All you need to do is update Front with next element’s address or index. The complexity for deletion is again O(1).
Queues in Python using Built-in List and Queue Class
Using Built-in List
Python offers built-in list data type to manage a collection of similar elements. It can be used to implement a queue with a few elements or when program execution speed is not a big issue. Python Append() and Pop() list functions can be used to add elements at Rear and delete elements at Front. It is same as we did in Stacks. Here Pop is called with an argument value 0 so that the front element is popped out instead of the latest one.
It is not a preferred way of implementing Queues in Python because pop function ends up in shifting elements upwards after a deletion. It slows down the program if a large number of elements are in the queue.
# program to implement List as a queue using Append and Pop fucntions pyQueue= option='Y' while (option=='Y' or option=='y'): #reading from user the option to insert of delete an element deen=int(input("Enter 1 for Insert(Enqueue) and 2 for Delete(Dequeue)")) if (deen==1): value=input("Enter the value to be added in the Queue") pyQueue.append(value) elif (deen==2): print("The deleted value is",pyQueue.pop(0)) else: print("Wrong option") continue option=str(input("do you want to do more operations(Y/N)")) #printing remaining queue elements after deletions and insertions print("Queue is ",pyQueue)
Using Python Queue Class
Python has built-in Queue class that implements multiple methods and properties to use in programs. Insertion is done with put(value) method by passing value to be inserted. Deletion is done with get() method.
This class is available in queue module. This module contains a variety of other queues classes like Multiprocessing, Multiple producers and multiple consumers etc. Read about this module from Official Python Website.
# program to undersand Built-in queue class from queue import Queue Qobject=Queue() option='Y' while (option=='Y' or option=='y'): #reading from user the option to insert of delete an element deen=int(input("Enter 1 for Insert(Enqueue) and 2 for Delete(Dequeue)")) if (deen==1): value=input("Enter the value to be added in the Queue") Qobject.put(value) elif (deen==2): #calling queue get function in print fucntion to display the deleted element print("The deleted value is",Qobject.get()) else: print("Wrong option") continue option=str(input("do you want to do more operations(Y/N)")) #printing remaining queue elements after deletions and insertions print("Queue is ",Qobject.queue)
Self defined Queue Class
The last one is self-defined class based example to implement Queues in Python. Here a Node Class is defined to create Queue elements. A ClassQueue class is defined with queue data members Front, Rear and Nodecount (to keep count of queue elements). Methods enqueue and dequeue are defined for insertion and deletion operations respectively. PrintData method prints the elements of the queue.
#user defined class for nodes class Node: def __init__(self, data=None, link=None): self.data=data self.link=link def __str__(self): return str(self.data) #user defined class for Queue class ClassQueue: #constructor for Queue Class def __init__(self, front=None,rear=None,nodecount=0): self.front=front self.rear=rear self.nodecount=nodecount #stores number of nodes in queue def enqueue(self, value=None):#add new elements to queue node=Node(value) if self.front==None: #if queue is empty node.link=None self.front=node self.rear=node else: self.rear.link=node self.rear=node self.nodecount=self.nodecount+1 def dequeue(self):#delete elements item=self.front.data self.front=self.front.link self.nodecount=self.nodecount-1 #Update count of queue elements return item def printData(self):#traverse and display queue elements ptr=self.front while ptr: print(ptr) ptr=ptr.link print() #Create blank Queue que=ClassQueue() numele= input('How many elements to be added in the queue??') #add a few elements to initialise queue for cnt in range(int(numele)): ele= input('Enter a value for queue ') que.enqueue(ele) cnt=cnt+1 #Print Queue before pushing of popping elements print("Queue Initially") que.printData() #As user whether to insert or delete an element. option='Y' while (option=='Y' or option=='y'): deem=int(input("Enter 1 for Insertion and 2 for Deletion")) if (deem==1): #calling class enqueue method to insert an element. value=input("Enter the value to be Added") que.enqueue(value) elif (deem==2): #calling class dequeue method to delete an element. print("The popped value is",que.dequeue()) else: print("Wrong option") continue option=str(input("do you want to do more operations(Y/N)??")) #Print Queue again after operations print("Queue Finally") que.printData()