Gaurav Aryal ⚡️
Queue Data Structure in Python

Queue Data Structure in Python

A Queue is an abstract data type that follows the First-In-First-Out (FIFO) principle. It represents a collection of elements where the element added first is the first to be removed. Just like a real-life queue, the elements are arranged in a sequential order, and new elements are added at the rear and removed from the front.

Basic Operations on a Queue
A Queue typically supports the following operations:
Enqueue: Adds an element to the rear of the Queue. Dequeue: Removes and returns the element from the front of the Queue. Front: Returns the element at the front 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
In Python, we can implement a Queue using various data structures. One common approach is to use a list, where the front of the Queue is at index 0 and the rear is at the end. Another efficient approach is to use the collections.deque class, which provides an optimized implementation of a double-ended Queue.
In our implementation, we will use the collections.deque class, which allows us to easily perform enqueue and dequeue operations in constant time.

from collections import deque

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

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

    def dequeue(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        return self.queue.popleft()

    def front(self):
        if self.is_empty():
            raise Exception("Queue is empty")
        return self.queue[0]

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

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

Use Cases for Queue
Queues are used in various scenarios, including:
Breadth-First Search (BFS): Queues are extensively used in BFS algorithms to explore nodes in a graph or tree level by level.
Task Scheduling: Queues can be employed to manage a queue of tasks, where new tasks are added at the rear and processed from the front.
Message Queues: In messaging systems, Queues are used to store and manage messages between producers and consumers.

Time and Space Complexity Analysis
The time complexity of Queue operations using a deque implementation is as follows:
Enqueue: O(1)
Dequeue: O(1)
Front: O(1)
IsEmpty: O(1)
Size: O(1)

The space complexity of a Queue depends on the number of elements stored in it and is O(n), where n represents the number of elements in the Queue. This is because the space required to store the elements grows linearly with the number of elements.
Since a Queue is implemented using a deque or a list in Python, the space complexity also includes the overhead of the underlying data structure. However, the additional space required for the Queue operations themselves remains constant.
It’s important to note that the space complexity may vary depending on the specific implementation and any additional data associated with each element in the Queue.
In terms of practical usage, Queues are memory-efficient data structures as they allocate space only for the elements that are actually present in the Queue. This makes them suitable for managing large collections of data where memory utilization is a concern.

profile image