Queue in Python

Posted in /  

Queue in Python
vinaykhatri

Vinay Khatri
Last updated on October 10, 2024

    A Python queue is a Linear Data Structure that stores data values in sequential order. The Python queue works on the principle of First in First Out (FIFO), where the data value inserted first in the queue will be pulled out first. The working system of the queue is similar to the First come first served. The Queue data structure consists of two ends Front and Rear. The Data Elements entered from the Rear end of the queue and pull out from the Front end. Here in this Python tutorial, we will walk you through the different techniques to implement a queue in Python.

    How does the Python Queue Work?

    The concept of queue Data Structure is borrowed from the real-world example of a queue of people. The queue data structure can be compared with a queue of people trying to buy tickets from a ticket counter. The Person who reached first to the ticket counter will get the ticket first, the second will get second, followed by the other people standing in the queue.

    Python Queue

    The Python Queue comprise of Two ends

    • Rear
    • Front

    The Rear end is the point from where the data is inserted. The Front end represents the point from where the data is removed. You can say the Front end is the ticket counter and the people are joining the queue from the Rear end.

    Python Queue Operations

    Like other Data structures, there are some specific operations associated with the Queue.

    • Enqueue: Inserting or adding a data value in a queue is known as Enqueue. the Data always inserted from the Rear end of the queue. The time complexity of enqueue operation is O(1).
    • Dequeue: Removing or deleting the item or element from the queue is known as Dequeue. The element can only be removed from the front end of the queue. And the time complexity of Dequeue operation is O(1)

    How to Implement Queue in Python

    There are various techniques to implement a queue data structure in Python. And to make it simpler Python comes with some in-built standard modules for the queue data structure. Here in this Python tutorial, we will learn 4 different techniques to implement a queue in Python.

    • Using List
    • Using Class and List
    • Using collections.deque
    • Using queue.Queue

    Implement a Queue using Python List

    With the help of Python list, we can implement a static queue data structure. We will treat the list object as a queue and use append() and pop() method as enqueue() and dequeue() operation. Using the append() method we will insert the element from the Rear end and using the pop() method remove the element from the Front end. Python lists are not efficient to build a queue data structure, because deleting or inserting an element at the beginning shift all the other elements that take time complexity of O(n).

    Python Program to build Queue using List

    #initializing a queue variable
    queue = []
    
    #Add element to queue from rear side Enqueue
    queue.append(36)
    queue.append(69)
    queue.append(40)
    queue.append(20)
    queue.append(10)
    queue.append(7)
    queue.append(9)
    
    print("The Initial queue is: ", queue)
    
    #dequeue, or removing element from the queue
    print("removed element:",queue.pop(0))
    print("removed element:",queue.pop(0))
    print("removed element:",queue.pop(0))
    print("removed element:",queue.pop(0))
    
    print("The queue after removing 4 elements", queue)

    Output

    The Initial queue is:  [36, 69, 40, 20, 10, 7, 9]
    removed element: 36
    removed element: 69
    removed element: 40
    removed element: 20
    The queue after removing 4 elements [10, 7, 9]

    Implement a Queue using Python class and List

    Using the Python class we can build a custom queue data structure with enqueue() and dequeue() methods. Similar to the concept of a list queue, we will be using the list as a basic data structure to implement the queue.

    Python program to build a queue using class and list.

    class Queue:
        def __init__(self):
            self.queue = []
    
        def enqueue(self,data):
            #inserting data at the end
            self.queue.append(data)
    
        def dequeue(self):
            if len(self.queue) >0:
                return self.queue.pop(0)
            else:
                return "Queue is empty"
    
        def __str__(self):
            return f"{self.queue}"
    
    queue = Queue()
    
    #inserting elements
    queue.enqueue(36)
    queue.enqueue(69)
    queue.enqueue(40)
    queue.enqueue(20)
    queue.enqueue(10)
    queue.enqueue(9)
    queue.enqueue(7)
    
    print("Initial Queue:", queue)
    
    #removing elements
    print("removed element:",queue.dequeue())
    print("removed element:",queue.dequeue())
    print("removed element:",queue.dequeue())
    print("removed element:",queue.dequeue())
    
    print("The queue after removing 4 elements", queue)

    Output

    Initial Queue: [36, 69, 40, 20, 10, 9, 7]
    removed element: 36
    removed element: 69
    removed element: 40
    removed element: 20
    The queue after removing 4 elements [10, 9, 7]

    Implement Python Queue using collection.deque the module

    Python has a standard module collections, that comes with a deque() class. The deque() class of collections module can also be used to implement the queue data structure. The collections deque() is more efficient than Python list, because it provides the time complexity of O(1) for enqueue() and dequeue() operations. Similar to the Python list’s append() and pop() methods, deque() support append() ad popleft() methods to insert and remove elements.

    Python Program to implement queue using collections.deque()

    from collections import deque
    #initializing a deque object
    queue = deque()
    
    #Add element to queue from rear side Enqueue
    queue.append(36)
    queue.append(69)
    queue.append(40)
    queue.append(20)
    queue.append(10)
    queue.append(7)
    queue.append(9)
    
    print("The Initial queue is: ", queue)
    
    #dequeue, or removing element from the queue
    print("removed element:",queue.popleft())
    print("removed element:",queue.popleft())
    print("removed element:",queue.popleft())
    print("removed element:",queue.popleft())
    
    print("The queue after removing 4 elements", queue)

    Output

    The Initial queue is:  deque([36, 69, 40, 20, 10, 7, 9])
    removed element: 36
    removed element: 69
    removed element: 40
    removed element: 20
    The queue after removing 4 elements deque([10, 7, 9])

    Implement Python Queue using queue module

    Python also supports an in-built queue module, that provides an alternative and easy way to implement a Python queue data structure. The Python queue module provides the Queue(maxsize) class to define a queue data structure. The maxsize represents the total length or size of the queue data structure. If the maxsize value equal to 0 or less than 0, the queue size will be infinity. If the maxsize is greater than 0 then only the specified number of elements or data values could be inserted in the queue data structure. The queue module Queue class follow the FIFO principle and support many inbuilt methods.

    Queue methods Description
    empty() Return a boolean value True if the queue is empty else return False
    full() Return a boolean value True if the queue is full else return False
    get() Remove the element from front and return it.
    put(data) It put the data into the queue.
    qsize() return the total number of data elements present in the queue.

    Python Program to implement queue using queue.Queue()

    from queue import Queue
    
    #initializing a queue with size 20
    queue = Queue(maxsize=20)
    
    #Add element to queue from rear side Enqueue
    queue.put(36)
    queue.put(69)
    queue.put(40)
    queue.put(20)
    queue.put(10)
    queue.put(7)
    queue.put(9)
    
    #dequeue, or removing element from the queue
    print("removed element:",queue.get())
    print("removed element:",queue.get())
    print("removed element:",queue.get())
    print("removed element:",queue.get())

    Output

    removed element: 36
    removed element: 69
    removed element: 40
    removed element: 20

    Conclusion

    In this Python tutorial, you learned how to implement queue Data structure in Python . Python list provides the simplest and straightforward way to initialize a queue-like data structure. And with Python class, we can define custom methods for enqueue and dequeue operation. As compared to the Python list collections.deque() and queue.Queue() classes are fast and efficient. To solve real-world problems and multi-threading programs you will be using the queue.Queue() method to implement an algorithm.

    People are also reading:

    Leave a Comment on this Post

    0 Comments