Python: Priority Queue Implementation

1. Introduction

A priority queue is a specialized data structure that allows items to be inserted with a priority value. Instead of being served in a traditional first-in, first-out manner like a typical queue, items in a priority queue are dequeued based on their priority. In this blog post, we'll delve into the details of implementing a priority queue using Python.

2. Program Overview

1. Define the PriorityQueue class.

2. Implement the enqueue method to insert an item with a given priority.

3. Implement the dequeue method to remove the item with the highest priority.

4. Implement a method to check if the queue is empty.

5. Implement a method to display the queue.

3. Code Program

class PriorityQueue:

    def __init__(self):
        # Initialize an empty list to hold the items and their priorities
        self.queue = []

    def enqueue(self, data, priority):
        """Add data to the queue with a specific priority."""
        # Use a tuple with (priority, data) to insert into the queue
        self.queue.append((priority, data))
        # Sort the queue by priority in descending order
        self.queue.sort(reverse=True)

    def dequeue(self):
        """Remove and return the item with the highest priority."""
        if not self.is_empty():
            # Pop the item with the highest priority
            return self.queue.pop()[1]
        else:
            return "Queue is empty."

    def is_empty(self):
        """Check if the queue is empty."""
        return len(self.queue) == 0

    def display(self):
        """Display the items in the queue."""
        for item in self.queue:
            print(item[1], end=" -> ")
        print(None)  # Display end of queue

# Sample usage
pq = PriorityQueue()
pq.enqueue("Task 1", 3)
pq.enqueue("Task 2", 1)
pq.enqueue("Task 3", 2)
print("Priority Queue:")
pq.display()
print("Dequeued:", pq.dequeue())
print("Priority Queue after dequeue:")
pq.display()

Output:

Priority Queue:
Task 1 -> Task 3 -> Task 2 -> None
Dequeued: Task 1
Priority Queue after dequeue:
Task 3 -> Task 2 -> None

4. Step By Step Explanation

1. The priority queue is implemented as a list of tuples. Each tuple consists of a priority and data.

2. When data is enqueued, it's added to the queue with its respective priority.

3. The enqueue method ensures the queue remains sorted based on priority, so the dequeue operation always removes the item with the highest priority.

4. The dequeue method removes and returns the item with the highest priority.

5. is_empty checks if the queue is empty.

6. The display method is provided for visualization, showing the items in the priority order.