Queues

A queue is a linear data structure that follows FIFO order: First In, First Out. The first value inserted is the first value removed.

Think of students standing in a line. The first student in the line is served first. New students join at the back.

Why Do We Need Queues?

A queue is useful when a program must preserve arrival order. The first request, task, or item that arrives should be handled first.

Without a queue, a program may accidentally process newer work before older work. That can be unfair, incorrect, or confusing.

The queue rule is:

first inserted item -> first item removed

That rule appears in many computing problems:

• A printer should usually print earlier jobs before later jobs.
• A CPU scheduler often gives waiting processes a fair turn.
• A keyboard buffer stores key presses in the order they happened.
• A network buffer stores packets or messages until the receiver can process them.
• Breadth-first search must visit older discovered vertices before newer ones.

The queue is not mainly about storing values. Arrays and linked lists can already store values. The queue is about fair ordering.

Everyday Queues

• Ticket counter line: the person who arrives first is served first.
• Bank or hospital waiting line: customers or patients are handled in arrival order, except for special priority systems.
• Printer line: documents wait for their turn.
• Food delivery orders: older accepted orders are usually prepared before newer ones.
• Bus stop: passengers usually board according to the waiting order.

Software Queues

• CPU scheduling: ready processes wait in queues before receiving CPU time.
• Printer spooling: print jobs are stored in a queue.
• Keyboard buffering: keystrokes are processed in the order typed.
• Network buffering: incoming packets wait in queues before processing.
• Breadth-first search: BFS uses a queue to visit nodes level by level.
• Producer-consumer systems: producers add work to a queue; consumers remove work.
• Message queues: distributed systems use queues to pass tasks between services.
• Simulation systems: events waiting to be processed are often stored in queues.

The two fundamental operations are:

• enqueue(x): add x to the back
• dequeue(): remove and return the front value

Other useful operations are:

• front(): read the front value without removing it
• is_empty(): check whether the queue has no values
• is_full(): check whether a fixed array queue has no free space
• display(): print the queue from front to rear

The queue invariant is simple: insert at the rear, remove from the front. Any operation that removes from the rear or inserts in the middle is no longer a simple queue operation.

Queue Trace

Start with an empty queue:

front -> empty <- rear

Apply:

enqueue(10), enqueue(20), enqueue(30), dequeue(), enqueue(40)

The logical queue becomes:

front -> 20 30 40 <- rear

The removed value was 10.

Linear Array Queue

A linear array queue uses:

• front: index of the first item
• rear: index of the last item

Initial state:

front = -1
rear = -1

Array Queue: Function-by-Function

#include <stdio.h>

#define SIZE 5

int queue[SIZE];
int front = -1;
int rear = -1;

#include <stdio.h> allows the program to use printf.

#define SIZE 5 fixes the queue capacity.

int queue[SIZE]; stores the queue values.

front stores the index of the first element. rear stores the index of the last element. When both are -1, the queue is empty.

void enqueue(int value) {
    if (rear == SIZE - 1) {
        printf("Queue Overflow\n");
    } else {
        if (front == -1) {
            front = 0;
        }

        rear++;
        queue[rear] = value;
        printf("%d inserted into queue\n", value);
    }
}

enqueue(value) inserts at the rear. If rear == SIZE - 1, the array is full. If the queue was empty, front becomes 0. Then rear moves forward and the new value is stored at queue[rear].

The first insertion is special. At the start:

front = -1
rear = -1

When the first value is inserted, both ends of the queue must become valid:

front = 0
rear = 0
queue[0] = value

For later insertions, only rear moves forward. The front stays where the oldest item is located.

Example after enqueue(10), enqueue(20), enqueue(30):

index: 0   1   2   3   4
data:  10  20  30
front = 0
rear = 2

If the overflow check is skipped, inserting after rear == SIZE - 1 writes outside the array.

void dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue Underflow\n");
    } else {
        printf("%d deleted from queue\n", queue[front]);
        front++;

        if (front > rear) {
            front = rear = -1;
        }
    }
}

dequeue() removes from the front. It first checks whether the queue is empty. If not, it prints queue[front] and moves front forward. If the last element was removed, both front and rear are reset to -1.

Only front moves during deletion because deletion happens at the front. rear does not move during dequeue().

Example:

Before dequeue:
queue: 10 20 30
front = 0
rear = 2

dequeue prints queue[0] = 10
front becomes 1

logical queue: 20 30

When the last item is removed, front becomes greater than rear. Resetting both to -1 makes the empty state clear and makes the next insertion behave like the first insertion again.

void peek() {
    if (front == -1) {
        printf("Queue is empty\n");
    } else {
        printf("Front element: %d\n", queue[front]);
    }
}

peek() prints the front element without removing it. It does not change front or rear.

Use peek() when a program needs to see the next item to be served but should not remove it yet. For example, a scheduler may inspect the next process before deciding whether it can run.

void displayQueue() {
    if (front == -1) {
        printf("Queue is empty\n");
    } else {
        printf("Queue elements: ");
        for (int i = front; i <= rear; i++) {
            printf("%d ", queue[i]);
        }
        printf("\n");
    }
}

displayQueue() prints from front to rear, because queue order is front-to-rear.

This output order matches service order. The first printed value is the next value that dequeue() would remove.

After one deletion from 10 20 30, front becomes 1, so display starts at index 1 and prints:

20 30

The old value 10 may still physically remain in queue[0], but it is no longer part of the logical queue.

int main(void) {
    enqueue(10);
    enqueue(20);
    enqueue(30);

    displayQueue();
    peek();
    dequeue();

    displayQueue();

    return 0;
}

main(void) tests the queue by inserting three values, showing the queue, reading the front value, deleting one value, and showing the queue again.

The purpose of main(void) is to demonstrate the queue behavior:

• enqueue adds values at the rear.
• displayQueue prints the current service order.
• peek reads the front value.
• dequeue removes the oldest value.
• displayQueue confirms the updated queue.

Array Queue: Full Code

#include <stdio.h>

#define SIZE 5

int queue[SIZE];
int front = -1;
int rear = -1;

void enqueue(int value) {
    if (rear == SIZE - 1) {
        printf("Queue Overflow\n");
    } else {
        if (front == -1) {
            front = 0;
        }

        rear++;
        queue[rear] = value;
        printf("%d inserted into queue\n", value);
    }
}

void dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue Underflow\n");
    } else {
        printf("%d deleted from queue\n", queue[front]);
        front++;

        if (front > rear) {
            front = rear = -1;
        }
    }
}

void peek() {
    if (front == -1) {
        printf("Queue is empty\n");
    } else {
        printf("Front element: %d\n", queue[front]);
    }
}

void displayQueue() {
    if (front == -1) {
        printf("Queue is empty\n");
    } else {
        printf("Queue elements: ");
        for (int i = front; i <= rear; i++) {
            printf("%d ", queue[i]);
        }
        printf("\n");
    }
}

int main(void) {
    enqueue(10);
    enqueue(20);
    enqueue(30);

    displayQueue();
    peek();
    dequeue();

    displayQueue();

    return 0;
}

This version is easy to understand, but it has a limitation: after several dequeues, free spaces at the beginning of the array are not reused. A circular queue fixes that.

Multiple Array Queues

The global version is best for learning one queue. If a program needs multiple queues, global queue, front, and rear are not enough because every operation would affect the same queue.

For multiple queues, place the array, front, and rear inside a struct:

#include <stdio.h>

#define SIZE 5

typedef struct {
    int data[SIZE];
    int front;
    int rear;
} Queue;

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

void enqueue(Queue *q, int value) {
    if (q->rear == SIZE - 1) {
        printf("Queue Overflow\n");
    } else {
        if (q->front == -1) {
            q->front = 0;
        }

        q->rear++;
        q->data[q->rear] = value;
    }
}

void dequeue(Queue *q) {
    if (q->front == -1 || q->front > q->rear) {
        printf("Queue Underflow\n");
    } else {
        printf("%d deleted\n", q->data[q->front]);
        q->front++;

        if (q->front > q->rear) {
            q->front = -1;
            q->rear = -1;
        }
    }
}

Now each queue has its own array, front, and rear:

Queue printQueue;
Queue cpuQueue;

initQueue(&printQueue);
initQueue(&cpuQueue);

enqueue(&printQueue, 10);
enqueue(&cpuQueue, 99);

Use the global version when teaching the basic movement of front and rear. Use the struct version when a program needs more than one queue.

Slow Shifting Queue

Another first attempt stores the front permanently at index 0 and shifts all values left during dequeue:

int dequeue_slow(int arr[], int *n) {
    int value = arr[0];

    for (int i = 0; i < *n - 1; i++) {
        arr[i] = arr[i + 1];
    }

    (*n)--;
    return value;
}

This is correct but inefficient. Every dequeue shifts all remaining elements, so dequeue is O(n). Practical array queues avoid this shifting cost.

Circular Queue

A circular queue lets head and tail wrap around the physical array. This reuses spaces created by dequeue operations.

Remove several values in the interactive queue, add new ones, and watch the rear wrap to a smaller physical index while FIFO order remains unchanged.

The compact implementation below assumes a positive capacity, successful allocation, a valid queue pointer, and a non-null output pointer for dequeue. If any assumption is false, it can dereference invalid memory or compute a remainder with zero. Use it to study circular indexing only. The checked initializer immediately afterward validates capacity and allocation before publishing queue state.

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

typedef struct {
    int *data;
    int head;
    int tail;
    int size;
    int capacity;
} CircularQueue;

void circular_queue_init(CircularQueue *q, int capacity) {
    q->data = malloc(capacity * sizeof(int));
    q->head = 0;
    q->tail = 0;
    q->size = 0;
    q->capacity = capacity;
}

int circular_queue_is_empty(const CircularQueue *q) {
    return q->size == 0;
}

int circular_queue_is_full(const CircularQueue *q) {
    return q->size == q->capacity;
}

int circular_enqueue(CircularQueue *q, int value) {
    if (circular_queue_is_full(q)) {
        return 0;
    }
    q->data[q->tail] = value;
    q->tail = (q->tail + 1) % q->capacity;
    q->size++;
    return 1;
}

int circular_dequeue(CircularQueue *q, int *out) {
    if (circular_queue_is_empty(q)) {
        return 0;
    }
    *out = q->data[q->head];
    q->head = (q->head + 1) % q->capacity;
    q->size--;
    return 1;
}

void circular_queue_free(CircularQueue *q) {
    free(q->data);
    q->data = NULL;
    q->head = 0;
    q->tail = 0;
    q->size = 0;
    q->capacity = 0;
}

For a new or already-freed queue object, initialization can report failure explicitly:

#include <stdint.h>

int circular_queue_init_checked(CircularQueue *q, int capacity) {
    if (q == NULL || capacity <= 0) {
        return 0;
    }
    if ((size_t)capacity > SIZE_MAX / sizeof *q->data) {
        return 0;
    }

    int *data = malloc((size_t)capacity * sizeof *data);
    if (data == NULL) {
        return 0;
    }

    q->data = data;
    q->head = 0;
    q->tail = 0;
    q->size = 0;
    q->capacity = capacity;
    return 1;
}

The caller may enqueue or dequeue only after this function returns 1. On a return value of 0, no queue field has changed. A reusable public dequeue should additionally reject q == NULL, out == NULL, an uninitialized data pointer, or non-positive capacity before reading an element.

The explicit size field makes full and empty states unambiguous. Without size, head == tail could mean either “empty” or “full”, so many implementations reserve one unused slot to distinguish them.

State Trace

For capacity 5, after enqueueing 10, 20, 30, the physical array may be:

index: 0   1   2   3   4
value: 10  20  30  _   _
head = 0, tail = 3, size = 3

After two dequeues and then enqueueing 40, 50, 60, the logical order is 30, 40, 50, 60, but the physical array is split:

index: 0   1   2   3   4
value: 60  _   30  40  50
head = 2, tail = 1, size = 4

Linked Queue

A linked queue can be implemented with only a front pointer. Enqueue traverses to the last node and appends there. Dequeue removes the front node.

This front-only version closely mirrors the singly linked list representation and introduces no separate rear-pointer invariant.

Linked Queue: Function-by-Function

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

stdio.h is needed for printf. stdlib.h is needed for malloc and free.

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

Each node stores one queue element. data stores the value, and next points to the next node in the queue.

Node *createNode(int data) {
    Node *newNode = malloc(sizeof(Node));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }

    newNode->data = data;
    newNode->next = NULL;

    return newNode;
}

createNode(data) allocates memory for a new node, stores the value, sets next to NULL, and returns the node address.

This function keeps node creation separate from queue logic. That makes enqueue easier to read because it can focus on attaching the new node to the queue.

The newNode == NULL check protects the program from using invalid memory if allocation fails.

Node *enqueue(Node *front, int data) {
    Node *newNode = createNode(data);

    if (newNode == NULL) {
        return front;
    }

    if (front == NULL) {
        return newNode;
    }

    Node *current = front;

    while (current->next != NULL) {
        current = current->next;
    }

    current->next = newNode;

    return front;
}

enqueue(front, data) inserts a new node at the rear. If the queue is empty, the new node becomes the front. Otherwise, the function traverses to the last node and links the new node there. The caller must write front = enqueue(front, data);.

There are two cases:

Case 1: empty queue
front == NULL
new node becomes front

Case 2: non-empty queue
walk to the last node
attach newNode after it
return original front

The traversal stops at the last node:

while (current->next != NULL) {
    current = current->next;
}

At that point, current is the rear node. Assigning current->next = newNode; attaches the new node at the end.

Because this front-only version has no separate rear pointer, it must walk through the list for every enqueue.

Node *dequeue(Node *front) {
    if (front == NULL) {
        printf("Queue Underflow\n");
        return NULL;
    }

    Node *temp = front;
    printf("%d deleted\n", temp->data);

    front = front->next;
    free(temp);

    return front;
}

dequeue(front) removes the front node. It saves the old front in temp, moves front to the next node, frees the old node, and returns the updated front.

The order is important:

Node *temp = front;
front = front->next;
free(temp);

The function must save the old front before moving front, otherwise the removed node’s address would be lost and could not be freed.

After removing the final node, front becomes NULL, which correctly represents an empty queue.

void peekQueue(Node *front) {
    if (front == NULL) {
        printf("Queue is empty\n");
    } else {
        printf("Front element: %d\n", front->data);
    }
}

peekQueue(front) prints the front value without deleting it.

This is useful when a program needs to inspect the next item but keep it waiting in the queue.

void displayQueue(Node *front) {
    if (front == NULL) {
        printf("Queue is empty\n");
        return;
    }

    Node *current = front;

    printf("Queue: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }

    printf("\n");
}

displayQueue(front) traverses from front to rear and prints every node.

The traversal uses current so that front remains unchanged. This is the same safe traversal pattern used in linked lists:

Node *current = front;

The function stops when current == NULL, which means it has passed the last node.

void freeQueue(Node *front) {
    while (front != NULL) {
        Node *temp = front;
        front = front->next;
        free(temp);
    }
}

freeQueue(front) releases all remaining nodes before the program exits.

This is memory cleanup, not a queue operation from the abstract data type. It matters in C because nodes created using malloc are not automatically released.

int main(void) {
    Node *front = NULL;

    front = enqueue(front, 10);
    front = enqueue(front, 20);
    front = enqueue(front, 30);

    displayQueue(front);
    peekQueue(front);

    front = dequeue(front);

    displayQueue(front);
    freeQueue(front);

    return 0;
}

main(void) creates an empty queue using Node *front = NULL, enqueues three values, peeks, dequeues once, displays again, and frees the remaining nodes.

Linked Queue: Full Code

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

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

Node *createNode(int data) {
    Node *newNode = malloc(sizeof(Node));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }

    newNode->data = data;
    newNode->next = NULL;

    return newNode;
}

Node *enqueue(Node *front, int data) {
    Node *newNode = createNode(data);

    if (newNode == NULL) {
        return front;
    }

    if (front == NULL) {
        return newNode;
    }

    Node *current = front;

    while (current->next != NULL) {
        current = current->next;
    }

    current->next = newNode;

    return front;
}

Node *dequeue(Node *front) {
    if (front == NULL) {
        printf("Queue Underflow\n");
        return NULL;
    }

    Node *temp = front;
    printf("%d deleted\n", temp->data);

    front = front->next;
    free(temp);

    return front;
}

void peekQueue(Node *front) {
    if (front == NULL) {
        printf("Queue is empty\n");
    } else {
        printf("Front element: %d\n", front->data);
    }
}

void displayQueue(Node *front) {
    if (front == NULL) {
        printf("Queue is empty\n");
        return;
    }

    Node *current = front;

    printf("Queue: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }

    printf("\n");
}

void freeQueue(Node *front) {
    while (front != NULL) {
        Node *temp = front;
        front = front->next;
        free(temp);
    }
}

int main(void) {
    Node *front = NULL;

    front = enqueue(front, 10);
    front = enqueue(front, 20);
    front = enqueue(front, 30);

    displayQueue(front);
    peekQueue(front);

    front = dequeue(front);

    displayQueue(front);
    freeQueue(front);

    return 0;
}

Because this front-only linked queue does not store a rear pointer, enqueue takes O(n) time. A rear-pointer linked queue stores both front and rear, making enqueue O(1).

Multiple Linked Queues

For front-only linked queues, each queue needs its own front pointer:

Node *printFront = NULL;
Node *cpuFront = NULL;

printFront = enqueue(printFront, 10);
cpuFront = enqueue(cpuFront, 99);

printFront = dequeue(printFront);

The nodes reachable from printFront form one queue. The nodes reachable from cpuFront form another queue.

Queue Tradeoffs

Queue Families

• Deque: supports insertion and deletion at both ends.
• Priority queue: removes the highest-priority item instead of the oldest item, usually using a heap.
• Circular queue: fixed-size FIFO buffer with wraparound.
• Blocking queue: used in concurrent programs; dequeue may wait until an item becomes available.
• Double-buffered queue: used in simulations to separate current work from next-step work.

The word “queue” describes the access rule. The implementation can vary widely.

Deque

A deque is a double-ended queue: it supports insertion and deletion at both the front and the back. It can behave like a stack or a queue depending on which ends are used.

Typical uses include:

• sliding-window algorithms
• browser history with forward/backward movement
• task schedulers that sometimes add urgent work to the front

A deque is commonly implemented using a doubly linked list or a circular buffer with careful head/tail arithmetic.

BFS Use

Breadth-first search depends on FIFO order. When a vertex is discovered, it is enqueued. Vertices discovered earlier are processed earlier, so BFS explores all vertices at distance k before vertices at distance k + 1.

void bfs_queue_demo(int start) {
    CircularQueue q;
    circular_queue_init(&q, 100);
    circular_enqueue(&q, start);

    int current;
    while (circular_dequeue(&q, &current)) {
        /* process current, then enqueue its undiscovered neighbors */
    }

    circular_queue_free(&q);
}

Replacing this queue with a stack changes the algorithm into DFS. The data structure controls the traversal order.

FIFO Applications

• BFS and unweighted shortest paths
• task scheduling
• producer-consumer buffers
• printer queues
• keyboard and network input buffering
• simulation event staging

Queues are a natural match whenever fairness by arrival time matters.

Queue Hazards

• Shifting array elements on every dequeue when a circular buffer is intended
• Failing to distinguish full and empty states
• Forgetting modulo arithmetic on head or tail
• Forgetting to store the returned front after linked-list enqueue or dequeue
• Forgetting that enqueue happens at the rear and dequeue happens at the front
• Assuming a priority queue is the same abstraction as a FIFO queue

Queue Costs

Queue Practice

1. Trace this sequence on an empty queue: enqueue(5), enqueue(8), dequeue(), enqueue(2), enqueue(9), dequeue(). Show the final queue and the dequeued values.
2. With capacity 5, enqueue 10, 20, 30, dequeue twice, then enqueue 40, 50, 60. Write head, tail, size, and the physical array after each operation in a circular queue.
3. Implement the front-only linked queue and verify that front becomes NULL after the last dequeue.
4. Explain why a queue, not a stack, is required for BFS shortest paths in an unweighted graph.
5. Explain why a simple linear array queue may report overflow even after some values were dequeued.

Queue Contract

The FIFO rule should be visible through a small interface rather than through the representation’s indices or links:

enqueue(value)      add value at the rear
dequeue(out)        remove the front value into out
front(out)          copy the front without removal
rear(out)           copy the rear without removal
is_empty()          report whether no values are stored
size()              report the number of stored values

An empty dequeue, front, or rear reports failure and leaves the queue unchanged. A returned status separates failure from ordinary integer values such as -1 or 0.

For a size-based circular queue, the representation invariant is:

0 <= size <= capacity
0 <= head < capacity when capacity > 0
0 <= tail < capacity when capacity > 0
the logical value at offset k is data[(head + k) % capacity]
tail == (head + size) % capacity

The last equation makes tail the next insertion slot. Other conventions make tail the current rear element. Both can work, but their formulas cannot be mixed.

Rear-Pointer Queue

A singly linked queue supports constant-time enqueue when it stores both ends. front owns the next node to remove, and rear identifies the final node:

front                              rear
  |                                  |
  v                                  v
[12] -> [27] -> [8] -> [4] -> NULL

The following complete C17 program implements that representation:

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

typedef struct FastQueueNode {
    int value;
    struct FastQueueNode *next;
} FastQueueNode;

typedef struct {
    FastQueueNode *front;
    FastQueueNode *rear;
    size_t size;
} FastQueue;

static bool fast_queue_valid(const FastQueue *queue) {
    if (queue == NULL) {
        return false;
    }
    if (queue->size == 0) {
        return queue->front == NULL && queue->rear == NULL;
    }
    if (queue->front == NULL || queue->rear == NULL ||
        queue->rear->next != NULL) {
        return false;
    }

    size_t count = 0;
    const FastQueueNode *last = NULL;
    for (const FastQueueNode *node = queue->front;
         node != NULL;
         node = node->next) {
        last = node;
        count++;
        if (count > queue->size) {
            return false;
        }
    }
    return count == queue->size && last == queue->rear;
}

static void fast_queue_init(FastQueue *queue) {
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
}

static bool fast_enqueue(FastQueue *queue, int value) {
    assert(fast_queue_valid(queue));
    FastQueueNode *node = malloc(sizeof *node);
    if (node == NULL) {
        return false;
    }

    node->value = value;
    node->next = NULL;
    if (queue->rear == NULL) {
        queue->front = node;
    } else {
        queue->rear->next = node;
    }
    queue->rear = node;
    queue->size++;
    assert(fast_queue_valid(queue));
    return true;
}

static bool fast_dequeue(FastQueue *queue, int *out) {
    assert(fast_queue_valid(queue));
    if (queue->front == NULL || out == NULL) {
        return false;
    }

    FastQueueNode *old_front = queue->front;
    *out = old_front->value;
    queue->front = old_front->next;
    free(old_front);
    queue->size--;

    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    assert(fast_queue_valid(queue));
    return true;
}

static bool fast_front(const FastQueue *queue, int *out) {
    assert(fast_queue_valid(queue));
    if (queue->front == NULL || out == NULL) {
        return false;
    }
    *out = queue->front->value;
    return true;
}

static bool fast_rear(const FastQueue *queue, int *out) {
    assert(fast_queue_valid(queue));
    if (queue->rear == NULL || out == NULL) {
        return false;
    }
    *out = queue->rear->value;
    return true;
}

static void fast_queue_destroy(FastQueue *queue) {
    FastQueueNode *node = queue->front;
    while (node != NULL) {
        FastQueueNode *next = node->next;
        free(node);
        node = next;
    }
    fast_queue_init(queue);
}

int main(void) {
    FastQueue queue;
    fast_queue_init(&queue);

    if (!fast_enqueue(&queue, 10) ||
        !fast_enqueue(&queue, 20) ||
        !fast_enqueue(&queue, 30)) {
        fast_queue_destroy(&queue);
        return EXIT_FAILURE;
    }

    int value;
    if (fast_front(&queue, &value)) {
        printf("front=%d ", value);
    }
    if (fast_rear(&queue, &value)) {
        printf("rear=%d\n", value);
    }
    while (fast_dequeue(&queue, &value)) {
        printf("%d ", value);
    }
    printf("\n");

    fast_queue_destroy(&queue);
    return EXIT_SUCCESS;
}

The singleton-to-empty transition clears rear. Leaving it unchanged would retain a pointer to a freed node. In every non-empty state, rear->next must be NULL, and following links from front must reach rear after exactly size nodes.

The validator traverses the queue and is intended for tests or debug builds. The core enqueue and dequeue operations themselves change only a constant number of links and remain O(1).

Circular Growth

A circular queue can also grow dynamically, but a wrapped buffer cannot be enlarged by changing only its allocation size. Live values must be copied in logical FIFO order:

old physical: [60, 70, 30, 40, 50], head = 2, size = 5
logical:       [30, 40, 50, 60, 70]
new physical: [30, 40, 50, 60, 70, _, _, _, _, _]
new head = 0, new tail = 5

#include <limits.h>
#include <stdint.h>

int circular_queue_grow(CircularQueue *queue) {
    int next_capacity = 8;
    if (queue->capacity > 0) {
        if (queue->capacity > INT_MAX / 2) {
            return 0;
        }
        next_capacity = queue->capacity * 2;
    }

    if ((size_t)next_capacity > SIZE_MAX / sizeof *queue->data) {
        return 0;
    }

    int *new_data = malloc((size_t)next_capacity * sizeof *new_data);
    if (new_data == NULL) {
        return 0;
    }

    for (int offset = 0; offset < queue->size; offset++) {
        int old_index = (queue->head + offset) % queue->capacity;
        new_data[offset] = queue->data[old_index];
    }

    free(queue->data);
    queue->data = new_data;
    queue->capacity = next_capacity;
    queue->head = 0;
    queue->tail = queue->size;
    return 1;
}

The loop is safe when capacity == 0 because a valid zero-capacity queue also has size == 0, so no modulo operation executes. Allocation finishes before any old state is released, preserving the queue if growth fails.

Geometric growth makes enqueue amortized O(1), although a growing enqueue costs O(n). A fixed circular buffer retains strict constant-time operations and predictable storage.

Queue Reference

This complete C17 queue joins the circular-index formulas and failure-safe growth into one implementation. It stores the physical index of the logical front plus the number of active values; the next rear slot is derived rather than maintained separately. Allocation finishes and wrapped values are copied in FIFO order before any old state is released.

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;
    size_t capacity;
    size_t head;
    size_t size;
} DynamicQueue;

static bool dynamic_queue_valid(const DynamicQueue *queue) {
    if (queue == NULL || queue->size > queue->capacity) {
        return false;
    }
    if (queue->capacity == 0) {
        return queue->data == NULL &&
               queue->head == 0 &&
               queue->size == 0;
    }
    return queue->data != NULL && queue->head < queue->capacity;
}

static void dynamic_queue_init(DynamicQueue *queue) {
    queue->data = NULL;
    queue->capacity = 0;
    queue->head = 0;
    queue->size = 0;
}

static void dynamic_queue_destroy(DynamicQueue *queue) {
    free(queue->data);
    dynamic_queue_init(queue);
}

static size_t dynamic_queue_index(const DynamicQueue *queue,
                                  size_t offset) {
    assert(queue->capacity > 0 && offset < queue->size);
    return (queue->head + offset) % queue->capacity;
}

static bool dynamic_queue_grow(DynamicQueue *queue) {
    assert(dynamic_queue_valid(queue));
    size_t next = queue->capacity == 0 ? 8 : queue->capacity * 2;
    if (next < queue->capacity ||
        next > SIZE_MAX / sizeof *queue->data) {
        return false;
    }

    int *new_data = malloc(next * sizeof *new_data);
    if (new_data == NULL) {
        return false;
    }

    for (size_t i = 0; i < queue->size; i++) {
        new_data[i] = queue->data[dynamic_queue_index(queue, i)];
    }

    free(queue->data);
    queue->data = new_data;
    queue->capacity = next;
    queue->head = 0;
    assert(dynamic_queue_valid(queue));
    return true;
}

static bool dynamic_enqueue(DynamicQueue *queue, int value) {
    assert(dynamic_queue_valid(queue));
    if (queue->size == queue->capacity &&
        !dynamic_queue_grow(queue)) {
        return false;
    }

    size_t rear = (queue->head + queue->size) % queue->capacity;
    queue->data[rear] = value;
    queue->size++;
    assert(dynamic_queue_valid(queue));
    return true;
}

static bool dynamic_dequeue(DynamicQueue *queue, int *out) {
    assert(dynamic_queue_valid(queue));
    if (queue->size == 0 || out == NULL) {
        return false;
    }

    *out = queue->data[queue->head];
    queue->head = (queue->head + 1) % queue->capacity;
    queue->size--;
    if (queue->size == 0) {
        queue->head = 0;
    }
    assert(dynamic_queue_valid(queue));
    return true;
}

static bool dynamic_front(const DynamicQueue *queue, int *out) {
    assert(dynamic_queue_valid(queue));
    if (queue->size == 0 || out == NULL) {
        return false;
    }
    *out = queue->data[queue->head];
    return true;
}

static bool dynamic_rear(const DynamicQueue *queue, int *out) {
    assert(dynamic_queue_valid(queue));
    if (queue->size == 0 || out == NULL) {
        return false;
    }

    size_t rear = (queue->head + queue->size - 1) % queue->capacity;
    *out = queue->data[rear];
    return true;
}

int main(void) {
    DynamicQueue queue;
    dynamic_queue_init(&queue);

    for (int value = 10; value <= 40; value += 10) {
        if (!dynamic_enqueue(&queue, value)) {
            dynamic_queue_destroy(&queue);
            return EXIT_FAILURE;
        }
    }

    int value;
    if (!dynamic_dequeue(&queue, &value) ||
        !dynamic_dequeue(&queue, &value) ||
        !dynamic_enqueue(&queue, 50) ||
        !dynamic_enqueue(&queue, 60)) {
        dynamic_queue_destroy(&queue);
        return EXIT_FAILURE;
    }

    if (dynamic_front(&queue, &value)) {
        printf("front=%d ", value);
    }
    if (dynamic_rear(&queue, &value)) {
        printf("rear=%d\n", value);
    }
    while (dynamic_dequeue(&queue, &value)) {
        printf("%d ", value);
    }
    putchar('\n');

    dynamic_queue_destroy(&queue);
    return EXIT_SUCCESS;
}

Resetting head to zero when the queue becomes empty creates one canonical empty state, which simplifies validation and later traces. The queue retains capacity after dequeue; shrinking on every removal would turn alternating enqueue/dequeue workloads into repeated allocation and copying.

Deque Operations

A circular deque uses the same head-and-size model but permits both-end updates:

front index = head
rear index  = (head + size - 1) % capacity, when size > 0

Push-front moves the head backward before writing:

queue->head = (queue->head + queue->capacity - 1) % queue->capacity;
queue->data[queue->head] = value;
queue->size++;

Adding capacity before subtracting avoids unsigned underflow in a size_t implementation. Push-back writes at (head + size) % capacity. Pop-front advances head; pop-back only reduces size. Every operation must check empty or full state before calculating an element index.

A doubly linked list with head and tail is the natural linked deque: next supports the front-to-rear direction and prev makes rear deletion constant time. A singly linked list cannot remove its rear in O(1) because it lacks the predecessor link.

Capacity Policies

When a bounded queue is full, the application must choose an explicit policy:

• reject the new item;
• block until space becomes available;
• overwrite the oldest item;
• grow the buffer.

These are different semantics, not interchangeable implementation details. Overwriting is appropriate for some recent-history or telemetry buffers and unacceptable for a queue of work that must not be lost.

Likewise, a queue of pointers needs an ownership rule. The structure may own enqueued objects, borrow them until dequeue, or transfer ownership into and back out of the queue. clear, failed enqueue, and destruction behavior follow from that decision.

Application Semantics

A producer-consumer buffer decouples arrival time from processing time while preserving order. A first-come scheduler removes the oldest waiting task, whereas round-robin scheduling removes a task, runs one time slice, and returns unfinished work to the rear. An event loop normally appends events created during one callback behind work already waiting, which avoids immediate recursive execution and gives older events a turn.

These uses may share the same representation but not the same full-buffer behavior. Rejecting, blocking, overwriting, and growing are different public contracts. A priority queue is also a different ADT: it chooses by a priority key rather than pure arrival order.

Wrapped Segments

A circular queue is logically one sequence but may occupy two physical array segments. If capacity is 8, head = 6, and size = 5, the logical offsets map as follows:

logical offset:  0  1  2  3  4
physical index:  6  7  0  1  2

The occupied segments are [6,8) followed by [0,3). Many operations can process a whole segment at once rather than calculate modulo for each element. The first segment length is:

first = min(size, capacity - head)
second = size - first

This view is useful for copying during growth, writing queued bytes to an output API that accepts contiguous memory, or exposing a read-only pair of spans. It does not change FIFO order: the end of the physical array is followed by index 0.

An empty queue has no occupied segment even if old bytes remain in its array. A full queue may have one segment when head == 0 or two when head != 0. Logical size—not whether head equals a rear index—distinguishes those states under the size-based invariant.

Batch Enqueue

A batch insertion can copy values into at most two free physical segments. First decide its failure contract. An atomic enqueue_all either accepts every value or leaves the queue unchanged; a streaming form may accept a prefix and return the accepted count.

For the atomic dynamic form:

1. reject count > SIZE_MAX - size;
2. ensure capacity for size + count, growing once if needed;
3. derive the next rear slot (head + size) % capacity;
4. copy to the physical end, then wrap and copy any remainder;
5. publish the new size only after all non-failing copies finish.

Suppose capacity 8 stores four values with head = 5:

occupied indices: 5, 6, 7, 0
next rear:         1

Enqueuing three more values fills indices 1, 2, 3 without moving the older four. If the required size exceeds capacity, growth first linearizes old values to index 0; the new batch then follows them.

As with a dynamic stack, an input pointer into the queue’s own backing array may dangle if growth relocates storage. Forbid overlap or snapshot source values before growth. A public batch contract should not leave this as an accidental implementation detail.

For pointer payloads, copying pointer values is not the same as successfully transferring ownership of every pointed-to object. Publish ownership only for the accepted range, and specify what happens to a partially accepted streaming batch.

Queue Iteration

An iterator should expose logical FIFO order, never raw slot order. With a saved logical offset k, the next physical index is:

(head + k) % capacity

Iteration stops when k == saved_size. A version counter can reject structural mutation after the iterator begins. Without such a check, dequeue can change which item offset 0 means, while growth can release the entire old buffer.

For a linked queue, an iterator can save the current node, but deleting the front may free it. Enqueue preserves existing node addresses and normally appends beyond the iterator’s initial end. The contract must decide whether the iterator sees later arrivals or a snapshot boundary. Saving the original rear node provides a natural stopping point while still avoiding a copied snapshot.

Iteration callbacks should not mutate the same queue unless the API explicitly coordinates that behavior. A callback that dequeues the current item or causes dynamic growth can invalidate traversal state before control returns.

Queue Oracles

A simple array whose active values are always kept from index 0 is a clear test oracle. Its dequeue shifts values and costs O(n), which is acceptable for small randomized tests. Compare enqueue/dequeue status, front, rear, size, and the complete logical sequence after each generated operation.

Bias generation toward empty, singleton, full, wraparound, and growth with two occupied segments. For a deque, generate all four end operations and compare both forward and reverse sequences. For a bounded overwrite policy, compare the displaced value as well as the retained sequence.

Allocation-failure tests should force linked-node creation and circular growth to fail. Under a strong enqueue contract, front, rear, size, capacity, and every queued value remain unchanged. For owned records, use destruction counters to prove that rejected values remain caller-owned, dequeued values transfer exactly once, and clear releases every value still queued.

Choosing Queues

Test empty value-producing operations, the first insertion, singleton removal, exact capacity, one operation beyond capacity, both physical wrap directions, growth while live values straddle the array end, and many alternating enqueue/dequeue cycles. For linked storage, verify that singleton removal clears both pointers. For owned payloads, test enqueue failure, dequeue transfer, clear, and destruction separately.

Queue Challenges

Circular Order

1. Explain why a circular queue can have rear < front while its logical order remains correct.

Wraparound Trace

2. Starting with capacity five, trace enough enqueue and dequeue operations to wrap the queue and become full. Record front, size, and the physical slot of each logical item.

Queue Operations

3. Add size, front, rear, and clear operations to both queue representations and test their empty behavior.
4. Add dynamic growth to the circular queue, then force growth while its logical values wrap across the physical end.
5. Implement all four circular-deque mutations from one head-and-size invariant.
6. Implement a doubly linked deque and verify reciprocal links after every end operation.

Message Ownership

7. Define ownership for dynamically allocated messages and test enqueue failure, dequeue transfer, clear, and destruction.

Overwrite Policy

8. Implement a bounded overwrite queue that returns the displaced oldest value to its caller. State how its contract differs from an ordinary bounded queue.

Iteration and Batches

9. Build an iterator that visits a wrapped queue in logical FIFO order without exposing its two physical segments.
10. Implement batch enqueue with a strong failure guarantee and at most one growth allocation.
11. Implement a fixed circular queue that rejects insertion when full and never allocates after initialization.
12. Investigate a single-producer, single-consumer ring buffer and list the synchronization and memory-order properties absent from an ordinary queue.