Implementation & Application of Queue using Array

Queue implementation using Array

A queue is an abstract data type that follows the First-In-First-Out (FIFO) principle: the element inserted first is the element removed first. A queue supports the following fundamental operations: enqueue (insert an element at the rear), dequeue (remove an element from the front), and queries such as checking whether the queue is empty or full, and retrieving the front and rear elements without removing them.

When implementing a queue using a simple linear array, repeatedly incrementing the front and rear indices may cause the indices to reach the end of the array even though there might be free space at the beginning (wasted space). The standard solution is to treat the array as circular, so indices wrap around to the start using modulo arithmetic.

Enqueue operation (Insertion)

• Check whether the queue is full.
• If inserting the very first element (queue was empty), initialise the front pointer appropriately.
• Increment the rear index in circular manner: rear = (rear + 1) % capacity.
• Store the new element at array[rear].
• Update any size counter or other bookkeeping used to detect empty/full.

Dequeue operation (Removal)

• Check whether the queue is empty.
• Retrieve the value at array[front] and return it (or provide it to the caller).
• Increment the front index in circular manner: front = (front + 1) % capacity.
• Update the size counter or other bookkeeping.
• If the queue becomes empty after removal and you use sentinel values, reset front and rear to -1; if you use a size counter, set size to 0 and keep front/rear as per the chosen convention.

Linear vs Circular array

• Linear array implementation increments indices without wrap-around and typically requires shifting elements or resetting when front passes the end; this wastes time or space.
• Circular array implementation uses modulo arithmetic to reuse previously freed slots at the start of the array and avoids shifting elements.
• Common ways to implement a queue using an array:
  • Use front, rear indices and a separate size counter to track the number of elements; detect full when size == capacity and empty when size == 0.
  • Use front and rear with sentinel value -1 to indicate empty; update/reset sentinel values when queue becomes empty.

Corrected C implementation (circular array)

#include <limits.h> #include <stdio.h> #include <stdlib.h> /* Queue implemented using circular array and a size counter */ struct Queue { int front, rear, size; unsigned capacity; int *array; }; struct Queue* createQueue(unsigned capacity) { struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue)); if (queue == NULL) { return NULL; } queue->capacity = capacity; queue->front = 0; queue->size = 0; queue->rear = capacity - 1; /* rear will move to 0 on first enqueue */ queue->array = (int*) malloc(queue->capacity * sizeof(int)); if (queue->array == NULL) { free(queue); return NULL; } return queue; } int isFull(struct Queue* queue) { return (queue->size == queue->capacity); } int isEmpty(struct Queue* queue) { return (queue->size == 0); } void enqueue(struct Queue* queue, int item) { if (isFull(queue)) { printf("Queue overflow. Cannot enqueue %d
", item); return; } queue->rear = (queue->rear + 1) % queue->capacity; queue->array[queue->rear] = item; queue->size = queue->size + 1; printf("%d enqueued to queue
", item); } int dequeue(struct Queue* queue) { if (isEmpty(queue)) { printf("Queue underflow. Cannot dequeue
"); return INT_MIN; /* sentinel for failure */ } int item = queue->array[queue->front]; queue->front = (queue->front + 1) % queue->capacity; queue->size = queue->size - 1; return item; } int frontItem(struct Queue* queue) { if (isEmpty(queue)) { return INT_MIN; } return queue->array[queue->front]; } int rearItem(struct Queue* queue) { if (isEmpty(queue)) { return INT_MIN; } return queue->array[queue->rear]; } int main() { struct Queue* queue = createQueue(1000); if (queue == NULL) { return 1; } enqueue(queue, 1); enqueue(queue, 2); enqueue(queue, 3); enqueue(queue, 4); printf("%d dequeued from queue

", dequeue(queue)); printf("Front item is %d
", frontItem(queue)); printf("Rear item is %d
", rearItem(queue)); /* free allocated memory */ free(queue->array); free(queue); return 0; }

Walkthrough example (state after operations)

Assume capacity = 5, initially front = 0, rear = 4 (as initialised above), size = 0.

• Enqueue 1:
  • rear becomes (4+1)%5 = 0; array[0] = 1; size = 1; front = 0.
• Enqueue 2:
  • rear becomes (0+1)%5 = 1; array[1] = 2; size = 2; front = 0.
• Enqueue 3:
  • rear becomes 2; array[2] = 3; size = 3; front = 0.
• Dequeue:
  • return array[front] = array[0] = 1; front becomes (0+1)%5 = 1; size = 2; remaining elements at indices 1 and 2.

Edge cases and conventions

• Overflow: Attempting to enqueue when the queue is full should be detected (e.g., size == capacity) and handled gracefully.
• Underflow: Attempting to dequeue from an empty queue should be detected (e.g., size == 0) and handled gracefully.
• Sentinel approach: Some implementations use front = rear = -1 to indicate an empty queue; when the last element is removed, both are reset to -1. The circular modulo increments still apply when adding/removing elements.
• Memory management: If the capacity is fixed, the array size determines maximum elements; for dynamic growth, use a dynamic array or linked list implementation of queue.

Time and space complexity

• Enqueue: O(1)
• Dequeue: O(1)
• Front / Rear (peek): O(1)
• Space complexity: O(N) where N is the capacity of the array (fixed-size implementation).

Applications of queue

• Buffers in media players (for example, an mp3 player or CD player) that play items in arrival order.
• Handling interrupts in an operating system where requests are queued for service.
• Managing a playlist where new songs are added at the end.
• Waiting queues for shared resources such as CPU scheduling queues, printers, or disk I/O.
• Message buffering in chat or messaging applications where messages are stored on the server until delivered.