Python - Data Structures - Queue

Queue Data Structures in Python

In Python, like any other programming language, the queue is a linear data structure that operates on the FIFO principle. This means that the element added first will be removed from the queue first.

Understand Queue with a Scenario

A queue is a linear data structure that follows the First In, First Out (FIFO) principle, similar to how people wait in line. This means that the first item added to the queue is the first one to be served. The three main operations associated with a queue are:

1. Front: This operation allows you to view the first item in the queue without removing it.
2. Dequeue: This operation removes the first item from the queue.
3. Enqueue: This operation adds a new item to the end of the queue.
4. Rear: Get the last item from the queue.

All of the above operation takes O(1) time complexity.

How to Create a Stack

There are several approaches to creating a queue in Python. Here we will create a queue using data structures and Python library modules. Python Queue can be constructed using the following methods:

Using collections.deque

Queue in Python can be implemented using the deque class from the collections module. Deque is preferred over list in the cases where we need quicker append and pop operations from both the ends of container, as deque provides an O(1) time complexity for append and pop operations.

from collections import deque

# Queue implementation using deque
queue = deque()

# Enqueue elements
queue.append(10)
queue.append(20)
queue.append(30)

print("Queue after enqueueing elements:", queue)

# Dequeue an element
dequeued_element = queue.popleft()
print("Dequeued element:", dequeued_element)
print("Queue after dequeuing:", queue)

# Peek the front element
if queue:
    print("Front element:", queue[0])
else:
    print("Queue is empty.")

Using queue.Queue

The queue module provides a FIFO Queue implementation with thread safety, which is useful for multithreaded applications.

from queue import Queue

# Queue implementation using queue.Queue
queue = Queue()

# Enqueue elements
queue.put(10)
queue.put(20)
queue.put(30)

print("Queue size:", queue.qsize())

# Dequeue an element
dequeued_element = queue.get()
print("Dequeued element:", dequeued_element)
print("Queue size after dequeuing:", queue.qsize())

# Check if the queue is empty
if queue.empty():
    print("Queue is empty.")
else:
    print("Queue is not empty.")

Using a List

You can use Python lists to implement a queue by using append() to enqueue and pop(0) to dequeue. However, this approach is less efficient for large queues because pop(0) involves shifting all elements.

# Queue implementation using a list
queue = []

# Enqueue elements
queue.append(10)
queue.append(20)
queue.append(30)

print("Queue after enqueueing elements:", queue)

# Dequeue an element
dequeued_element = queue.pop(0)
print("Dequeued element:", dequeued_element)
print("Queue after dequeuing:", queue)

# Peek the front element
if queue:
    print("Front element:", queue[0])
else:
    print("Queue is empty.")

Using a Custom Class

A custom class allows you to encapsulate the queue logic, making the implementation more readable and reusable.

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

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            return "Queue is empty!"

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            return "Queue is empty!"

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

    def size(self):
        return len(self.queue)

# Usage
queue = Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)

print("Front element:", queue.peek())
print("Dequeued element:", queue.dequeue())
print("Queue size:", queue.size())

Use Cases of Queue

There are the following use cases of Queue:

• Job Scheduling: Operating systems employ queues to schedule jobs; the first job entered is the first to be processed.
• Print Queue Management: Documents are queued for print spooling in the order that they are sent to the printer.
• Data Buffering: In situations like live video streaming, queues serve as buffers in data streams, guaranteeing that data is handled in the order it comes.
• Asynchronous Data movement: Data can be temporarily held and processed later, thanks to queues, which enable asynchronous data movement between components.