Queues & Circular Queues

Topics Covered:
31. Queue Abstract Data Type (FIFO) & Operations • Linear Array Queue & The "False Overflow / Drift" Problem • Linked List Queue Implementation • 32. Circular Queue (Ring Buffer) & Modulo Arithmetic • Wrap-Around State Tracking & Kernel Ring Buffers • Two-Stack Queue Paradigm (Potential Method Proof) • Production Implementations

While stacks govern depth-first backtracking through Last-In, First-Out (LIFO) access, queues enforce fair, sequential scheduling through First-In, First-Out (FIFO) semantics. Elements enter at the rear and exit from the front, mirroring pipeline buffers and operating system task schedulers. However, naive linear array implementations suffer from pointer drift and false capacity exhaustion. This chapter analyzes the FIFO abstraction, diagnoses the false overflow failure mode, formalizes modulo-arithmetic circular ring buffers, details two-stack queue emulation with a rigorous potential method amortized proof, and explores lock-free kernel buffer architectures.

• Define the FIFO Queue Abstract Data Type and enforce boundary invariants for front and rear pointers.
• Diagnose the "false overflow" (pointer drift) problem in linear array queues and quantify the $O(n)$ latency penalty of element shifting.
• Implement circular queues (ring buffers) using modulo arithmetic to achieve $O(1)$ wrap-around insertions and deletions.
• Compare full/empty state disambiguation strategies: explicit counter tracking versus the reserved empty slot invariant.
• Prove the amortized $O(1)$ complexity of the two-stack queue using the formal Physicist's Potential Method.
• Analyze the architectural role of circular ring buffers in Linux kernel kfifo and high-throughput network packet ring buffers.

A Queue is a restricted-access linear sequence governed by the First-In, First-Out (FIFO) discipline:

• Elements are inserted strictly at the Rear (Tail) via Enqueue.
• Elements are removed strictly from the Front (Head) via Dequeue.
• The element that has spent the longest duration in the queue is always the next one to be serviced.

Interactive Simulations:
Step through FIFO queue behavior live in the Interactive Queue Enqueue Simulator and the Interactive Queue Dequeue Simulator.

Consider a static array of capacity $C=5$ with two pointer offsets: front and rear.

State Progression Demonstrating Drift

Why Linear Arrays Fail for Queues:

The condition rear == capacity - 1 evaluates to true ($4==4$), so the linear queue reports an Overflow Error and rejects the item, even though $60\%$ of the physical array is vacant!

To reuse the vacated slots at the front of a linear array, the implementation would have to shift all remaining elements back to index 0 on every dequeue:

Instead of treating backing memory as a finite line that dead-ends at index $C-1$, a Circular Queue (Ring Buffer) bends the array into a continuous logical ring where index $C-1$ connects directly to index $0$.

When pointer rear or front increments past the physical boundary of the array, it wraps around to the beginning using Modulo Arithmetic:

When slot $C-1$ is reached, $((C-1)+1)(\mathrm{mod}C)=0$. If slot $0$ was previously vacated by a Dequeue, rear immediately claims it without shifting a single byte of memory.

When front == rear, does it signify that the queue is completely empty or completely full? Two distinct architectural patterns resolve this ambiguity:

Strategy A: Explicit Count Variable (Recommended)

Maintain an internal integer count tracking the active element count ($0\le \text{count}\le \text{Capacity}$):

• Empty Condition: $\text{count}==0$
• Full Condition: $\text{count}==\text{Capacity}$
• Available Slots: $\text{Capacity}-\text{count}$

Strategy B: Reserved Empty Slot (Classic Textbook)

Sacrifice one array slot permanently. An array of size $C$ holds at most $C-1$ elements:

• Empty Condition: $\text{front}==\text{rear}$
• Full Condition: $(\text{rear}+1)(\mathrm{mod}C)==\text{front}$

Let Capacity $C=5$. We trace a complete lifecycle demonstrating wrap-around:

Can a strict FIFO queue be constructed using only two LIFO stacks ($S_{\text{in}}$ and $S_{\text{out}}$)?

1Enqueue(x):
2    S_in.Push(x)
3 
4Dequeue():
5    if S_out.IsEmpty():
6        if S_in.IsEmpty(): raise Underflow
7        while not S_in.IsEmpty():
8            S_out.Push(S_in.Pop())  // Inverts LIFO to FIFO order!
9    return S_out.Pop()

Formal Amortized Proof via the Physicist's Potential Method:

Define the potential function $\Phi$ of the two-stack system at state $t$ as:

• Notice that $\Phi (D_0)=0$ (initially empty) and $\Phi (D_t)\ge 0$ for all $t\ge 0$.

1. Amortized Cost of Enqueue(x):

   • Actual work $c_i=1$ (pushing onto $S_{\text{in}}$).
   • $\Delta \Phi =\Phi (D_i)-\Phi (D_{i-1})=2(|S_{\text{in}}|+1)-2|S_{\text{in}}|=+2$.
   • Amortized cost:
     $${\hat{c}}_i=c_i+\Delta \Phi =1+2=3=\Theta (1)$$

2. Amortized Cost of Dequeue():

   • Case A: $S_{\text{out}}$ is non-empty:
     • Actual work $c_i=1$ (pop from $S_{\text{out}}$).
     • $\Delta \Phi =0$ (size of $S_{\text{in}}$ is unchanged).
     • ${\hat{c}}_i=1+0=1=\Theta (1)$.
   • Case B: $S_{\text{out}}$ is empty (batch transfer of $k=|S_{\text{in}}|$ items):
     • Actual work $c_i=2k+1$ ($k$ pops from $S_{\text{in}}$, $k$ pushes to $S_{\text{out}}$, plus $1$ final pop).
     • $\Delta \Phi =2\cdot 0-2k=-2k$.
     • Amortized cost:
       $${\hat{c}}_i=c_i+\Delta \Phi =(2k+1)-2k=1=\Theta (1)$$

Therefore, every operation executes in amortized $\Theta (1)$ time. $■$

In high-performance operating system engineering (such as the Linux kernel's kfifo subsystem):

• Capacities are constrained to powers of two: $C=2^k$.
• Integer modulo division (id % C) translates to an expensive multi-cycle CPU instruction (idiv on x86, taking 15–40 clock cycles).
• By constraining $C=2^k$, modulo is replaced with a single-cycle bitwise AND mask:
  $$\text{index}(\mathrm{mod}{2}^k)\equiv \text{index}\&(2^k-1)$$

// Linux kernel kfifo wrap-around idiom:
unsigned int next_in = (fifo->in + 1) & (fifo->size - 1);

Furthermore, by decoupling in and out into 64-bit monotonically increasing unsigned counters that wrap naturally on integer overflow ($2^{64}-1\to 0$), Single-Producer Single-Consumer (SPSC) ring buffers run completely lock-free without mutex locks or atomic compare-and-swap (CAS) instructions.

A. C++20 Ring Buffer with Bitwise Masking & Template Safety

#include <iostream>
#include <vector>
#include <stdexcept>
#include <concepts>

template <typename T>
class CircularQueue {
private:
    std::vector<T> buffer_;
    size_t capacity_;
    size_t mask_;
    size_t front_;
    size_t rear_;
    size_t count_;

    static size_t next_power_of_two(size_t n) {
        size_t power = 1;
        while (power < n) power <<= 1;
        return power;
    }

public:
    explicit CircularQueue(size_t min_capacity = 8)
        : capacity_(next_power_of_two(min_capacity)),
          mask_(capacity_ - 1),
          buffer_(capacity_),
          front_(0),
          rear_(0),
          count_(0) {}

    bool enqueue(T item) {
        if (is_full()) {
            return false;
        }
        buffer_[rear_] = std::move(item);
        rear_ = (rear_ + 1) & mask_;
        ++count_;
        return true;
    }

    bool dequeue(T& item) {
        if (is_empty()) {
            return false;
        }
        item = std::move(buffer_[front_]);
        front_ = (front_ + 1) & mask_;
        --count_;
        return true;
    }

    [[nodiscard]] bool is_empty() const noexcept { return count_ == 0; }
    [[nodiscard]] bool is_full() const noexcept { return count_ == capacity_; }
    [[nodiscard]] size_t size() const noexcept { return count_; }
    [[nodiscard]] size_t capacity() const noexcept { return capacity_; }
};

1. FIFO Invariant: Queues enforce First-In, First-Out order, serving as the universal primitive for breadth-first search and pipeline scheduling.
2. False Overflow Elimination: Naive linear array queues suffer from pointer drift; circular ring buffers recycle memory via modulo arithmetic (idx + 1) % C.
3. Disambiguation Rules: Full versus empty state in ring buffers is cleanly resolved by maintaining an explicit element count tracker.
4. Hardware Symbiosis: Sizing ring buffers to powers of two enables bitwise wrap-around masking idx & (C - 1), a cornerstone optimization in Linux kernel kfifo and NIC ring buffers.

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 10: Elementary Data Structures. MIT Press.
2. Corbet, J., Rubini, A., & Kroah-Hartman, G. (2005). Linux Device Drivers (3rd ed.), Chapter 11: Data Types in the Kernel (kfifo). O'Reilly Media.
3. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 1.3: Bags, Queues, and Stacks. Addison-Wesley.
4. Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.), Section 2.2: Linear Lists. Addison-Wesley.