Queue in Python – Analytics Vidhya

Introduction

Imagine you are standing in front of a supermarket waiting for your turn to buy concert tickets of your favourite artist. All go to the line formation and move from the line at the front of it. Computer scientists call this orderliness a queue, which follows the First In, First Out (FIFO) policy. Programmers find queues as useful as other Python data structures and use them to manage tasks, process asynchronous data, and perform many other functions. In this article we will focuses on using queues in Python, the general overview of the queues, and the importance of queues.

Learning Outcomes

• Understand what a queue is and its importance in programming.
• Learn different ways to implement queues in Python.
• ExploExplore various operations you can perform on queues.
• Discover practical applications of queues.
• Gain insights into advanced queue types and their use cases.

What is a Queue?

A queue is a linear data structure that follows the First In First Out (FIFO) principle. It operates by inserting data at the rear end and deleting data from the front end. This process ensures that the queue removes the first inserted element first, adhering to the FIFO principle.

Operations on Queues

Here are the operations that are typically associated with a queue.

• Enqueue: This operation adds an item to the end of the queue. If the queue is full, it results in an overflow condition. The time complexity for this operation is (O(1)).
• Dequeue: This operation removes an item from the front of the queue. Items follow the FIFO principle and are removed in the same order they were added. If the queue is empty, it results in an underflow condition. The time complexity for this operation is (O(1)).
• Peek or Front: This operation retrieves the item at the front of the queue without removing it. The time complexity for this operation is (O(1)).
• Rear or Back: This operation retrieves the item at the end of the queue. The time complexity for this operation is (O(1)).
• IsEmpty: Checking if the queue is empty. Time complexity: O(1) – Constant time operation.
• IsFull: Checking if the queue is full (if implemented with a fixed size). Time complexity: O(1) – Constant time operation.
• Size: Returns the number of elements in the queue. Time complexity: O(1) – Constant time operation in most implementations.

Implementing Queues in Python

There are several ways to implement queues in Python:

Using Lists

Python lists can be used to implement a queue. However, using lists for queues is not efficient for large datasets because removing elements from the front of a list is an O(n) operation.

class ListQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)
        print(f"Enqueued: {item}")

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Dequeue from an empty queue")
        item = self.queue.pop(0)
        print(f"Dequeued: {item}")
        return item

    def peek(self):
        if self.is_empty():
            raise IndexError("Peek from an empty queue")
        print(f"Peek: {self.queue[0]}")
        return self.queue[0]

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        print(f"Size: {len(self.queue)}")
        return len(self.queue)

    def clear(self):
        self.queue = []
        print("Queue cleared")

# Example usage
lq = ListQueue()
lq.enqueue(1)
lq.enqueue(2)
lq.peek()
lq.dequeue()
lq.size()
lq.clear()

Output:

Enqueued: 1
Enqueued: 2
Peek: 1
Dequeued: 1
Size: 1
Queue cleared

Using collections.deque

The collections.deque class from the collections module provides a more efficient way to implement a queue as it allows O(1) operations for appending and popping elements from both ends.

from collections import deque

class DequeQueue:
    def __init__(self):
        self.queue = deque()

    def enqueue(self, item):
        self.queue.append(item)
        print(f"Enqueued: {item}")

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Dequeue from an empty queue")
        item = self.queue.popleft()
        print(f"Dequeued: {item}")
        return item

    def peek(self):
        if self.is_empty():
            raise IndexError("Peek from an empty queue")
        print(f"Peek: {self.queue[0]}")
        return self.queue[0]

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        print(f"Size: {len(self.queue)}")
        return len(self.queue)

    def clear(self):
        self.queue.clear()
        print("Queue cleared")

# Example usage
dq = DequeQueue()
dq.enqueue(1)
dq.enqueue(2)
dq.peek()
dq.dequeue()
dq.size()
dq.clear()

Output:

Enqueued: 1
Enqueued: 2
Peek: 1
Dequeued: 1
Size: 1
Queue cleared

Using queue.Queue

The queue.Queue class from the queue module is designed specifically for multi-threaded programming. It provides thread-safe queues and various synchronization primitives.

from queue import Queue, Empty

class ThreadSafeQueue:
    def __init__(self, maxsize=0):
        self.queue = Queue(maxsize=maxsize)

    def enqueue(self, item):
        self.queue.put(item)
        print(f"Enqueued: {item}")

    def dequeue(self):
        try:
            item = self.queue.get(timeout=1)  # Wait for up to 1 second for an item
            print(f"Dequeued: {item}")
            return item
        except Empty:
            raise IndexError("Dequeue from an empty queue")

    def peek(self):
        with self.queue.mutex:
            if self.queue.empty():
                raise IndexError("Peek from an empty queue")
            print(f"Peek: {self.queue.queue[0]}")
            return self.queue.queue[0]

    def is_empty(self):
        return self.queue.empty()

    def size(self):
        print(f"Size: {self.queue.qsize()}")
        return self.queue.qsize()

    def clear(self):
        with self.queue.mutex:
            self.queue.queue.clear()
            print("Queue cleared")

# Example usage
tsq = ThreadSafeQueue()
tsq.enqueue(1)
tsq.enqueue(2)
tsq.peek()
tsq.dequeue()
tsq.size()
tsq.clear()

Output:

Enqueued: 1
Enqueued: 2
Peek: 1
Dequeued: 1
Size: 1
Queue cleared

Applications of Queues

Queues are widely used in various applications, including:

• Task Scheduling: Computer scientists propose the queue as one of the basic abstract data types, which many applications use to order elements according to a specific criterion.
• Breadth-First Search: Another traversal algorithm is the BFS algorithm which employs a queue data structure to traverse nodes in a graph level by level.
• Handling Asynchronous Data: This is because web servers handle data flow by using queues, processing requests in the order they receive them.
• Buffering: Queues are just as IO Buffers that relate data Interchange transactions as a way to control data flow between data producers and data consumers.
• Print Spooling: Scheduling of print jobs in printers who accomplish print requests on a first-come, first-served basis.
• Order Processing: Customers orders’ management in the context of both physical and online stores.
• Resource Allocation: Manage shared resources like printers or CPU time (e.g., allocate resources based on queue position).
• Batch Processing: Handle jobs in batches, processing them sequentially (e.g., image processing, data analysis).
• Networking: Manage network traffic, routing data packets (e.g., routers use queues to buffer incoming packets).
• Operating Systems: Manage interrupts, handle system calls, and implement process scheduling.
• Simulations: Model real-world systems with waiting lines (e.g., bank queues, traffic lights).

Advanced Queue Types

Let us now look into the advanced queue types below:

Priority Queue

A priority queue assigns a priority to each element. Elements with higher priority are dequeued before those with lower priority.

from queue import PriorityQueue

pq = PriorityQueue()

# Enqueue
pq.put((1, 'task 1'))  # (priority, value)
pq.put((3, 'task 3'))
pq.put((2, 'task 2'))

# Dequeue
print(pq.get())  # Output: (1, 'task 1')
print(pq.get())  # Output: (2, 'task 2')

Double-Ended Queue (Deque)

A deque allows elements to be added or removed from both ends, making it more versatile.

from collections import deque

deque = deque()

# Enqueue
deque.append(1)        # Add to rear
deque.appendleft(2)    # Add to front

# Dequeue
print(deque.pop())     # Remove from rear, Output: 1
print(deque.popleft()) # Remove from front, Output: 2

Circular Queue

Efficiently uses array space by wrapping around to the beginning when the end is reached.

class CircularQueue:
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.front = self.rear = -1
        self.capacity = capacity

    def is_empty(self):
        return self.front == -1

    def is_full(self):
        return (self.rear + 1) % self.capacity == self.front

    def enqueue(self, item):
        if self.is_full():
            print("Queue Overflow")
            return
        if self.front == -1:
            self.front = 0
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = item

    def dequeue(self):
        if self.is_empty():
            print("Queue Underflow")
            return
        item = self.queue[self.front]
        if self.front == self.rear:
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity
        return item

    def peek(self):
        if self.is_empty():
            print("Queue is empty")
            return
        return self.queue[self.front]

    def size(self):
        if self.is_empty():
            return 0
        return (self.rear + 1 - self.front) % self.capacity

# Example usage
cq = CircularQueue(5)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print(cq.dequeue())  # Output: 1
print(cq.peek())  # Output: 2

Blocking Queue

It synchronizes access between threads. It blocks when the queue is full or empty until space is available.

import queue

class BlockingQueue:
    def __init__(self, maxsize):
        self.queue = queue.Queue(maxsize)

    def put(self, item):
        self.queue.put(item)

    def get(self):
        return self.queue.get()

    def empty(self):
        return self.queue.empty()

    def full(self):
        return self.queue.full()

# Example usage
bq = BlockingQueue(5)
import threading

def producer():
    for i in range(10):
        bq.put(i)

def consumer():
    while True:
        item = bq.get()
        print(item)
        bq.task_done()

producer_thread = threading.Thread(target=producer)
consumer_thread = threading.Thread(target=consumer)
producer_thread.start()
consumer_thread.start()

Advantages of Queues

• Order Maintenance: Queues maintain the order of elements, which is essential for task scheduling and processing sequences.
• Concurrency Handling: Queues efficiently manage concurrent data processing, especially in multi-threaded applications.
• Simplicity and Flexibility: You can implement queues easily and adapt them for various applications, from simple task management to complex data processing pipelines.

Conclusion

Computer scientists propose the queue as one of the basic abstract data types, which many applications use to order elements according to a specific criterion. Queues are of different types in python but below are the best and commonly used methods to implement them. Learning the proper utilization of queues as well as mastering their application can play an extensive role in polishing one’s programming skills and make it possible to address numerous issues.

Frequently Asked Questions