Linked queues and circular queues represent two fundamental approaches to implementing the queue data structure, each offering distinct advantages suited to specific computational problems.

Linked Queue Implementation

A linked queue utilizes a linked list structure where elements are added at the rear and removed from the front. This implementation maintains two primary pointers: front, referencing the head node, and rear, referencing the tail node.

Operational Logic

• Initialization: Set both front and rear to None, indicating an empty queue.
• Enqueue: Create a new node. If the queue is empty, both pointers reference the new node. Otherwise, the current rear's next pointer links to the new node, and rear updates to the new node.
• Dequeue: If the queue is empty, return a sentinel value. Otherwise, retrieve data from the front node, advance front to the next node, and if front becomes None, reset rear to None.

Python Implementation

The following code demonstrates a linked queue using a custom node class:

class QueueNode:
    def __init__(self, value):
        self.value = value
        self.next_node = None

class DynamicLinkedQueue:
    def __init__(self):
        self.front = None
        self.rear = None

    def add_item(self, value):
        new_node = QueueNode(value)
        if self.rear is None:
            self.front = self.rear = new_node
        else:
            self.rear.next_node = new_node
            self.rear = new_node

    def remove_item(self):
        if self.front is None:
            return None
        retrieved_value = self.front.value
        self.front = self.front.next_node
        if self.front is None:
            self.rear = None
        return retrieved_value

Use Cases

Linked queues are ideal for scenarios requiring dynamic memory allocation, such as managing process scheduling in operating systems or handling asynchronous data streams in network applications where the data volume is unpredictable.

Circular Queue Implementation

A circular queue uses a fixed-size array, treating the end of the array as connected to the beginning. It typically tracks a head index for dequeuing and a tail index for enqueuing. The queue is empty when head and tail are equal (in some implementations) or defined by sentinel values. It is full when (tail + 1) % capacity == head.

Operational Logic

• Initialization: Allocate an array of a specific capacity and set head and tail to -1.
• Enqueue: Check if the queue is full. If it is the first element, set indices to 0. Otherwise, update tail circularly and place the element.
• Dequeue: Check if the queue is empty. If it contains only one element, reset indices to -1. Otherwise, retrieve the element and update head circularly.

Python Implementation

class RingBufferQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.buffer = [None] * capacity
        self.head = -1
        self.tail = -1

    def enqueue(self, item):
        if (self.tail + 1) % self.capacity == self.head:
            print("Error: Queue is at full capacity.")
            return
        if self.head == -1:
            self.head = 0
            self.tail = 0
        else:
            self.tail = (self.tail + 1) % self.capacity
        self.buffer[self.tail] = item

    def dequeue(self):
        if self.head == -1:
            print("Error: Queue is empty.")
            return None
        item = self.buffer[self.head]
        if self.head == self.tail:
            self.head = -1
            self.tail = -1
        else:
            self.head = (self.head + 1) % self.capacity
        return item

Use Cases

Circular queues are efficient for fixed-capacity buffering. Common applications include memory management, producer-consumer problems, and implementing sliding window algorithms where data overwrites older entries automatically or strictly bounded storage is required.