Queues

Introduction

A queue is a line at a ticket counter: people join at the rear and are served from the front, so the first in is the first out (FIFO). The operations are enqueue (join), dequeue (leave from the front), peek and is_empty, all O(1).

Whenever work should be handled in the order it arrived, a queue is the right tool. The interesting part is storing it, because a queue that simply marches along an array soon runs off the end while free cells lie behind it.

How it works

A linked queue

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

typedef struct node {
    int value;
    struct node *next;
} Node;

typedef struct {
    Node *front, *rear;
} Queue;

void enqueue(Queue *q, int x) {
    Node *n = malloc(sizeof(Node));
    n->value = x;
    n->next = NULL;
    if (q->rear == NULL) q->front = n;
    else q->rear->next = n;
    q->rear = n;
}

int dequeue(Queue *q) {   // the caller checks that the queue is not empty
    Node *n = q->front;
    int x = n->value;
    q->front = n->next;
    if (q->front == NULL) q->rear = NULL;
    free(n);
    return x;
}

int main(void) {
    Queue q = {NULL, NULL};
    for (int i = 1; i <= 3; i++) enqueue(&q, i * 100);
    while (q.front != NULL) printf("served %d\n", dequeue(&q));
    return 0;
}

A linked queue keeps two pointers: front for dequeuing and rear for enqueuing. It never becomes full. One special case: when the last node leaves, rear must become NULL too, or it would point to freed memory.

Queues are used for printer jobs, for messages between programs, and in breadth-first search on graphs, later in this course.

Syntax

int rear = (q->front + q->count) % CAPACITY;   // the next free cell
q->items[rear] = x;
q->count++;

q->front = (q->front + 1) % CAPACITY;          // after removing the front item
q->count--;

Example

A simple array queue moves front right after every dequeue, and soon reaches the end of the array even though the cells at the start are free. A circular queue wraps round to index 0 with %:

#include <stdio.h>
#define CAPACITY 4

typedef struct {
    int items[CAPACITY];
    int front;   // index of the first item
    int count;   // how many items are in the queue
} Queue;

int enqueue(Queue *q, int x) {
    if (q->count == CAPACITY) return 0;   // full
    int rear = (q->front + q->count) % CAPACITY;
    q->items[rear] = x;
    q->count++;
    return 1;
}

int dequeue(Queue *q, int *out) {
    if (q->count == 0) return 0;   // empty
    *out = q->items[q->front];
    q->front = (q->front + 1) % CAPACITY;
    q->count--;
    return 1;
}

int main(void) {
    Queue q;
    q.front = 0;
    q.count = 0;
    int x;
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    dequeue(&q, &x);
    printf("served %d\n", x);
    enqueue(&q, 4);
    enqueue(&q, 5);
    while (dequeue(&q, &x)) printf("served %d\n", x);
    return 0;
}

The struct keeps front (the index of the first item) and count. The rear is computed: (front + count) % CAPACITY. Watch the last two enqueues: after index 3 comes index 0 again, reusing the cell that 1 left.

Keeping count makes full and empty easy to tell apart. With only front and rear, both a full and an empty queue can have front == rear, which is why some textbooks leave one cell always empty.

Line by line

1. Queue keeps the array, the index of the first item and how many items there are.
2. enqueue refuses when count equals the capacity, and computes the rear from front and count.
3. dequeue refuses when count is 0, copies out the front item and moves front round the ring.
4. main enqueues 1, 2 and 3, then dequeues 1 and prints it.
5. Enqueuing 4 fills index 3, and enqueuing 5 wraps round to index 0, the cell that 1 left.
6. The last loop serves everything else in arrival order.

Expected result

served 1
served 2
served 3
served 4
served 5

In the real world

Printers, web servers and message systems all queue work so that a burst of requests can wait its turn. Keyboards and network cards use exactly this ring-shaped buffer, because its size is fixed and nothing has to move.

Common mistakes

• Forgetting % CAPACITY, so the rear runs off the end of the array.
• In a linked queue, not resetting rear when the queue becomes empty.
• Mixing up the ends: enqueue at the rear, dequeue at the front.

Best practices

• Keep a count unless you have a reason not to, because it makes the tests simple.
• Reset rear when a linked queue becomes empty.
• Test a run that wraps round the end of the array at least twice.

Summary

A queue serves items in arrival order. A circular array reuses its cells by wrapping indexes with %, and a linked queue keeps a pointer at each end, so both operations stay O(1).

Mark lesson complete