Implement a Queue in Python

Introduction

The queue is a data structure that stores items in a First-In, First-Out (FIFO) manner. Unlike a stack, where elements are added and removed from the same end, in a queue, elements are added at one end (the “rear”) and removed from the other end (the “front”). In this blog post, we’ll explore how to implement a queue from scratch in Python and discuss Python’s in-built mechanisms for creating queues.

The Queue Data Structure

The fundamental operations for a queue are:

1. Enqueue: To add an element to the rear of the queue.
2. Dequeue: To remove and return the element from the front of the queue.
3. Front: To look at the front element without removing it.
4. isEmpty: To check whether the queue is empty.
5. getSize: To get the number of elements in the queue.

Implementing a Queue from Scratch

Just like stacks, queues can be implemented using either Python lists or custom linked lists.

Using Python’s native list data structure, a queue can be easily implemented as follows:

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

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

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

    def front(self):
        if not self.isEmpty():
            return self.queue[0]
        else:
            return "Queue is empty"

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

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

# Example usage
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # Output will be 1
print(q.front())  # Output will be 2
print(q.isEmpty())  # Output will be False
print(q.getSize())  # Output will be 2

Using Python’s In-Built Queue Mechanisms

Using Python List Directly

Python lists provide the append() and pop() methods for adding and removing elements, but removing an element from the beginning of a list is an O(n) operation. This is not efficient for large queues.

# Initialize queue
queue = []

# Enqueue elements
queue.append(1)
queue.append(2)
queue.append(3)

# Dequeue elements
print(queue.pop(0))  # Output will be 1

Using collections.deque

The collections.deque class is a double-ended queue, and it supports fast O(1) append and pop operations from both ends. It’s ideal for implementing a queue in Python.

from collections import deque

# Initialize queue
queue = deque()

# Enqueue elements
queue.append(1)
queue.append(2)
queue.append(3)

# Dequeue elements
print(queue.popleft())  # Output will be 1

Using queue.Queue

Python also offers the Queue class from the queue module for implementing multi-producer, multi-consumer queues, which is especially useful in multi-threaded programming.

from queue import Queue

# Initialize queue
q = Queue()

# Enqueue elements
q.put(1)
q.put(2)
q.put(3)

# Dequeue elements
print(q.get())  # Output will be 1

Conclusion

We’ve seen how to implement a queue data structure in Python both from scratch and by using Python’s in-built capabilities. Understanding queues is crucial for grasping more complex data structures and algorithms, especially those related to task scheduling and breadth-first search algorithms.

With multiple ways to implement a queue in Python, you can choose the one that best fits your specific needs and performance requirements.

Conclusion

We’ve seen how to implement a queue data structure in Python both from scratch and by using Python’s in-built capabilities. Understanding queues is crucial for grasping more complex data structures and algorithms, especially those related to task scheduling and breadth-first search algorithms.

With multiple ways to implement a queue in Python, you can choose the one that best fits your specific needs and performance requirements.

If you find this guide useful, please share with others, and spread the knowledge!