Queues

A queue is a linear data structure that follows the FIFO principle — First In, First Out. Picture a line of people waiting at a checkout counter: the first person to join the line is the first person to be served. Elements are added at the rear (enqueue) and removed from the front (dequeue). Queues show up everywhere: task scheduling, breadth-first search, print spoolers, and message buffers.

Core Operations

enqueue — add an element to the rear of the queue
dequeue — remove and return the element at the front
peek/front — look at the front element without removing it
isEmpty — check whether the queue has any elements
isFull — for a fixed-size implementation, check whether there is room left

The Naive Array Implementation Wastes Space

A first attempt at an array-based queue keeps a front index and a rear index. enqueue writes at rear and increments it; dequeue reads at front and increments it. The problem: front only ever moves forward, so once rear reaches the end of the array, the queue reports itself as full even though slots at the beginning have been vacated by earlier dequeues. The fix is a circular buffer.

Circular Buffer Indexing

A circular (ring) buffer treats the array as if its end wraps around to its beginning. Instead of always incrementing an index, we increment it modulo the array size: index = (index + 1) % capacity. This lets the queue reuse slots that were freed by earlier dequeues, so a fixed-size array can hold a continuous stream of enqueue/dequeue operations without ever needing to shift elements.

#include <stdio.h>

#define CAPACITY 5

typedef struct {
    int items[CAPACITY];
    int front;
    int rear;
    int count; /* number of elements currently stored */
} CircularQueue;

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

int isEmpty(const CircularQueue *q) {
    return q->count == 0;
}

int isFull(const CircularQueue *q) {
    return q->count == CAPACITY;
}

int enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        return 0;
    }
    q->rear = (q->rear + 1) % CAPACITY; /* wrap around */
    q->items[q->rear] = value;
    q->count++;
    return 1;
}

int dequeue(CircularQueue *q, int *outValue) {
    if (isEmpty(q)) {
        return 0;
    }
    *outValue = q->items[q->front];
    q->front = (q->front + 1) % CAPACITY; /* wrap around */
    q->count--;
    return 1;
}

int main(void) {
    CircularQueue q;
    int value;

    initQueue(&q);
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);

    dequeue(&q, &value);
    printf("Dequeued: %d\n", value); /* 1 */

    /* Because the buffer wraps around, we can keep enqueueing
       even though "rear" would otherwise run off the array. */
    enqueue(&q, 4);
    enqueue(&q, 5);
    enqueue(&q, 6);

    while (dequeue(&q, &value)) {
        printf("Dequeued: %d\n", value);
    }

    return 0;
}

Note

Tracking `count` explicitly (instead of trying to infer full/empty purely from `front == rear`) avoids an ambiguous case where a full queue and an empty queue would otherwise look identical.

Implementing a Queue with a Linked List

A linked-list queue keeps two pointers: front (the head, where we dequeue) and rear (the tail, where we enqueue). Both operations run in O(1) because we never need to walk the list.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;
    Node *rear;
} LinkedQueue;

void initLinkedQueue(LinkedQueue *q) {
    q->front = NULL;
    q->rear = NULL;
}

int lqIsEmpty(const LinkedQueue *q) {
    return q->front == NULL;
}

int lqEnqueue(LinkedQueue *q, int value) {
    Node *node = malloc(sizeof(Node));
    if (node == NULL) {
        return 0;
    }
    node->data = value;
    node->next = NULL;

    if (q->rear == NULL) {
        q->front = node;
        q->rear = node;
    } else {
        q->rear->next = node;
        q->rear = node;
    }
    return 1;
}

int lqDequeue(LinkedQueue *q, int *outValue) {
    if (lqIsEmpty(q)) {
        return 0;
    }
    Node *old = q->front;
    *outValue = old->data;
    q->front = old->next;
    if (q->front == NULL) {
        q->rear = NULL; /* queue is now empty */
    }
    free(old);
    return 1;
}

int main(void) {
    LinkedQueue q;
    int value;

    initLinkedQueue(&q);
    lqEnqueue(&q, 100);
    lqEnqueue(&q, 200);
    lqEnqueue(&q, 300);

    while (lqDequeue(&q, &value)) {
        printf("Dequeued: %d\n", value);
    }

    return 0;
}

Tip

Circular buffers are not just a classroom exercise — they are the standard technique behind real audio buffers, network packet buffers, and producer/consumer queues in operating systems.

Array (Circular) vs Linked List

Aspect	Circular array queue	Linked-list queue
Maximum size	Fixed at creation	Limited only by available memory
Memory overhead	None per element	Extra pointer per node
Cache locality	Good (contiguous memory)	Poorer (nodes scattered on the heap)
Resizing	Requires reallocation + re-copy	Grows naturally, one node at a time

Warning

Forgetting to wrap indices with the modulo operator is the single most common bug when implementing a circular queue by hand — always use `(index + 1) % CAPACITY`, never a plain increment.