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.

Real-Life Uses

• 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.

Computer Uses

• 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.

Operation 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: Beginner Version

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() {
    enqueue(10);
    enqueue(20);
    enqueue(30);

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

    displayQueue();

    return 0;
}

main() 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() 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() {
    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.

#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;
}

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 version is very close to basic singly linked list code, so it is easier for beginners.

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 beginner 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() 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 beginner linked queue does not store a rear pointer, enqueue takes O(n) time. A more optimized linked queue stores both front and rear, making enqueue O(1).

Multiple Linked Queues

For linked queues, each queue only needs its own front pointer in the beginner version:

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.

Array vs Linked Queue

Variants

• 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.

Uses

• 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.

Pitfalls

• 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

Costs

Exercises

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 beginner 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.