Stacks and queues

Stacks and queues are the workhorses of systems programming. Both are lists with deliberately restricted operations: you may add and remove only at the ends, never in the middle. That restriction is their strength. Because only the ends are touched, every operation can be O(1) with a simple array or linked list, and the order in which items come out is guaranteed by the structure itself. A stack returns items in last-in, first-out order, like a pile of plates. A queue returns them in first-in, first-out order, like a line at a counter. Processors keep a call stack in hardware, operating systems schedule tasks from queues, network cards buffer packets in queues, and compilers check brackets and evaluate expressions with stacks.

The NS-4 uses both every second it runs. The radar driver's interrupt handler deposits each detection into a queue, and the main loop takes detections out in the same order to classify them. The maintenance port accepts text commands from a technician's laptop, such as set lane 2 threshold (speed > 15) and (length < 600), and the command parser uses a stack to check that the parentheses balance and to evaluate the condition. Jonah's tasks this week are to replace the radar queue, which occasionally loses detections, and to finish the parser.

The stack ADT

A stack supports push, which adds an item on top; pop, which removes and returns the top item; and peek, also called top, which returns the top item without removing it. Usually there are also is_empty and size. Popping an empty stack is an error, called underflow, and pushing onto a full fixed-size stack is overflow. With an array, the stack keeps an index top that counts the items: push writes at a[top] and increments it; pop decrements it and reads a[top]. Both are O(1). A Python list works directly as a stack using append and pop, which act at the end of the list where they are cheap. With a linked list, push and pop work at the head, also in O(1).

The processor's own call stack is the most important stack of all. Each time a function is called, the processor pushes a frame holding the return address, saved registers and the function's local variables; each return pops it. On the NS-4 the stack lives in a fixed region of RAM, 4 KB for the main loop, and a stack that grows past that region overwrites whatever memory lies beyond it, usually with baffling results days later. Firmware teams guard against this by filling the stack region with a known pattern at start-up and checking during testing how much of the pattern has been overwritten, and by enabling the processor's memory protection so that an overflow causes an immediate, diagnosable fault instead of silent corruption. Lesson 6 shows how recursion consumes this stack.

Using a stack: balanced brackets

Checking that brackets balance is the classic stack application. Read the text from left to right. Push each opening bracket. At each closing bracket, the stack must be non-empty and its top must be the matching opening bracket; pop it. At the end the stack must be empty. The stack works because brackets nest: the most recently opened bracket must be the first one closed, which is exactly last-in, first-out order. A simple counter is not enough once there is more than one kind of bracket, because a counter would accept ( [ ) ].

# Balanced-bracket check for NS-4 maintenance commands
OPEN, CLOSE = "([" + chr(123), ")]" + chr(125)     # chr(123) and chr(125) are the curly braces
PAIRS = dict(zip(CLOSE, OPEN))

def balanced(text):
    stack = []
    for pos, ch in enumerate(text):
        if ch in OPEN:
            stack.append((ch, pos))
        elif ch in PAIRS:
            if not stack or stack[-1][0] != PAIRS[ch]:
                return f"unexpected '{ch}' at position {pos}"
            stack.pop()
    if stack:
        ch, pos = stack[-1]
        return f"'{ch}' at position {pos} is never closed"
    return "balanced"

for cmd in ("set lane 2 threshold (speed > 15) and (length < 600)",
            "set lane 1 window [0, (3 * 60)]",
            "set lane 3 threshold (speed > 15 and (length < 600)",
            "set class map {truck: [7, 8), bus: [4]}"):
    print(f"{balanced(cmd):<38} {cmd}")

balanced                               set lane 2 threshold (speed > 15) and (length < 600)
balanced                               set lane 1 window [0, (3 * 60)]
'(' at position 21 is never closed     set lane 3 threshold (speed > 15 and (length < 600)
unexpected ')' at position 27          set class map {truck: [7, 8), bus: [4]}

Storing the position along with each bracket costs almost nothing and turns a yes-or-no answer into a useful error message, which a technician standing beside a highway in the rain will appreciate. The same pattern, push on open and pop on close, underlies parsing of nested structures generally: HTML and XML tags, JSON objects, nested function calls in a compiler and undo histories in editors.

Using a stack: evaluating expressions

The parser's second job is to evaluate the condition. Expressions written with operators between operands, infix notation, need precedence rules and parentheses. Postfix notation, also called reverse Polish notation, puts each operator after its operands: 3 + 4 × 2 becomes 3 4 2 × +. Postfix needs no parentheses and is evaluated with a single stack: push each number; at each operator, pop two operands, apply the operator and push the result. Edsger Dijkstra's shunting-yard algorithm converts infix to postfix using a second stack for operators. Stack-based evaluation is how many calculators, the Java virtual machine and Python's own bytecode interpreter work.

The queue ADT

A queue supports enqueue, which adds an item at the back; dequeue, which removes and returns the item at the front; and peek. With a linked list, enqueue at the tail and dequeue at the head are both O(1), as lesson 4 showed. With an ordinary Python list, dequeue by pop(0) is O(n), because every remaining element shifts, so a long-running queue built that way slows down as it grows. Python's collections.deque is a double-ended queue built from linked blocks of 64 elements that supports O(1) operations at both ends; use it whenever you need a queue in Python.

The circular buffer

The array implementation of a queue that firmware engineers use everywhere is the circular buffer, also called a ring buffer. It keeps a fixed array of capacity N and two indexes: head, where the next item will be removed, and tail, where the next item will be written. Enqueue writes at tail and advances it; dequeue reads at head and advances it. When an index reaches the end of the array it wraps around to 0, so the queue chases itself around the ring, reusing slots as they are freed. There is no shifting and no allocation, and both operations are O(1).

The one subtle point is telling a full buffer from an empty one, since in both cases head equals tail. There are three common solutions. Keep a separate count of items. Leave one slot always empty, so the buffer is full when advancing tail would make it equal head; this wastes one slot but needs no shared count. Or let head and tail run as free-running counters and compute the slot as the counter modulo N, so the number of items is simply tail − head; if N is a power of two, the modulo is a cheap bitwise AND and unsigned overflow of the counters is harmless. The NS-4 uses the third method for the radar queue.

/* Single-producer, single-consumer ring buffer for radar detections (NS-4) */
#include <stdint.h>
#include <stdbool.h>

#define RQ_SIZE 64u                        /* must be a power of two */
typedef struct { uint32_t t_us; int16_t range_cm, speed_cms; } det_t;

static det_t rq[RQ_SIZE];
static volatile uint32_t rq_head, rq_tail; /* free-running counters */
static volatile uint32_t rq_dropped;

void radar_isr_push(det_t d)               /* called only from the interrupt */
{
    if (rq_tail - rq_head == RQ_SIZE) { rq_dropped++; return; }   /* full: count the loss */
    rq[rq_tail & (RQ_SIZE - 1)] = d;
    rq_tail++;                             /* publish after the data is written */
}

bool radar_pop(det_t *out)                 /* called only from the main loop */
{
    if (rq_tail == rq_head) return false;  /* empty */
    *out = rq[rq_head & (RQ_SIZE - 1)];
    rq_head++;
    return true;
}

This design solves Jonah's lost-detection bug. The old radar queue was a linked list whose nodes were allocated in the interrupt and freed in the main loop, and both sides updated a shared count; occasionally an interrupt arrived in the middle of the main loop's update and a detection vanished. In the ring buffer, only the interrupt writes tail and only the main loop writes head, and each side writes the data before publishing the index, so no lock is needed as long as the processor does not reorder those memory writes. On this single-core microcontroller it does not, and the volatile keyword stops the compiler from caching the indexes in registers. On a multicore processor, the same idea needs explicit memory barriers or C11 atomic operations. When the queue is full, the interrupt counts a dropped detection instead of overwriting old data silently, so a test can show whether the queue is large enough.

Other queue variants

A deque, or double-ended queue, allows adding and removing at both ends, so it can act as a stack or a queue; it is also the basis of the sliding-window algorithms used to keep running maxima and minima over recent sensor readings. A queue can also be built from two stacks: push onto an in stack, and pop from an out stack, refilling out by moving everything from in whenever out is empty. Each item is moved at most once, so the amortized cost per operation is O(1), a neat result used in functional programming languages where arrays cannot be modified in place. Finally, a priority queue removes items in order of priority rather than arrival; it is not a list at all but a heap, the subject of lesson 9.