Data Structure - Queue

A queue is a linear data structure that follows the First In First Out (FIFO) principle. It can be compared to the real-life scenario of queuing to buy tickets — the person who queues first gets served first.

Queue Concept and Principle

Queue — FIFO Principle Illustration
Front
front
→
20
30
Rear
rear
← dequeueenqueue →

enqueue: insert at rear | dequeue: delete from front | Complexity O(1)

FIFO verification: enqueue 10→20→30, dequeue 10→20→30 (First In First Out)

A queue only allows insertion at one end (rear) and deletion at the other end (front).

This is exactly the opposite of the stack's LIFO principle.

Array Implementation of Queue

Example

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

#define MAX 100

struct Queue {
    int items[MAX];
    int front;   /* front pointer: points to the first element */
    int rear;    /* rear pointer: points to the next insertion position */
};

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

bool isEmpty(struct Queue* q) {
    return q->front == q->rear;
}

bool isFull(struct Queue* q) {
    return q->rear == MAX;
}

/* enqueue: add element at rear */
void enqueue(struct Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full!\n");
        return;
    }
    q->items[q->rear++] = value;  /* write at rear, then move rear back */
    printf("enqueue: %d\n", value);
}

/* dequeue: remove element from front */
int dequeue(struct Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    return q->items[q->front++];  /* return element at front, then move front back */
}

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

    enqueue(&q, 10);  /* enqueue: 10 */
    enqueue(&q, 20);  /* enqueue: 20 */
    enqueue(&q, 30);  /* enqueue: 30 */

    printf("dequeue: %d\n", dequeue(&q));  /* output: dequeue: 10 (FIFO) */
    printf("dequeue: %d\n", dequeue(&q));  /* output: dequeue: 20 */
    printf("dequeue: %d\n", dequeue(&q));  /* output: dequeue: 30 */
    return 0;
}

A queue implemented with a normal array has a "false overflow" problem: as enqueue and dequeue continue, front and rear keep moving toward the end of the array, and even if there are plenty of empty spaces at the front of the array, they cannot be reused. The solution is to use aCircular Queue。

Circular Queue

Circular Queue — modulo operation for pointer wraparound

Key formulas for circular queue

enqueue: items[rear] = value; rear = (rear + 1) % MAX;

dequeue: value = items[front]; front = (front + 1) % MAX;

Empty check: front == rear | Full check: (rear + 1) % MAX == front

Running example (capacity=5, max 4 items): enqueue 10→20→30→40, dequeue 10→20, enqueue 50→60 → 60 stored at index 0 (wraparound), perfectly reusing freed space.

A circular queue logically treats the array as a ring structure with the head and tail connected, and implements pointer wraparound via modulo arithmetic.

Example

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

#define MAX 5 /* deliberately set a small capacity to make the circular effect easier to observe */

struct CircularQueue {
    int items[MAX];
    int front;  /* front index */
    int rear;   /* rear index (next insertion position) */
};

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

/* empty check: front and rear coincide */
bool isEmpty(struct CircularQueue* q) {
    return q->front == q->rear;
}

/* full check: (rear + 1) % MAX == front Note: the circular queue deliberately leaves one position empty to distinguish empty from full */
/* enqueue: write at rear, then move rear forward circularly */
bool isFull(struct CircularQueue* q) {
    return (q->rear + 1) % MAX == q->front;
}

"Circular queue is full!
void enqueue(struct CircularQueue* q, int value) {
    if (isFull(q)) {
        printf(/* modulo for wraparound */\n");
        return;
    }
    q->items[q->rear] = value;
    q->rear = (q->rear + 1) % MAX;  "enqueue: %d (rear=%d)
    printf(/* dequeue: return element at front, then move front forward circularly */\n", value, q->rear);
}

/* Dequeue: return the element at front, then front moves forward cyclically */
int dequeue(struct CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Circular queue is empty!\n");
        return -1;
    }
    int value = q->items[q->front];
    q->front = (q->front + 1) % MAX;  /* Modulo operation implements wraparound */
    return value;
}

int main() {
    struct CircularQueue q;
    initQueue(&q);

    enqueue(&q, 10);  /* Enqueue: 10 (rear=1) */
    enqueue(&q, 20);  /* Enqueue: 20 (rear=2) */
    enqueue(&q, 30);  /* Enqueue: 30 (rear=3) */
    enqueue(&q, 40);  /* Enqueue: 40 (rear=4) — capacity 5, max 4 elements */

    printf("Dequeue: %d\n", dequeue(&q));  /* Dequeue: 10 (front=1) */
    printf("Dequeue: %d\n", dequeue(&q));  /* Dequeue: 20 (front=2) */

    enqueue(&q, 50);  /* Enqueue: 50 (rear=0 — wraps around to the beginning!) */
    enqueue(&q, 60);  /* Enqueue: 60 (rear=1) */

    printf("Remaining elements: ");
    while (!isEmpty(&q)) {
        printf("%d ", dequeue(&q));
    }
    printf("\n");  /* Output: Remaining elements: 30 40 50 60 */
    return 0;
}

Application Scenarios of Queue

Application ScenariosDescription
Breadth-First Search (BFS)Traverse graph nodes level by level; a queue is needed to store the "to-be-visited" nodes
Operating System Task SchedulingThe CPU allocates time slices in the order tasks arrive
Print Task QueueMultiple computers share one printer; print requests are queued and processed in submission order
Message QueueIn distributed systems, messages produced by producers are passed to consumers through a queue
Other Extensions