Queues

A queue in an array has eight cells, yet it turns an item away with only two waiting. Watch where the other six went.

⋯11bool enqueue(struct queue *q, int v)12{13    if (q->tail == CAP)14        return false;15    q->items[q->tail] = v;16    q->tail++;17    return true;18}19 20int dequeue(struct queue *q)21{22    int v = q->items[q->head];23    q->head++;24    return v;25}⋯27int main(void)28{29    struct queue q = { .head = 0, .tail = 0 };30    for (int v = 1; v <= 3; v++)31        enqueue(&q, v);32    printf("served");33    for (int v = 4; v <= 9; v++) {34        int x = dequeue(&q);35        printf(" %d", x);36        if (!enqueue(&q, v))37            printf("\n%d refused with %d of %d cells in use\n", v, q.tail - q.head, CAP);38    }39    return 0;40}

First in, first out

A printer takes jobs in the order they were sent. The first job sent is printed first, the next one after it, and a new job waits behind all the others. A structure that hands things back in the order they arrived is a queue. First in, first out.

A queue has three operations:

• enqueue: add an item at the back, the tail.
• dequeue: take the item at the front, the head, and return it.
• peek: read the item at the head without taking it.

A stack does all its work at one end. A queue works at both: items join at one end and leave at the other. It is not a stack read backwards: in a stack the item that leaves is the newest; in a queue it is the oldest.

The code and its cost

An array with two indices

#define CAP 8

struct queue {
    int items[CAP];
    int head, tail;
};

head is the index of the oldest item. tail is the index of the next free cell, one past the newest item. The items waiting are the cells from head up to tail − 1, so there are tail − head of them, and the queue is empty when head equals tail. sizeof (struct queue) is 40 bytes: 32 for the array, 4 each for head and tail. In the clip, q sits at 0x7fc0, so items[i] is at 0x7fc0 + 4i, head at 0x7fe0 and tail at 0x7fe4.

bool enqueue(struct queue *q, int v)
{
    if (q->tail == CAP)
        return false;
    q->items[q->tail] = v;
    q->tail++;
    return true;
}

int dequeue(struct queue *q)
{
    int v = q->items[q->head];
    q->head++;
    return v;
}

enqueue writes into the cell at tail, then moves tail on. dequeue reads the cell at head, then moves head on. Like pop in Stacks, dequeue erases nothing: after the first dequeue in the clip, items[0] still holds 1. It is simply behind the head, and no longer in the queue. dequeue also trusts its caller: on an empty queue (head equal to tail) it would read a cell that holds no item, and with head at CAP it would read items[8], past the end of the array, which is undefined behaviour. The caller must check first.

Each operation is a fixed few steps: a comparison and two writes for enqueue, a read and a write for dequeue, one read for peek. How many items wait makes no difference.

Why it runs out of room

head and tail only ever move right. When tail reaches 8, enqueue refuses every new item, however many cells lie unused behind head. In the clip that happens with two items waiting: cells 0 to 5 hold old numbers that no one will read again, and the queue cannot reach them. They come back only if the queue empties completely and both indices are put back to 0, and a queue that is never empty never gets them back.

The program prints the refusal itself:

served 1 2 3 4 5 6
9 refused with 2 of 8 cells in use

Shifting instead

One fix keeps the oldest item always in cell 0: dequeue takes items[0] and then moves every other item one cell to the left.

int dequeue(struct queue *q)
{
    int v = q->items[0];
    for (int i = 1; i < q->tail; i++) {
        q->items[i - 1] = q->items[i];
        moves++;
    }
    q->tail--;
    return v;
}

Now no cell is ever lost, and the same arrivals are never refused. But each dequeue moves every item left behind it. In queue-shift.c, the same program with this dequeue and a counter, three items wait at every dequeue, so each one moves two items, and the six dequeues move 12 in all:

served 1 2 3 4 5 6
12 moves

With n items waiting, a dequeue costs n − 1 moves. The two-index queue never moves an item; the shifting queue never loses a cell. Circular queues get both, by letting head and tail wrap round to cell 0.

A queue of nodes

On the nodes of Singly linked lists, a queue has no capacity to run out of. The head of the list is the head of the queue, and the queue keeps a second pointer to the last node:

struct lqueue {
    struct node *head, *tail;
};

void enqueue(struct lqueue *q, int v)
{
    struct node *n = malloc(sizeof *n);
    if (n == NULL)
        exit(1);
    n->key = v;
    n->next = NULL;
    if (q->tail == NULL)
        q->head = n;
    else
        q->tail->next = n;
    q->tail = n;
}

A new node joins after the last one. The tail pointer is what makes that fast: without it, every enqueue would have to walk the whole list from the head to find the last node, a step for every item waiting. With it, enqueue is a fixed few steps. dequeue unlinks the head node, as removing the first node in Removing from a linked list does, and frees it. When it takes the last node, it must clear tail as well, or tail would keep the address of a freed node.

1#include <stdio.h>2#include <stdlib.h>3 4struct node {5    int key;6    struct node *next;7};8 9struct lqueue {10    struct node *head, *tail;11};12 13void enqueue(struct lqueue *q, int v)14{15    struct node *n = malloc(sizeof *n);16    if (n == NULL)17        exit(1);18    n->key = v;19    n->next = NULL;20    if (q->tail == NULL)21        q->head = n;22    else23        q->tail->next = n;24    q->tail = n;25}26 27int dequeue(struct lqueue *q)28{29    struct node *n = q->head;30    int v = n->key;31    q->head = n->next;32    if (q->head == NULL)33        q->tail = NULL;34    free(n);35    return v;36}37 38int main(void)39{40    struct lqueue q = { NULL, NULL };41    for (int v = 1; v <= 3; v++)42        enqueue(&q, v);43    printf("served");44    while (q.head != NULL) {45        int x = dequeue(&q);46        printf(" %d", x);47    }48    printf("\n");49    return 0;50}

The linked queue never refuses an item while malloc can find memory. It pays with a malloc per enqueue, a free per dequeue, and a next pointer in every node: 32 bytes of heap for each int on this platform.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic queue.c -o queue
./queue

It prints the two lines above. queue-shift.c prints 12 moves after the served line, and queue-linked.c prints served 1 2 3.

Worked example

By hand. On an empty array queue of 8 cells: enqueue 5, enqueue 8, dequeue, enqueue 2, dequeue, enqueue 6.

The dequeues return 5 and then 8, in the order they arrived. Two items wait, 2 and 6, in cells 2 and 3, and cells 0 and 1 are behind head.

Empty and refused. Start empty, enqueue 8 items and dequeue all 8. head and tail are both 8, so the queue is empty, and yet the next enqueue is refused: tail is at the end. Every cell is free and none can be used.

Shifting a long queue. With 1,000 items waiting, one dequeue of the shifting version moves 999 of them. Serving them all moves 999 + 998 + … + 1 + 0 = 499,500 items, where the two-index queue moves none.

The fix to come. If tail went back to cell 0 after cell 7, the empty-and-refused queue above would take its next item in cell 0. That is the ring buffer of Circular queues.

Where it’s used

Printers and servers. A print queue holds documents in the order they were sent; a web server keeps requests waiting in a queue until a worker is free.

Messages between parts of a program. One part puts messages in a queue and another takes them out in the same order, so neither has to wait for the other.

Searching a graph. Breadth-first search (19.2) visits a maze or a network one layer at a time by keeping the places still to visit in a queue, and walking a tree level by level (12.4) works the same way.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.