C Queues

A queue is a linear data structure that stores items in the order they arrive and lets you retrieve them in that same order. It follows the FIFO rule — First In, First Out — just like a line of people waiting at a checkout counter: whoever joins the line first is the first one served. C has no built-in queue type, so you build one yourself using an array or a linked list, which is exactly why understanding queues deeply also teaches you a lot about pointers, memory, and abstract data types in C.

Overview: How a Queue Works

A queue supports two core operations: enqueue (add an item to the back/rear of the queue) and dequeue (remove an item from the front of the queue). Unlike a stack (LIFO), a queue never lets you touch anything except the two ends: you always insert at the rear and always remove from the front.

In C, there are two common ways to implement a queue:

• Array-based queue — a fixed-size block of contiguous memory (a plain C array or a block from malloc) with two index variables, front and rear, that track the current boundaries of the queue.
• Linked-list-based queue — a chain of dynamically allocated nodes connected by pointers, with a front pointer and a rear pointer so both ends can be reached in O(1) time.

With a plain array-based queue, a naive implementation just increments front and rear forever and never reuses freed slots. That wastes memory because the slots before front become permanently unusable once rear passes the end of the array, even though the queue may currently hold far fewer items than its capacity. The fix is a circular queue: when rear (or front) reaches the last index, it wraps back around to index 0 using the modulo operator (%). This lets a fixed-size array be reused indefinitely as long as the number of items currently stored never exceeds its capacity.

A linked-list queue avoids the fixed-capacity problem entirely: nodes are allocated with malloc as needed and freed with free when dequeued, so the queue can (in theory) grow until memory runs out. The tradeoff is the overhead of dynamic allocation and the extra memory used by each node’s pointer field.

Internally, a circular queue needs a way to distinguish an empty queue from a full one, since front == rear can mean either state once the indices wrap. A common solution is to keep an explicit count field alongside the indices, which is what the circular queue example below does.

Syntax

There is no queue keyword in C. You define your own struct and functions. A typical array-based queue looks like this:

#define CAPACITY 100

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

void initQueue(Queue *q);
int  isFull(Queue *q);
int  isEmpty(Queue *q);
void enqueue(Queue *q, int value);
int  dequeue(Queue *q);

Part	Meaning
items[CAPACITY]	The backing storage for queued elements.
front	Index of the element that will be removed next.
rear	Index of the last inserted element.
count	How many elements are currently stored; used to detect full/empty without ambiguity in a circular queue.
enqueue(q, value)	Adds value to the rear of the queue.
dequeue(q)	Removes and returns the value at the front of the queue.

A linked-list-based queue instead uses a node struct plus two pointers:

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

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

Examples

Example 1: A Simple (Linear) Array-Based Queue

This first example shows the most basic array queue, without wraparound, so you can see the limitation it has.

#include <stdio.h>

#define CAPACITY 5

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

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

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

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

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

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty, cannot dequeue\n");
        return -1;
    }
    int value = q->items[q->front];
    q->front++;
    q->count--;
    return value;
}

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);
    enqueue(&q, 50);
    enqueue(&q, 60);
    enqueue(&q, 70);

    return 0;
}

Output:
Enqueued 10
Enqueued 20
Enqueued 30
Dequeued: 10
Dequeued: 20
Enqueued 40
Enqueued 50
Queue is full, cannot enqueue 60
Queue is full, cannot enqueue 70

Notice the problem: after dequeuing twice, only 3 items remain in the queue, so there is plenty of logical room. But rear only ever increases and never wraps, so once it reaches index 4 (CAPACITY - 1), enqueue reports the queue as full even though the two slots vacated at the front (indices 0 and 1) are sitting unused. This is exactly the limitation a circular queue solves.

Example 2: A Circular Queue (Solving the Wraparound Problem)

By using the modulo operator when advancing front and rear, the same fixed array can be reused indefinitely.

#include <stdio.h>

#define CAPACITY 5

typedef struct {
    int items[CAPACITY];
    int front;
    int rear;
    int count;
} CircularQueue;

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

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

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

void enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full, cannot enqueue %d\n", value);
        return;
    }
    q->rear = (q->rear + 1) % CAPACITY;
    q->items[q->rear] = value;
    q->count++;
    printf("Enqueued %d\n", value);
}

int dequeue(CircularQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty, cannot dequeue\n");
        return -1;
    }
    int value = q->items[q->front];
    q->front = (q->front + 1) % CAPACITY;
    q->count--;
    return value;
}

int main(void) {
    CircularQueue 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);
    enqueue(&q, 50);
    enqueue(&q, 60);
    enqueue(&q, 70);
    enqueue(&q, 80);

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

    return 0;
}

Output:
Enqueued 10
Enqueued 20
Enqueued 30
Dequeued: 10
Dequeued: 20
Enqueued 40
Enqueued 50
Enqueued 60
Enqueued 70
Queue is full, cannot enqueue 80
Dequeued: 30
Dequeued: 40
Dequeued: 50
Dequeued: 60
Dequeued: 70

This time, thanks to the modulo wraparound, the 5-slot array actually holds five real items at once — 30, 40, 50, 60, and 70 — reusing the two slots freed by the earlier dequeues instead of leaving them permanently stranded. Only once count genuinely reaches CAPACITY does enqueue(&q, 80) get rejected, and the closing loop drains all five items in the correct order. Compare that to Example 1, which reported “full” after storing only 3 real items because it never reused the space freed by dequeues.

Example 3: A Dynamic Queue Using a Linked List

A linked-list queue removes the fixed-capacity limit entirely by allocating a new node for every enqueued value.

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

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

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

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

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

void enqueue(LinkedQueue *q, int value) {
    Node *node = malloc(sizeof(Node));
    if (node == NULL) {
        printf("Allocation failed\n");
        exit(1);
    }
    node->data = value;
    node->next = NULL;

    if (isEmpty(q)) {
        q->front = node;
        q->rear = node;
    } else {
        q->rear->next = node;
        q->rear = node;
    }
    printf("Enqueued %d\n", value);
}

int dequeue(LinkedQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty, cannot dequeue\n");
        return -1;
    }
    Node *temp = q->front;
    int value = temp->data;

    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return value;
}

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

    enqueue(&q, 100);
    enqueue(&q, 200);
    enqueue(&q, 300);
    enqueue(&q, 400);

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

    enqueue(&q, 500);

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

    return 0;
}

Output:
Enqueued 100
Enqueued 200
Enqueued 300
Enqueued 400
Dequeued: 100
Dequeued: 200
Enqueued 500
Dequeued: 300
Dequeued: 400
Dequeued: 500

Each call to enqueue allocates one node with malloc and links it after the current rear. Because rear is tracked directly, appending is O(1) — there is no need to walk the whole list. Each dequeue unlinks the front node, copies out its value, and calls free on it, so memory grows and shrinks with actual usage instead of being capped at a fixed CAPACITY.

Under the Hood: What Happens Step by Step

For an array-based (circular) queue, each operation does the following:

• enqueue(q, value): check whether the queue is already full; if not, advance rear (with (rear + 1) % CAPACITY for a circular queue), write value into items[rear], and update the bookkeeping. All of this is plain array indexing, so it runs in constant time with no hidden allocation.
• dequeue(q): check whether the queue is empty; if not, read items[front], advance front the same way, and update the bookkeeping. The old slot’s value is not erased — it is simply considered “stale” and will be overwritten by a future enqueue.

For a linked-list queue:

• enqueue: malloc asks the heap allocator for a new block of memory sized for one Node. The new node’s next is set to NULL, then the current rear‘s next pointer is redirected to the new node, and finally rear itself is updated to point at the new node. If the queue was empty, front and rear both point at the single new node.
• dequeue: the node pointed to by front is remembered in a temporary pointer, front is advanced to front->next, the value is copied out of the old node, and then free returns that node’s memory to the heap allocator. If the list becomes empty, rear must also be reset to NULL, otherwise it becomes a dangling pointer pointing at freed memory.

Common Mistakes

Mistake 1: Forgetting to reset rear to NULL when a linked queue becomes empty

Wrong code:

int dequeue(LinkedQueue *q) {
    Node *temp = q->front;
    int value = temp->data;
    q->front = q->front->next;
    free(temp);
    return value;
}

If this empties the queue, q->front correctly becomes NULL, but q->rear still points at the node that was just freed. The next enqueue call will write through q->rear->next, which is a use-after-free — undefined behavior that may crash or silently corrupt memory. The corrected version (as shown in Example 3) explicitly checks if (q->front == NULL) q->rear = NULL; after advancing front.

Mistake 2: Using a linear (non-circular) array queue and calling it “full” too early

As Example 1 demonstrated, a linear queue whose rear never wraps reports itself full once rear hits CAPACITY - 1, even if many earlier slots were freed by dequeues. Always use (index + 1) % CAPACITY for a reusable, fixed-size array queue.

Mistake 3: Confusing front == rear for empty vs. full

In a circular queue, both an empty queue and a full queue can have front == rear — this alone is ambiguous. Relying only on comparing front and rear without a separate count (or without sacrificing one array slot as a deliberate gap) will misreport queue state. Keep an explicit count field, as Example 2 does.

Mistake 4: Not checking malloc‘s return value

If the heap is exhausted, malloc returns NULL. Writing to node->data without checking for NULL first dereferences a null pointer and crashes the program. Always check the return value before using it, as Example 3 does.

Best Practices

• Always check isFull before enqueue and isEmpty before dequeue — never assume the caller has already checked.
• Prefer a circular buffer over a linear array when the queue has a known maximum size and you want O(1) enqueue/dequeue without dynamic allocation.
• Prefer a linked-list queue when the maximum number of elements is unknown or highly variable, accepting the small overhead of per-node allocation.
• Keep an explicit count (or sacrifice one slot) in circular queues to unambiguously distinguish full from empty.
• Always free every node you dequeue from a linked queue, and reset both front and rear to NULL when the queue becomes empty, to avoid dangling pointers.
• Store elements by value for small, simple types (like int); for larger structs, consider storing pointers to heap-allocated data instead of copying whole structs in and out of the queue.
• If a queue must be shared between threads, add proper synchronization (e.g. a mutex) — none of the implementations shown here are thread-safe.
• Write a freeQueue function that drains and frees every remaining node before your program exits, to avoid memory leaks.

Practice Exercises

• Exercise 1: Extend the circular queue from Example 2 with a peek(q) function that returns the value at the front of the queue without removing it. Make sure it correctly reports an error when the queue is empty.
• Exercise 2: Write a freeQueue(LinkedQueue *q) function for the linked-list queue in Example 3 that repeatedly dequeues (and frees) every remaining node, leaving front and rear both NULL. Call it at the end of main and verify with valgrind (or by inspection) that no memory is leaked.
• Exercise 3: Implement a queue of char * (strings) instead of int, using the linked-list approach. Think carefully about who owns each string’s memory: does the queue copy the string with strdup, or does it just store the caller’s pointer? Write your enqueue/dequeue functions to match your chosen ownership rule.

Summary

• A queue is a FIFO (First In, First Out) data structure: items are added at the rear and removed from the front.
• C has no built-in queue; you implement one with an array (fixed capacity) or a linked list (dynamic capacity).
• A linear array queue wastes space because rear never wraps around; a circular queue fixes this by wrapping indices with the modulo operator.
• An explicit count field resolves the ambiguity between “empty” and “full” when front == rear in a circular queue.
• A linked-list queue allocates a node per enqueue and frees it per dequeue, trading fixed-size limits for allocation overhead.
• Always reset rear (and front) to NULL when a linked queue empties, and always check malloc‘s return value, to avoid dangling pointers and crashes.