Queue Implementation in C

Analogy categoryAnalogies

1. Introduction

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle: the first element added is the first one removed. Think of a line of people waiting at a ticket counter — whoever joins first gets served first. Queues are widely used in C programs for task scheduling, breadth-first search (BFS), buffering data (e.g., I/O buffers, print spoolers), and simulating real-world waiting-line systems.

🏏

Cricket analogy: A queue mirrors fans lining up outside the stadium gate for an IPL final: the first fan to arrive at 6am is the first one let in, exactly the FIFO principle a queue enforces, unlike a stack where the last person in would somehow enter first.

This lesson implements a queue using a fixed-size array with two index variables, 'front' and 'rear', that track the ends of the queue. A naive array queue wastes space as elements are dequeued, so production-quality implementations typically use a circular queue (wrapping indices with modulo arithmetic) or a linked-list-based queue for unbounded growth.

🏏

Cricket analogy: A naive stadium seating chart that never reuses vacated seats after fans leave wastes capacity, just as a naive array queue wastes space after dequeues; production venues reuse seats dynamically the way a circular queue wraps indices with modulo arithmetic.

2. Syntax

#define MAX 100

typedef struct Queue {
    int items[MAX];
    int front;
    int rear;
} Queue;

'front' points to the index of the next element to be dequeued, and 'rear' points to the index of the last enqueued element. An empty queue is initialized with front = 0 and rear = -1 (or equivalently, a count of 0).

🏏

Cricket analogy: 'front' is like the next fan due to enter the stadium gate, and 'rear' is like the last fan who joined the back of the line; an empty queue before the gates open has front = 0 and rear = -1, meaning no one has been let in and no one is waiting yet.

3. Explanation

The two core queue operations are enqueue (add an element at the rear) and dequeue (remove the element at the front). Enqueue increments 'rear' and stores the new value there; dequeue reads the value at 'front' and increments 'front'. Because elements are always added at one end and removed from the other, the relative order of insertion is preserved — the hallmark of FIFO behavior.

🏏

Cricket analogy: Enqueue is like a new fan joining the back of the stadium entry line, incrementing 'rear'; dequeue is like the gate letting the front-most fan in and incrementing 'front'; because entry always happens at one end and exit at the other, fans are let in exactly in the order they arrived, true FIFO.

A queue can be implemented with an array (as shown here) or with a linked list where 'front' and 'rear' are pointers to the head and tail nodes. The linked-list version avoids the wasted-space problem of a simple linear array queue and grows dynamically, similar to how a stack can also be built on either structure.

🏏

Cricket analogy: A stadium's entry line can be a fixed physical rope barrier (array) or a flexible chain of stewards who each point to the next person (linked list); the steward-chain version grows to any crowd size without wasting rope, just as a linked-list queue avoids the wasted-space problem of an array queue.

Queue overflow (enqueue when rear == MAX - 1) and queue underflow (dequeue when the queue is empty, front > rear) must always be checked. With a simple linear array queue, once 'front' advances past index 0 due to dequeues, that freed space at the beginning is never reused — this is why circular queues (using modulo arithmetic on indices) are preferred in production code.

Time complexity: enqueue and dequeue are both O(1) since they only touch the element at 'rear' or 'front' and adjust an index. A circular queue keeps this O(1) behavior while also reusing freed slots, unlike a simple linear array queue.

4. Example

#include <stdio.h>

#define MAX 5

typedef struct Queue {
    int items[MAX];
    int front;
    int rear;
} Queue;

void initQueue(Queue *q) {
    q->front = 0;
    q->rear = -1;
}

int isFull(Queue *q) {
    return q->rear == MAX - 1;
}

int isEmpty(Queue *q) {
    return q->front > q->rear;
}

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue overflow: cannot enqueue %d\n", value);
        return;
    }
    q->items[++(q->rear)] = value;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue underflow: cannot dequeue\n");
        return -1; /* sentinel value */
    }
    return q->items[(q->front)++];
}

int main(void) {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("Dequeued: %d\n", dequeue(&q));
    printf("Dequeued: %d\n", dequeue(&q));

    enqueue(&q, 40);
    printf("Dequeued: %d\n", dequeue(&q));
    printf("Dequeued: %d\n", dequeue(&q));
    printf("Dequeued: %d\n", dequeue(&q)); /* triggers underflow */

    return 0;
}

5. Output

text

Dequeued: 10
Dequeued: 20
Dequeued: 30
Dequeued: 40
Queue underflow: cannot dequeue
Dequeued: -1

6. Key Takeaways

A queue follows FIFO: the first element enqueued is the first one dequeued.
'front' tracks the next element to remove; 'rear' tracks the last element added.
Always guard enqueue against overflow (rear == MAX - 1) and dequeue against underflow (front > rear).
A simple linear array queue wastes freed slots; circular queues reuse them via modulo indexing.
Enqueue and dequeue are both O(1) operations.