Stacks, Queues & Deques

A stack, queue, or deque is best understood as a restriction on an abstract sequence—not as a particular class or node layout. A stack exposes one end and therefore removes the most recently inserted item (LIFO). A queue inserts at the back and removes from the front (FIFO). A deque exposes both ends. Those rules determine legal histories; array, linked, and blocked representations determine cost, locality, capacity, and invalidation.

Three contracts over one sequence #

Let the abstract state be $s=\langle x_0,\ldots,x_{n-1}\rangle$.

The contract is incomplete until empty/full behavior is stated. top on empty may be a violated precondition, an exception, an optional result, or a blocking wait. A bounded push may reject, overwrite the oldest element, block, or apply backpressure upstream. These policies produce different ADTs even if the successful path is identical.

A stack needs one changing boundary #

A fixed or dynamic array can store the stack in data[0:size), with the top at data[size-1]. Push constructs at size; pop destroys there and decrements size. Both are $O(1)$ except that a dynamic array occasionally reallocates, making one push $O(n)$ and invalidating borrowed element addresses.

A singly linked list can instead make the head the top. Push allocates and prepends; pop unlinks the head. These are worst-case $O(1)$ after allocation, and other node addresses remain stable, but allocation and pointer chasing usually make scans less local. A stack does not expose arbitrary scan or indexing, so choose by latency, capacity, failure, and lifetime requirements rather than by folklore.

Stacks turn recursive control state into explicit data. Depth-first search, parsing, undo histories, and interpreters push frames containing the information needed to resume. An explicit stack avoids call-stack overflow and can impose a memory limit, but it does not remove the underlying $O(d)$ space requirement for depth $d$.

std::vector<Node*> work{root};
while (!work.empty()) {
    Node* node = work.back();
    work.pop_back();
    visit(*node);
    // Push in reverse if visitation order matters.
    for (auto it = node->children.rbegin(); it != node->children.rend(); ++it)
        work.push_back(*it);
}

A queue needs two independently moving ends #

Using a plain array and shifting every remaining element after pop is $Theta(n)$ per removal. A queue instead tracks logical head and tail positions. In a linked queue, head points to the next removal and tail to the insertion point; both must be updated when the last element leaves or the first enters.

In a circular buffer of capacity $m$, physical slot for logical offset $i$ is

$$\mathop{\mathrm{slot}}(i)=(head+i)\bmod m.$$

With explicit size, the invariant is $0\le size\le m$, the front is data[head], and the next insertion slot is (head + size) % m. Push increments size; pop advances head = (head + 1) % m and decrements size. Wrapping changes physical order but not the abstract FIFO sequence.

template<class T, std::size_t Capacity>
class RingQueue {
    static_assert(Capacity > 0);
    std::array<std::optional<T>, Capacity> data;
    std::size_t head = 0, size_ = 0;
public:
    bool try_push(T value) {
        if (size_ == Capacity) return false;
        data[(head + size_) % Capacity].emplace(std::move(value));
        ++size_;
        return true;
    }
    std::optional<T> try_pop() {
        if (size_ == 0) return std::nullopt;
        auto value = std::move(data[head]);
        data[head].reset();
        head = (head + 1) % Capacity;
        --size_;
        return value;
    }
};

Two-index designs face an ambiguity: head == tail can mean empty or full after wrap. Resolve it deliberately by storing a size, reserving one unusable slot, or adding a phase/generation bit. Never guess full/empty from equal indices without specifying which encoding is used.

For continuously increasing unsigned counters, physical access can use counter % capacity while occupancy is tail - head, provided wraparound arithmetic and maximum distance are proven safe. This separates logical progress from physical reuse and is useful in concurrent rings, but atomics do not by themselves establish whether an element is initialized and visible.

A deque is not necessarily one contiguous allocation #

A deque supports push_front, push_back, pop_front, and pop_back in constant time under its contract. A circular buffer can do this by moving either logical endpoint. A linked list can do it with head/tail links. A blocked deque keeps a map of fixed-size chunks, avoiding whole-buffer relocation while retaining locality within each chunk.

The C++ std::deque guarantees constant-time insertion/removal at either end and random access, but it is not required to store all elements contiguously. Its iterator/reference invalidation rules differ from std::vector and from linked lists. Do not pass &deque[0] as if it began one flat C array.

Representation and policy are separate decisions #

A bounded queue is often an architectural control surface. Blocking propagates latency; rejecting loses or reroutes work; overwriting loses the oldest data; unbounded growth trades immediate success for eventual memory pressure. The queue cannot choose this business policy invisibly.

Concurrency requires a history, not just atomic counters #

Calling a type “thread-safe” does not say enough. Specify:

• single-producer/single-consumer, multi-producer, multi-consumer, or externally locked;
• which operation is the linearization point;
• when a producer publishes initialized storage and a consumer acquires it;
• how full/empty waiting handles cancellation, shutdown, timeouts, and spurious wakeups;
• whether retained references remain valid after another thread pops;
• how destroyed or reused slots avoid ABA and use-after-free.

In a condition-variable queue, wait in a predicate loop under the mutex. Shutdown must be part of the predicate or blocked threads can wait forever. In a lock-free ring, per-slot sequence numbers or an equivalent proven protocol usually carry publication state; merely making head and tail atomic is insufficient.

Where the ADTs appear #

• Breadth-first search uses a FIFO queue so vertices are processed in nondecreasing discovery distance in an unweighted graph.
• Depth-first search uses a LIFO stack, explicit or implicit, to postpone siblings while descending.
• Dijkstra's algorithm needs a priority queue, not a FIFO queue, because the next item is chosen by minimum tentative distance.
• Expression evaluation often uses an operand stack and an operator stack; precedence rules determine when operators pop.
• Event loops use queues, but priority, fairness, coalescing, deadlines, and backpressure make the production contract richer than FIFO alone.

Review and failure diagnostics #

1. Is order actually LIFO, FIFO, double-ended, or priority-based?
2. What happens on empty and, if bounded, on full?
3. Is a claimed $O(1)$ operation worst-case or amortized, and does it allocate?
4. Does the ring distinguish full from empty after wrap?
5. Are object construction and destruction aligned with slot publication and reuse?
6. What references/iterators survive growth, pop, or block-map changes?
7. Can one logical wrapped batch require two physical spans?
8. Is backpressure behavior visible to upstream callers and shutdown paths?
9. Are compound operations such as read-then-pop atomic when clients require them to be?
10. Does concurrency include safe lifetime and memory ordering, not only atomic indices?

Exercises #

1. Give an abstraction function for a ring queue whose head=6, size=4, and capacity is 8.
2. Explain why BFS becomes depth-first-like if its FIFO work queue is replaced by a stack.
3. Design the full/empty encoding for a ring that deliberately wastes one slot.