Queue Data Structure

A Queue is a linear data structure characterized by the First-In, First-Out (FIFO) protocol. This means the first element added to the structure will always be the first one to be removed, mimicking a physical queue of people waiting for a service.

Unlike a stack, which restricts access to a single end, a queue maintains two distinct access points: elements enter at the Rear and are removed from the Front. This dual-ended nature preserves chronological order during data processing.

          +-----------------------------------------+
Dequeue <- | Front | Index 1 | Index 2 | ... | Rear | <- Enqueue
(Removal) +-----------------------------------------+ (Insertion)

Queue as an Abstract Data Type (ADT)

As an Abstract Data Type (ADT), a queue is defined strictly by its logical behavior and the set of operations allowed on it, entirely independent of any specific coding implementation.

The Queue ADT specifies that a structure must support adding elements at one end and removing them from the other. However, it does not dictate whether this should be achieved using a static contiguous array or a dynamic chain of linked nodes. This abstraction allows developers to focus on high-level problem-solving while keeping the underlying data management modular and interchangeable.

Core Primitive Operations: Enqueue and Dequeue

The functional integrity of a queue relies on two primary operations:

• Enqueue: Adds a new data element to the Rear of the queue. Before insertion, the system must check for an Overflow condition if the queue uses a fixed-size array. If space is available, the Rear pointer is incremented to the next index, and the value is stored.
• Dequeue: Removes and returns the element currently at the Front of the queue. Before removal, the system checks for an Underflow condition to ensure the queue is not empty. Once retrieved, the Front pointer increments to target the next element in line.

Linear Queue Limitations and Memory Fragmentation

In a standard Linear Queue implemented with a static array, a significant structural flaw exists due to the one-way movement of pointers.

As elements are enqueued, the Rear pointer moves toward the end of the array (MAX - 1). As elements are dequeued, the Front pointer also moves forward, leaving unused, empty slots behind it at the beginning of the array. Eventually, the Rear pointer hits the final index, and the system reports the queue as “Full”—even if there are multiple empty slots at the front created by previous deletions. This leads to artificial memory fragmentation where perfectly usable memory is wasted because the linear structure cannot recycle it.

The Solutions: Circular and Priority Queues

1. Circular Queue: The Modular Solution

To solve the fragmentation problem of linear queues, the Circular Queue logically connects the final slot of the array back to the first slot, forming a continuous ring. This is achieved using modular arithmetic for all pointer transitions:

New Index = (Current Index + 1) % MAX

By wrapping the Rear pointer back to index 0 when it exceeds the array bounds, the circular queue successfully reuses the slots freed up by the Front pointer, ensuring maximum memory utilization.

2. Priority Queue

A Priority Queue is a specialized variation where the strict FIFO rule is modified. Every element in this structure is assigned an explicit priority value. When a Dequeue operation runs, the system does not necessarily remove the oldest item; instead, it selects and removes the element with the highest priority. If two elements share the same priority, they are processed in their original order of arrival.

Real-World Application: Priority queues are critical for operating systems that must prioritize urgent system hardware interrupts over standard background user tasks.

Technical Architecture & Implementation

1. Circular Queue Logic Conditions

For a circular queue of size MAX, the management of pointers is as follows:

• Initialization: Set Front = -1 and Rear = -1.
• Full Condition: The queue is full when the next position of Rear would collide with Front: (Rear + 1) % MAX == Front.
• Empty Condition: The queue is empty if Front == -1.

2. Dynamic Linked Queue Implementation

A dynamic implementation uses a linked list to manage data, eliminating the risk of overflow as long as system memory is available.

• Structure: Each node contains a Data field and a Next pointer.
• Pointers: The system maintains a Front pointer targeting the first node and a Rear pointer targeting the last node.
• Dynamic Enqueue: Create a new node, point Rear->Next to the new node, and update Rear to the new node.
• Dynamic Dequeue: Retrieve data from the Front node, update Front to Front->Next, and free the memory of the old node.

3. C Implementation: Circular Queue Operations

This code demonstrates the modular logic required for a functional circular queue, matching standard technical university lab requirements.

C

#include <stdio.h>
#define MAX 5

int queue[MAX];
int front = -1, rear = -1;

// ENQUEUE: Insertion at the Rear with modular wrap-around
void enqueue(int val) {
    if ((rear + 1) % MAX == front) {
        printf("Queue Overflow\n");
    } else {
        if (front == -1) front = 0; // First element check
        rear = (rear + 1) % MAX;    // Modular increment
        queue[rear] = val;
        printf("Enqueued %d at index %d\n", val, rear);
    }
}

// DEQUEUE: Deletion from the Front with modular wrap-around
int dequeue() {
    if (front == -1) {
        printf("Queue Underflow\n");
        return -1;
    } else {
        int val = queue[front];
        if (front == rear) { // Reset if queue becomes empty
            front = rear = -1;
        } else {
            front = (front + 1) % MAX; // Modular increment
        }
        return val;
    }
}

Comparative Analysis: Queue Variations

The table below provides a direct architectural comparison of the three primary queue types:

Attribute / Feature	Linear Queue (Array)	Circular Queue (Array)	Priority Queue
Pointer Logic	Simple increment: rear++	Modular wrap-around: (rear + 1) % MAX	Sorted dynamically based on priority value
Memory Efficiency	Low; suffers from dead-space fragmentation	High; actively reuses empty slots	Varies depending on implementation (Array/Heap)
Ordering Rule	Strict FIFO	Strict FIFO (Circular ring)	Priority-based; ties default to FIFO
Overflow Condition	Rear == MAX - 1	(Rear + 1) % MAX == Front	Implementation dependent