Queue in Python

What is a Queue?

A queue is a data structure that stores elements in a FIFO (First In, First Out) order. This means:

• The first element put into the queue will be the first one extracted.
• Think of it as a line of people waiting at a ticket counter-the first person there is served first.

Queues are very widely used in programming for applications like:

• Task scheduling
• Handling requests in web servers
• Managing resources in multi-threaded applications

Ways to Implement Queues in Python

Python has several tools that can be used to implement queues. Each one is designed for certain situations. Let’s go a bit further for each method.

1. Queue using collections.deque

What is deque?

• deque (pronounced “deck”) stands for double-ended queue.
• It is a part of the collections module in Python.
• It allows you to add and remove items from both ends efficiently, i.e., it has O(1) (constant time) complexity for these operations.

When to Use deque?

• When you need a simple, efficient queue implementation without additional features like thread safety.
• Suitable for most general-purpose tasks.

Here’s how you can use deque to create a queue:

from collections import deque

# Step 1: Create an empty queue
queue = deque()

# Step 2: Enqueue (add) elements
queue.append("A")  # Adds "A" to the right end of the queue
queue.append("B")  # Adds "B" to the right end
queue.append("C")  # Adds "C" to the right end
print("Queue after enqueue:", queue)

# Step 3: Dequeue (remove) elements
print("Dequeued:", queue.popleft())  # Removes "A" from the left end
print("Dequeued:", queue.popleft())  # Removes "B" from the left end

# Step 4: Check the queue state
print("Queue after dequeue:", queue)

Output:

Queue after enqueue: deque(['A', 'B', 'C'])
Dequeued: A
Dequeued: B
Queue after dequeue: deque(['C'])

Key Points:

• append(x) adds an element x to the right end of the queue.
• popleft() removes an element from the left end of the queue.

2. Queue using queue.Queue

What is queue.Queue?

• A part of the queue module in Python.
• Designed for multi-threaded programming.
• Provides a thread-safe implementation of a queue. That means, it can be used in a scenario where many threads access the queue at the same time.

Features of queue.Queue:

1. Thread Safety: It prevents issues like race conditions when used in multi-threaded programs.
2. Fixed Size: You may specify the queue as fixed-sized: when such a queue becomes full, then putting additional elements to it would cause the inserting thread to wait for space.

Here’s how to use queue.Queue:

from queue import Queue

# Step 1: Create a queue with a maximum size
queue = Queue(maxsize=5)

# Step 2: Enqueue (put) elements
queue.put("A")  # Adds "A" to the queue
queue.put("B")  # Adds "B" to the queue
queue.put("C")  # Adds "C" to the queue
print("Queue size after enqueue:", queue.qsize())

# Step 3: Dequeue (get) elements
print("Dequeued:", queue.get())  # Removes "A" from the queue
print("Dequeued:", queue.get())  # Removes "B" from the queue

# Step 4: Check the queue size
print("Queue size after dequeue:", queue.qsize())

Output:

Queue size after enqueue: 3
Dequeued: A
Dequeued: B
Queue size after dequeue: 1

Key Methods:

• put(x): Adds an element x to the queue. Blocks if the queue is full.
• get(): Removes and returns the first element. Blocks if the queue is empty.
• qsize(): Returns the current number of elements in the queue.

When to Use?

• When you’re working with multi-threaded programs and need thread-safe operations.

3. Priority Queue using queue.PriorityQueue

What is a Priority Queue?

• A specialized queue where elements are retrieved based on their priority rather than their insertion order.
• Lower priority numbers are dequeued first.

Here’s how you can use PriorityQueue:

from queue import PriorityQueue

# Step 1: Create a priority queue
priority_queue = PriorityQueue()

# Step 2: Enqueue elements with priorities
priority_queue.put((2, "Task A"))  # Priority 2
priority_queue.put((1, "Task B"))  # Priority 1
priority_queue.put((3, "Task C"))  # Priority 3

# Step 3: Dequeue elements
print("Dequeued:", priority_queue.get())  # Removes "Task B" (lowest priority number)
print("Dequeued:", priority_queue.get())  # Removes "Task A"
print("Dequeued:", priority_queue.get())  # Removes "Task C"

Output:

Dequeued: (1, 'Task B')
Dequeued: (2, 'Task A')
Dequeued: (3, 'Task C')

When to Use?

• When you need to process elements based on priority, such as in scheduling systems.

4. Queue using list

Why Use a List?

• Lists are native to Python, so they are very convenient to use.
• However, they are not efficient for queue operations since removing the first element pop(0) requires shifting all other elements, which has O(n) complexity.

Here’s a simple implementation using a list:

# Step 1: Create an empty queue
queue = []

# Step 2: Enqueue elements
queue.append("A")
queue.append("B")
queue.append("C")
print("Queue after enqueue:", queue)

# Step 3: Dequeue elements
print("Dequeued:", queue.pop(0))  # Removes the first element
print("Dequeued:", queue.pop(0))

# Step 4: Check the queue state
print("Queue after dequeue:", queue)

Output:

Queue after enqueue: ['A', 'B', 'C']
Dequeued: A
Dequeued: B
Queue after dequeue: ['C']

When to Use?

• For small-scale tasks or when you don’t require efficient performance.

Summary Table