Stacks, queues and ring buffers

A stack gives you back the most recent thing you put in (LIFO); a queue gives you back the oldest (FIFO). Both are tiny interfaces — push, pop, peek — and the interesting part is making every operation O(1) without wasting memory. This lesson uses the standard adaptors, then builds the structure behind a fast queue: the ring buffer.

1. The standard adaptors

std::stack, std::queue and std::priority_queue are adaptors: thin wrappers that restrict an underlying container to one discipline.

#include <print>
#include <queue>
#include <stack>

int main() {
    std::stack<int> s;
    std::queue<int> q;
    for (int i = 1; i <= 3; ++i) {
        s.push(i);
        q.push(i);
    }
    std::println("stack top {}, queue front {} back {}", s.top(), q.front(), q.back());
    s.pop();
    q.pop();
    std::println("after pop: stack top {}, queue front {}", s.top(), q.front());
}

So std::stack<int, std::vector<int>> is fine (vector has everything a stack needs), but std::queue<int, std::vector<int>> fails to compile as soon as you call pop() — vector has no pop_front, because removing the first element of a contiguous array means shifting all the others.

pop() returns void. Read with top()/front() first, then pop — a design that keeps pop exception-safe. And calling top(), front() or pop() on an empty adaptor is undefined behaviour; check empty().

2. Why not a vector?

A stack maps perfectly onto a vector: push and pop at the back are amortized O(1). A queue doesn't: you add at the back and remove at the front, and v.erase(v.begin()) moves every remaining element. Draining n elements that way costs n + (n−1) + … + 1 = O(n²).

The fix is to stop moving data and move an index instead.

3. The ring buffer

Keep the elements in one array and remember where the front is. Popping advances head; pushing writes at head + size. When an index runs off the end of the array it wraps around to slot 0:

Full or empty? If you track head and tail (one past the back), then head == tail both when the buffer is empty and when it's full. Two standard fixes: keep a size count (what we'll do), or never fill the last slot.

Power-of-two capacity. If the capacity is a power of two, % cap becomes & (cap - 1) — a single AND instead of a division, and it stays correct when the index wraps around the type's range too. std::has_single_bit and std::bit_ceil in <bit> help.

Worked example: a fixed-capacity ring

A fixed ring is what you'd use for a producer/consumer queue or a UART receive buffer on a microcontroller — no allocation after construction.

#include <array>
#include <bit>
#include <cstddef>
#include <optional>
#include <print>

template <class T, std::size_t N>
    requires(std::has_single_bit(N))
class FixedRing {
public:
    bool push(const T& v) {
        if (size_ == N) return false;           // full: caller decides what to drop
        buf_[(head_ + size_) & (N - 1)] = v;
        ++size_;
        return true;
    }
    std::optional<T> pop() {
        if (size_ == 0) return std::nullopt;     // empty
        T v = buf_[head_];
        head_ = (head_ + 1) & (N - 1);
        --size_;
        return v;
    }
    std::size_t size() const { return size_; }

private:
    std::array<T, N> buf_{};
    std::size_t head_ = 0, size_ = 0;
};

int main() {
    FixedRing<int, 4> r;
    for (int i = 1; i <= 5; ++i) std::println("push {} -> {}", i, r.push(i));
    while (auto v = r.pop()) std::print("{} ", *v);
    std::println("");
    for (int i = 6; i <= 8; ++i) r.push(i);     // wraps around the array
    while (auto v = r.pop()) std::print("{} ", *v);
    std::println("");
}

Note the std::array<T, N> buf_{} — it default-constructs N objects up front. That's fine for int, but a general container must not construct objects in empty slots (T may have no default constructor, or be expensive). The build task uses raw storage, like your own vector did: std::allocator<T>, std::construct_at, std::destroy_at.

4. Growing a ring

When a growable ring is full, allocate twice the capacity and move the elements across — in queue order, starting at slot 0 of the new buffer, then reset head to 0. Copying slot-for-slot would be wrong whenever the queue is wrapped:

Doubling gives amortized O(1) push by the same argument as for a vector, and a queue whose size stays bounded never allocates again — the ring just keeps cycling through its slots.

Faded example — your turn

Fill in back() and pop() for a ring with members data_, head_, size_, cap_ (a power of two, elements built with construct_at):

T& back() { return data_[/* ??? */]; }
void pop() {
    /* ??? */                 // end the front element's lifetime
    head_ = /* ??? */;
    --size_;
}

5. Deque: the standard's answer

std::deque is not a ring. It's a list of fixed-size blocks plus a small index of block pointers, so it can grow at both ends without moving elements — push_back and push_front never invalidate references to existing elements (they do invalidate iterators). That's why it's the default container for std::queue. A single ring buffer is more compact and cache-friendly, but growth moves everything.

6. Monotonic stacks and deques (preview)

Two patterns turn up in many problems.

Next greater element. For each value, find the first larger value to its right. A stack holding indices of values still waiting for their answer is always decreasing; each new value resolves every smaller waiting value:

#include <print>
#include <stack>
#include <vector>

std::vector<int> next_greater(const std::vector<int>& v) {
    std::vector<int> out(v.size(), -1);
    std::stack<std::size_t> waiting;           // indices; their values decrease
    for (std::size_t i = 0; i < v.size(); ++i) {
        while (!waiting.empty() && v[waiting.top()] < v[i]) {
            out[waiting.top()] = v[i];
            waiting.pop();
        }
        waiting.push(i);
    }
    return out;
}

int main() {
    for (int x : next_greater({2, 7, 3, 5, 4, 6, 8})) std::print("{} ", x);
    std::println("");
}

Each index is pushed once and popped at most once, so the whole thing is O(n) even though there's a loop inside a loop.

Sliding-window maximum. Keep a deque of indices whose values decrease from front to back: drop from the back anything smaller than the new value (it can never be a maximum again), drop from the front anything that left the window. The front is always the window's maximum — O(n) total.

#include <deque>
#include <print>
#include <vector>

int main() {
    std::vector<int> v{1, 3, -1, -3, 5, 3, 6, 7};
    std::size_t k = 3;
    std::deque<std::size_t> dq;
    for (std::size_t i = 0; i < v.size(); ++i) {
        while (!dq.empty() && v[dq.back()] <= v[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() + k <= i) dq.pop_front();
        if (i + 1 >= k) std::print("{} ", v[dq.front()]);
    }
    std::println("");
}

Summary

• Stack = LIFO (vector is ideal), queue = FIFO (needs O(1) at both ends).
• std::stack/std::queue adapt a container; pop() returns nothing; empty access is UB.
• A ring buffer moves indices, not data: element i at (head + i) & (cap - 1).
• Track size to tell full from empty; keep capacity a power of two.
• Grow by doubling and re-lay the elements in queue order with head = 0.
• Monotonic stack/deque: each element enters and leaves once → O(n).