Queues and Stacks

Up to this point in the course, we have primarily treated data structures as relatively static storage lockers. We allocate them, we fill them with entities, and we iterate over them to perform some task. Occasionally, we might need to add or remove something from the collection.

However, not all problems take this form. Sometimes our primary goal is to move data between systems, and we need to create appropriate structures to support that work. When our network card receives packets from a multiplayer server, those packets must be streamed into the game engine. When we watch a video, the decoding thread streams frames to the rendering thread. When we listen to Spotify, the application streams decoded samples to the operating system's audio drivers.

In these scenarios, data is not meant to be stored long-term. It is meant to flow. The data structure exists purely as a temporary transit lounge.

When systems interact, the simplest architecture is direct invocation. The system that generates the data instantly calls the system that processes the data:

1void DoWork() {
2  auto* task = PrepareTask();
3  CompleteTask(task); 
4}

This is a tightly coupled design. The CPU is physically locked into executing this exact sequence of instructions. If PrepareTask() takes 1 millisecond, but CompleteTask() takes 50 milliseconds, the pipeline stalls. The system cannot generate another task until the previous one is fully processed.

If a sudden burst of work arrives - like a player firing a machine gun, spawning 50 projectiles in a single frame - our system will lock up entirely while it tries to process every single one sequentially.

To solve this, we separate the generation of data from the processing of data. This requires us to introduce an intermediate data structure that the producer can write data to, and the consumer can read data from:

1void Producer() {
2  auto* task = PrepareTask();
3  Queue.push(task); 
4}
5
6void Consumer() {
7  auto* task = Queue.pop(); 
8  CompleteTask(task);
9}

This decoupling gives us a lot of architectural flexibility:

• The producer and consumer can be in different parts of our application. They can even run on different threads, or they can run on different systems entirely in an environment like a data center.
• We can scale resources independently. If tasks are being produced faster than they are being consumed, we can assign additional threads to consume the tasks.
• We can pause and resume work. If something more important comes up, our consumer can stop working on tasks, and its resources can be reallocated to work on something else. The producer can keep running, building up a backlog of tasks for it to work on when it returns.

In systems engineering, this intermediate data structure is often called a buffer. It acts as a mechanical shock absorber. When a burst of data arrives, the producer simply shoves it into the buffer and can then go back to working on something else. The consumer pulls data out of the buffer at its own steady, sustainable pace, completely insulated from the chaos of the producer.

Our examples will be single-threaded initially - we'll push some tasks onto the collection and then pop them back off again on the same thread - but we'll move to multithreaded examples with producers and consumers running concurrently later in the chapter.

When we push data into a buffer, we eventually need to pull it out. The order in which we retrieve that data fundamentally dictates how our system behaves.

There are two primary paradigms for ordering how data gets added to and removed from a pipeline. We have the FIFO (First-In, First-Out) paradigm, where the first item placed into the buffer is the first item removed. This is like a queue of people waiting at a grocery store checkout. People join the queue at one end, and they leave at the other.

The other paradigm is LIFO (Last-In, First-Out). The last item placed into the buffer is the first item removed. This is like a stack of plates in a cafeteria. Plates are added to the top of the stack, and they're also removed from the top of the stack.

If chronological order matters, we use a queue. For example, rendering input events from a mouse, processing incoming network messages, or streaming a video file. If we instead need to react to the most recent data first, we use a stack. For example, an application's "Undo" feature is expected to act in reverse chronological order, reverting the user's most recent actions first.

If fairness matters, we also prefer queues. As long as the consumer is running, each object in the queue is gradually making its way to the front and will eventually get processed. With a stack, all activity happens at the top; objects at the bottom stay at the bottom. They can be forced to wait a long time before getting processed, and might never get processed at all if new objects are being produced faster than existing objects are being consumed.

The C++ standard library provides built-in tools for both of these buffering patterns via the <queue> and <stack> headers.

Both of these containers provide a highly restricted API. Unlike a std::vector or std::list, we cannot iterate through them, and we cannot arbitrarily access elements in the middle. We can only interact with the precise ends of the collection that the first-in-first-out (std::queue) or last-in-first-out (std::stack) paradigm permits.

Using std::queue

A std::queue enforces the FIFO pattern. We insert elements at the back using push(), and we read the oldest element at the front using front(). To permanently remove the element and advance the queue, we must explicitly call pop():

1#include <queue>
2#include <iostream>
3#include <string>
4
5int main() {
6  std::queue<std::string> Tasks;
7
8  // Producers push to the back
9  Tasks.push("Load Texture");
10  Tasks.push("Parse JSON");
11  Tasks.push("Compile Shader");
12
13  // Consumers pull from the front
14  while (!Tasks.empty()) {
15    // Read the oldest data
16    std::string current = Tasks.front();
17    std::cout << "Executing: " << current << '\n';
18
19    // Destroy the data to advance the queue
20    Tasks.pop();
21  }
22
23  return 0;
24}

1Executing: Load Texture
2Executing: Parse JSON
3Executing: Compile Shader

Using std::stack

A std::stack enforces the LIFO pattern. We insert elements onto the top using push(), and we read that same newest element using top().

Just like the queue, we use pop() to destroy the top element and expose the data sitting beneath it:

1#include <stack>
2#include <iostream>
3
4int main() {
5  std::stack<int> UndoHistory;
6
7  // Pushing state changes
8  UndoHistory.push(10);
9  UndoHistory.push(20);
10  UndoHistory.push(30);
11
12  // We pop backwards through time
13  while (!UndoHistory.empty()) {
14    // Read the newest data
15    int current = UndoHistory.top();
16    std::cout << "Reverting state to: " << current << '\n';
17
18    // 2. Destroy the data to expose the previous state
19    UndoHistory.pop();
20  }
21
22  return 0;
23}

1Reverting state to: 30
2Reverting state to: 20
3Reverting state to: 10

If we look closely at std::stack and std::queue, we might notice they are not real, low-level data structures. They are container adapters. They act as a semantic wrapper around a pre-existing standard library container. They intentionally restrict how we can interact with that underlying container, selectively exposing only the methods that comply with the FIFO or LIFO rules.

By default, both std::stack and std::queue use a std::deque (a double-ended queue) as their underlying physical storage. However, because they are templates, we can tell the adapter to use a different physical layout, such as a std::vector or std::list:

1#include <stack>
2#include <vector>
3#include <list>
4
5int main() {
6  // A stack backed by a contiguous array
7  std::stack<int, std::vector<int>> VectorStack;
8
9  // A stack backed by scattered heap nodes
10  std::stack<int, std::list<int>> ListStack;
11}

To understand why the standard library uses std::deque (double-ended queue) by default, we have to look at the mechanical failures of std::vector when used for data flow.

If we used a std::vector to back our queue, removing the oldest element from the front leaves a physical gap at index 0. To maintain contiguity, the CPU must physically shift every single remaining element one position to the left. If we have a queue of 10,000 tasks, a single pop() triggers 9,999 memory copies - an $O(N)$ memory shift.

Even for a stack, where we only push and pop from the back, std::vector has a flaw: the reallocation spike . When the array hits its capacity, it must allocate a larger block of RAM and painfully copy every existing element over, stalling the CPU.

The std::deque is designed to solve both of these physical problems. Mechanically, it operates like a chunked array, heavily resembling the unrolled linked lists we built in the previous chapter.

Instead of one massive block of contiguous RAM, chunked arrays like std::deque manage multiple smaller, fixed-size chunks of memory, coordinated by a central directory of pointers.

When we push data to the back, it fills the current chunk. If that chunk runs out of space, it doesn't move or copy the old data. It simply allocates a brand new chunk from the OS and adds its pointer to the directory.

When we pop data from the front, it just steps a read pointer forward within the first chunk. When all the elements in that chunk have been read, the entire chunk is deleted.

The Limitations of std::deque

Whilst std::deque is flexible and appropriate for a wide range of scenarios requiring a stack or queue, it brings its own hardware penalties. Because it allocates chunks dynamically, pushing data into a std::queue will inevitably trigger heap allocations when the current chunk is full.

If we are writing a lock-free multithreaded application, or streaming audio where we must deliver a frame every 16 milliseconds, triggering a call to the global allocator at unpredictable times can be disaster. It introduces latency spikes and OS-level thread contention that will completely derail our pipeline.

Throughout this chapter, we'll cover two of the most common alternative implementations of stacks and queues. We'll create a Ring Buffer - a circular queue that can handle an infinite amount of traffic without ever needing to be resized or reallocated. We'll also create a Trieber Stack, which uses the linked-list-based techniques we covered in the previous section to outperform std::stack in multithreaded contexts.

In this lesson, we pivoted from data storage to data flow.

1. We decoupled systems by introducing a buffer, allowing producers and consumers to operate at their own independent speeds.
2. We explored FIFO (Queues) for fairness and chronological streaming, and LIFO (Stacks) for reverse-chronological backtracking.
3. We used the standard library's container adapters (std::queue and std::stack) to enforce these access patterns.
4. We recognized the hardware penalty of shifting arrays, and acknowledged that the dynamic heap allocations of std::deque make standard library queues often unsuitable for real-time or concurrent systems.