Queue in Python

Queues are fundamental data structures that follows the First In, First Out (FIFO) principle, meaning the first element added to the queue will be the first one to be removed. Think of a queue like a line at a coffee shop: the first person in line gets served first, while new people join the end of the line.

Python provides several ways to implement queues, each suited for different purposes such as manage data flow in various scenarios, from simple scripts to complex, multithreaded applications.

This article will walk you through the basics of queues, their types, and how to work with them in Python.

source: GeeksForGeeks

Types of Queues in Python

Each queue type has specific use cases:

• FIFO Queue: First In, First Out. Processing items in arrival order (e.g., task scheduling). Example: queue.Queue or collections.deque.
• LIFO Queue: Last In, First Out (stack behavior). Processing the most recent item first (e.g., undo functionality in applications). Example: queue.LifoQueue.
• Priority Queue: Elements are processed based on priority rather than order of arrival. Prioritizing certain tasks over others (e.g., emergency handling systems). Example: queue.PriorityQueue.

In Python, you can create a queue using a variety of methods:

• Lists (although not efficient for large queues)
• collections.deque — a double-ended queue
• queue.Queue — a thread-safe queue for multithreading
• queue.LifoQueue — a Last In, First Out queue
• queue.PriorityQueue — a queue where elements are prioritized

Let’s explore each of these methods, along with examples.

Queue using lists

A simple way to create a queue is by using a Python list and utilizing the append() and pop(0) methods. However, lists are generally inefficient for queue operations because removing items from the front requires shifting all other elements, which is slow for large lists.

# Basic queue implementation using a list
queue = []

# Adding elements (Enqueue)
queue.append('A')
queue.append('B')
queue.append('C')

# Removing elements (Dequeue)
print(queue.pop(0))  # Output: A
print(queue.pop(0))  # Output: B
print(queue.pop(0))  # Output: C

Time Complexity:

• Enqueue (append): O(1)
• Dequeue (pop(0)): O(n)

Use Cases: Lists are best used for small queues or temporary data storage when you don’t need frequent dequeuing. If you’re building a simple queue in a short script or want a quick solution without importing additional libraries, lists may be sufficient.

Queue Using collections.deque

The deque (double-ended queue) is a part of the collections module and is much more efficient for queue operations. It allows for fast appending and popping from both ends.

from collections import deque

# Creating a deque
queue = deque()

# Adding elements (Enqueue)
queue.append('A')
queue.append('B')
queue.append('C')

# Removing elements (Dequeue)
print(queue.popleft())  # Output: A
print(queue.popleft())  # Output: B
print(queue.popleft())  # Output: C

Time Complexity:

• Enqueue (append): O(1)
• Dequeue (popleft): O(1)

Use Cases: deque is excellent for typical FIFO queues, where you need fast appending and removal. It's commonly used in task scheduling, buffering data streams, and implementing breadth-first search (BFS) algorithms in graphs.

Queue Using queue.Queue

The queue.Queue class in Python is designed specifically for thread-safe, FIFO queues, making it ideal for multithreaded programs where multiple threads need to access the same queue.

from queue import Queue

# Creating a queue
queue = Queue()

# Adding elements (Enqueue)
queue.put('A')
queue.put('B')
queue.put('C')

# Removing elements (Dequeue)
print(queue.get())  # Output: A
print(queue.get())  # Output: B
print(queue.get())  # Output: C

Key Methods in queue.Queue:

• put(item): Adds an item to the queue.
• get(): Removes and returns an item from the queue.
• qsize(): Returns the number of items in the queue.
• empty(): Returns True if the queue is empty, otherwise False.
• full(): Returns True if the queue is full (if a max size is set).

Time Complexity:

• Enqueue (put): O(1)
• Dequeue (get): O(1)

Use Cases: This queue is widely used in multithreaded applications where multiple threads need to share a queue. It’s common in producer-consumer problems, where one thread produces data and another consumes it. Examples include web scraping, server request handling, and processing pipelines.

LIFO Queue (Last In, First Out) Using queue.LifoQueue

A LIFO queue (also known as a stack) is the opposite of a FIFO queue. The most recently added item is the first to be removed. This is implemented with the LifoQueue class.

from queue import LifoQueue

# Creating a LIFO queue
stack = LifoQueue()

# Adding elements
stack.put('A')
stack.put('B')
stack.put('C')

# Removing elements (Last In, First Out)
print(stack.get())  # Output: C
print(stack.get())  # Output: B
print(stack.get())  # Output: A

Time Complexity:

• Push (put): O(1)
• Pop (get): O(1)

Use Cases: LIFO queues are helpful when you need the most recently added item first. Typical use cases include implementing undo operations in applications, maintaining browser history stacks, and managing depth-first search (DFS) in trees or graphs.

Priority Queue Using queue.PriorityQueue

A Priority Queue processes elements based on priority rather than the order they were added. Elements with the lowest priority number are dequeued first. This type of queue is useful for scenarios where certain tasks should be handled before others.

from queue import PriorityQueue

# Creating a priority queue
priority_queue = PriorityQueue()

# Adding elements with priority (priority, item)
priority_queue.put((1, 'Low Priority'))
priority_queue.put((3, 'High Priority'))
priority_queue.put((2, 'Medium Priority'))

# Removing elements based on priority
print(priority_queue.get()[1])  # Output: Low Priority
print(priority_queue.get()[1])  # Output: Medium Priority
print(priority_queue.get()[1])  # Output: High Priority

Time Complexity:

• Enqueue (put): O(log n) — because it maintains the heap property
• Dequeue (get): O(log n) — retrieves and removes the smallest element

Use Cases: Priority queues are useful for managing tasks based on priority. Common applications include scheduling algorithms in operating systems, Dijkstra’s shortest path algorithm, and handling emergency service requests where higher priority tasks must be processed first.

To understand this concept more I implemented a simple task scheduler. Sharing one of the code (using the Queue.queue class) here:

fimport queue
import threading
import time

# Define a queue for tasks
task_queue = queue.Queue()

# Define a worker function that processes tasks
def worker():
    while True:
        task = task_queue.get()  
        if task is None:
            break  
        print(f"Processing task: {task}")
        time.sleep(1) 
        task_queue.task_done()  
        print(f"Task completed: {task}")

# Function to add tasks to the queue
def add_tasks():
    for i in range(1, 6):
        task = f"Task-{i}"
        print(f"Adding {task} to the queue")
        task_queue.put(task) 
    print("All tasks have been added to the queue.")

# Set up and start the worker threads
num_worker_threads = 3
threads = []

for i in range(num_worker_threads):
    thread = threading.Thread(target=worker)
    thread.start()
    threads.append(thread)

# Add tasks to the queue
add_tasks()

# Wait until all tasks have been processed
task_queue.join()  
print("All tasks have been processed.")

# Stop the worker threads
for i in range(num_worker_threads):
    task_queue.put(None)  

for thread in threads:
    thread.join()

print("All worker threads have been stopped.")

More code related to Queue’s coming up in my github