1.4.2 - Stacks, queues and circular buffers

Removal order defines a stack or queue

A stack uses last in, first out (LIFO). Push adds an item at the top; pop removes and returns the top item. If A, B and C are pushed, the next removals are C, B and A. Peek reads the next removable item without removing it. Undo history can use a stack because the latest action is undone before earlier actions. The idea also appears in nested function calls, where the most recent unfinished call returns first.

A queue uses first in, first out (FIFO). Enqueue adds at the rear; dequeue removes and returns from the front. Enqueuing A, B and C gives removals A, B and C. This preserves a first-come waiting order, such as print jobs accepted under a simple FIFO policy. A priority policy would require additional behaviour; FIFO alone does not move an urgent job ahead of older jobs.

The removal rule is independent of representation. A stack or queue may be implemented using a fixed array, a changing list, or linked nodes. A fixed implementation can become full; removing from an empty structure is underflow. An attempt to add beyond a fixed capacity is overflow. The contract must say whether an operation returns failure, raises an error or follows another policy. Silently returning old unused data is not a valid empty-operation result.

Maintain a stack's top and capacity

A stack's pointer convention must be stated before tracing it. Here top is the number of active items and the index of the next free slot, not the last occupied index. With capacity 3, top = 0 means empty and top = 3 means full. Active items occupy storage indices 0 through top - 1; the next pop reads index top - 1.

Push first checks space, writes at storage[top], then increments top. Pop first checks top > 0, decrements top, then returns storage[top]. Reading storage[top] before decrementing would read a free slot. Old values may remain in unused backing slots after a pop; top decides which values are active.

def push(storage, top, value):
    if top == len(storage):
        return top, False
    storage[top] = value
    return top + 1, True

def pop(storage, top):
    if top == 0:
        return top, None, False
    top -= 1
    return top, storage[top], True

storage = [None, None, None]
top = 0
top, ok = push(storage, top, "A")
top, ok = push(storage, top, "B")
top, item, ok = pop(storage, top)
print(item, top)
top, ok = push(storage, top, "C")
print(storage[:top])

The output is B 1, then ["A", "C"]. Both functions assume 0 <= top <= len(storage) and return the new top explicitly. Failure leaves storage and top unchanged. None is accompanied by a Boolean success flag so a legitimate stored None need not be confused with failure. A peek under this convention reads storage[top - 1] only if top is positive, without changing top.

To traverse active stack data for display without popping it, read from top - 1 down to 0 for top-first order, or 0 up to top - 1 for bottom-first order, and label the chosen direction. Traversal is not removal. Another valid representation uses top = -1 for empty and top as the last occupied index; its full condition and update order differ. Never combine that convention's condition with this convention's code.

Separate a queue's front and rear

A queue needs to track both ends. In this linear queue, front is the next occupied index to remove, and rear is the next free index for insertion. Start front = rear = 0 in an array of capacity four. Enqueue writes at rear then increments rear. Dequeue checks front < rear, reads storage[front], then increments front. Equal pointers mean empty under this linear convention.

After enqueuing A, B and C, the active sequence occupies indices 0,1,2, with front = 0 and rear = 3. Dequeuing twice returns A then B and leaves front = 2, rear = 3. Enqueuing D writes index 3 and gives rear = 4. The active queue is C,D, but this simple implementation cannot accept another item because rear has reached capacity. Indices 0 and 1 are now unused, yet continually increasing rear never reuses them.

One repair is to shift active entries to the front, which takes work and must update both pointers. Another is a circular queue, which reuses vacant indices by wrapping. Neither solution changes FIFO. A fixed queue operation must check space/emptiness before accessing the array. Dequeue on an empty queue returns the declared failure result without reading storage, even if old values remain there.

To traverse the active linear queue without removing it, visit indices front through rear - 1. In a linked queue, front identifies the first node and rear the last node, rather than the next free array index. Enqueue links a new tail; dequeue advances the head. Removing its only node must set both node references to NULL. These are alternative representations with explicitly different pointer meanings.