Circular & Priority Queues

Circular Queue

A Circular Queue is a linear data structure in which the last position is connected back to the first position, forming a circle. It follows the First In First Out (FIFO) principle.

Key Points:

• Helps efficiently reuse space of the queue.
• Uses modulo arithmetic to efficiently wrap around indices.
• Commonly implemented with arrays.

Example Implementation (Python):

class CircularQueue:
    def __init__(self, capacity):
        self.queue = [None] * capacity
        self.capacity = capacity
        self.front = -1
        self.rear = -1

    def enqueue(self, data):
        if (self.rear + 1) % self.capacity == self.front:
            print("Queue is full")
            return
        if self.front == -1:
            self.front = 0
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = data

    def dequeue(self):
        if self.front == -1:
            print("Queue is empty")
            return None
        data = self.queue[self.front]
        if self.front == self.rear:
            self.front = -1
            self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity
        return data

    def display(self):
        if self.front == -1:
            print("Queue is empty")
            return
        i = self.front
        while True:
            print(self.queue[i], end=" ")
            if i == self.rear:
                break
            i = (i + 1) % self.capacity
        print()

Priority Queue

A Priority Queue is an abstract data type similar to a regular queue, but with an added priority assigned to each element. Elements are dequeued based on their priority rather than arrival order.

Key Points:

• Higher priority elements are dequeued before lower priority.
• Can be implemented using heaps or linked lists.
• Useful in scheduling, simulations, and pathfinding.

Example Implementation (Python using heapq):

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []

    def push(self, item, priority):
        heapq.heappush(self.heap, (priority, item))

    def pop(self):
        if self.heap:
            return heapq.heappop(self.heap)[1]
        else:
            return None

    def peek(self):
        if self.heap:
            return self.heap[0][1]
        else:
            return None

# Usage Example
pq = PriorityQueue()
pq.push("task1", 3)
pq.push("task2", 1)
pq.push("task3", 2)

print(pq.pop())  # Outputs: task2 (highest priority)
print(pq.peek()) # Outputs: task3