Queues and ring buffers

First in, first out

A queue serves items in the order they arrived: FIFO, first in first out, like a line at a counter. Its two operations are enqueue, which adds an item at the back, and dequeue, which removes the item at the front. Queues show up wherever work arrives faster than it can be handled, or has to be handled in order: print jobs, web requests waiting for a worker, messages between programs, packets arriving at a network card, and the breadth-first search you will meet in the graphs module.

Why a list is a poor queue

A dynamic array handles one end cheaply, but a queue uses both. Enqueueing with append is O(1), but dequeuing from the front with pop(0) shifts every remaining item, which is O(n). A queue that processes a million items that way does on the order of n²/2 moves.

A linked list with head and tail pointers gives O(1) at both ends, but pays an allocation and a probable cache miss per item. The structure real systems use instead is a ring buffer.

The ring buffer

A ring buffer, also called a circular buffer, is a fixed array plus two numbers: head, the index of the oldest item, and size, how many items are stored. The back of the queue is not stored separately; it is computed as (head + size) % capacity. The remainder makes the array behave as if its end were joined to its start.

The trace above runs it with 4 slots:

• Enqueuing writes at (head + size) % 4 and increments size.
• Dequeuing reads buf[head], then moves head forward with (head + 1) % 4. Nothing shifts. The slot the old item occupied simply becomes free.
• When the back reaches the last slot, the next enqueue wraps to slot 0, reusing space that dequeues freed. In the trace, E lands in A's old slot.

Every operation is a few arithmetic operations and one memory access: O(1), with no allocation after the first. Items never move once written, which is exactly the property hardware needs.

When the capacity is a power of two, % capacity can be replaced with & (capacity − 1), a single AND instruction, the same trick hash tables use to pick a slot. Many implementations insist on power-of-two sizes for that reason.

Full or empty?

Some ring buffers store head and tail indexes instead of head and size. That creates an ambiguity: when the queue is empty, tail equals head, and when it is completely full, tail has wrapped all the way around and equals head again. Implementations resolve it in one of two ways: keep a separate count, as the trace does, or never fill the last slot, so that "full" means tail is one behind head. Both are common; the second wastes one slot but keeps the state to two indexes, which matters when two threads share the buffer.

When it fills up

A fixed-size queue can be full, and what happens then is a design decision, not an accident:

• Grow. A growable ring buffer allocates a larger array, usually double, and copies the items in queue order, from head to the end of the old array and then from its start up to head. That straightens out any wrap-around. Java's ArrayDeque and Rust's VecDeque work this way. Python's collections.deque uses a different layout, a linked list of fixed-size blocks, which gives the same O(1) operations at both ends.
• Block. The producer waits until the consumer makes room. This is backpressure: a slow consumer automatically slows the producer down.
• Drop or overwrite. Audio and video buffers drop data rather than fall behind, and a log that keeps the last N events overwrites the oldest one.
• Reject. A server returns an error, such as HTTP 503, instead of queuing work it can't finish in time.

An unbounded queue sounds convenient, but under sustained overload it grows until the process runs out of memory. Most real systems choose a bound and one of the policies above.

Ring buffers in real systems

Because a ring buffer never allocates and never moves its items, it is the standard way for two independent parties to pass a stream of data:

• Network cards write incoming packets into receive rings in main memory, and the operating system reads them out in order.
• Linux's io_uring interface uses two rings shared between a program and the kernel, one for submitted I/O requests and one for completions, so that programs can do I/O without a system call for every operation.
• Audio systems fill a ring with samples ahead of the sound card reading them.
• The LMAX Disruptor, a Java library built for a financial exchange, uses a pre-allocated ring buffer to pass millions of messages per second between threads.

When one thread only enqueues and another only dequeues, a ring buffer can even be made safe without locks, because each index is written by only one side. The expert level of this track builds on exactly that idea.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Queues and ring buffers from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

function next_greater_elements(nums):
    n = length(nums)
    ans = array of size n filled with -1
    stack = empty_stack()  // stores indices with decreasing values
    for i from 0 to n - 1:
        while not stack.empty() and nums[stack.top()] < nums[i]:
            idx = stack.pop()
            ans[idx] = nums[i]
        stack.push(i)
    return ans

#include <vector>
 
std::vector<int> nextGreaterElements(const std::vector<int>& nums) {
    int n = static_cast<int>(nums.size());
    std::vector<int> ans(n, -1), st;
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[st.back()] < nums[i]) {
            ans[st.back()] = nums[i];
            st.pop_back();
        }
        st.push_back(i);
    }
    return ans;
}

import java.util.*;
 
public class StackQueueSolver {
    public static int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && nums[st.peekLast()] < nums[i]) {
                ans[st.pollLast()] = nums[i];
            }
            st.offerLast(i);
        }
        return ans;
    }
}

def next_greater_elements(nums: list[int]) -> list[int]:
    ans = [-1] * len(nums)
    stack: list[int] = []
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            ans[stack.pop()] = x
        stack.append(i)
    return ans

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.