Python Queues

Python Queues: A FIFO Data Structure

A Queue is a linear data structure that, like a Stack, follows a specific order for operations. The order is FIFO (First-In, First-Out). This means the first element added to the queue will be the first element to be removed.

The best real-world analogy is a checkout line at a grocery store. The first person to get in line is the first person to be served.

Core Queue Operations

A queue has two primary operations:

1. enqueue: Adds an element to the back (or "tail") of the queue.
2. dequeue: Removes an element from the front (or "head") of the queue.

Common helper operations include:

• peek (or front): Returns the front element of the queue without removing it.
• isEmpty: Checks if the queue is empty.
• size: Returns the number of elements in the queue.

Implementing a Queue in Python

While you can use a Python list to implement a queue, it is very inefficient. Appending to the end is fast (O(1)), but removing from the beginning (list.pop(0)) is slow (O(n)) because all other elements must be shifted.

The recommended way to implement a queue is with the collections.deque object, which stands for "double-ended queue". It is specifically designed for fast appends and pops from both ends.

from collections import deque

// Initialize an empty queue
my_queue = deque()
// Enqueue items
my_queue.append("Customer 1")
my_queue.append("Customer 2")
my_queue.append("Customer 3")
print("Queue after enqueues:", my_queue)
// Peek at the front item
front_item = my_queue[0]
print("Front item is:", front_item)
// Dequeue an item
removed_item = my_queue.popleft() // pop from the left side!
print("Dequeued item:", removed_item)
print("Queue after dequeue:", my_queue)

Class-based deque Implementation

For cleaner code, you can wrap the deque in a class.

from collections import deque

class Queue:
    def init(self):
        self.items = deque()
    def is_empty(self):
        return not self.items
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        if not self.is_empty():
            return self.items.popleft()
        return "Queue is empty"
    def size(self):
        return len(self.items)
q = Queue()
q.enqueue("Task 1")
q.enqueue("Task 2")
print("Queue size:", q.size()) // 2
print("Processing:", q.dequeue()) // Task 1

Common Use Cases for Queues

• Task Scheduling: Managing tasks in a CPU or jobs in a print queue.
• Buffering: Handling data streams between processes, like streaming video.
• Graph Algorithms: Used in Breadth-First Search (BFS) to explore nodes level by level.
• Order Processing: Managing orders in an e-commerce system.