Queues in Python

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.

Example

# 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.

Example

# 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.

Code

#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()

admin