C++ Circular Queue: Full vs Empty and Modulo vs Mask

Revised November 2026. This tutorial first appeared in Korean in 2021. We recompiled the circular queue with Apple clang 21 (-Wall -Wextra: no warnings; ASan and UBSan: no reports). The idea in the article, one dummy slot to separate full from empty, is correct, but enqueue never checked isFull(): one item too many and a full queue reports itself as empty. The sample output also differed from ours, because of an evaluation-order rule that changed in C++17. Below are both issues, two correct designs, and a measurement of % vs bitmask indexing.

This article is for developers who need a fixed-size FIFO buffer in C or C++ (audio and network buffers, log rings, producer/consumer queues) and for C# developers curious about what Queue<T> does internally. A circular queue, or ring buffer, stores items in an array and lets the front and rear indexes wrap around, so dequeue never shifts elements. The hard part is not the wrap; it is telling a full ring from an empty one, and it is the one bug that sanitizers cannot see.

Why a linear array queue is slow

If a queue lives in a plain array with the front always at index 0, every dequeue has to shift the remaining elements one slot left. With 1,000 items that is 999 moves per dequeue, so draining the queue is O(n²). The fix is to stop moving data and move the indexes instead:

• front is the index of the next item to dequeue,
• rear is the index where the next item will be written,
• both advance by one and wrap from the last index back to 0.

Now enqueue and dequeue are O(1) and the array is reused forever. The price is that front and rear alone no longer tell you how many items there are. (A linked queue avoids the problem by having no capacity at all, at roughly 16 times the cost in our measurements.)

The full vs empty ambiguity

Take a 4-slot array. Start empty: front == rear == 0. Enqueue four items: rear advances 0 → 1 → 2 → 3 → back to 0. Now the queue is completely full and front == rear == 0, exactly the same state as empty.

There are two standard ways out.

1. Leave one slot empty. Allocate cap + 1 slots and call the queue full when advancing rear would land on front. Empty is front == rear, full is (rear + 1) % n == front. This is what the 2021 article did, and its explanation was right.
2. Keep a count. Store head and count; the write position is (head + count) % cap. Empty is count == 0, full is count == cap, and every slot is usable.

.NET's own Queue<T> uses the second approach. Reading its private fields with reflection on .NET 10, after filling a 4-slot queue with wrap-around:

Int32[] _array, Int32 _head, Int32 _tail, Int32 _size, Int32 _version
array=[4,5,2,3] head=2 tail=2 size=4
after 5th item: array.Length=8 head=0 tail=5 size=5

head == tail while size is 4, so the count is what says "full". On the next enqueue the array doubles and the items are copied out in order.

Re-running the 2021 code: the missing full check

The 2021 class allocated capacity + 1 nodes and had correct isEmpty, isFull and getSize functions. But enqueue and dequeue never called them. enqueue wrote and advanced rear unconditionally, and dequeue read and advanced front unconditionally. We gave it a 3-slot queue and four items:

CircularQueue cq(3);              // 3 usable slots (+1 dummy)
for (int i = 1; i <= 4; i++) {
    cq.enqueue(i * 10);
    cout << "enqueue(" << i * 10 << ") -> size " << cq.getSize()
         << ", isEmpty " << cq.isEmpty() << ", isFull " << cq.isFull() << endl;
}
cout << "dequeue on 'empty' queue: " << cq.dequeue() << endl;

enqueue(10) -> size 1, isEmpty 0, isFull 0
enqueue(20) -> size 2, isEmpty 0, isFull 0
enqueue(30) -> size 3, isEmpty 0, isFull 1
enqueue(40) -> size 0, isEmpty 1, isFull 0
dequeue on 'empty' queue: 10

The fourth enqueue wrote into the dummy slot and moved rear onto front. The queue now claims to be empty, three values are unreachable, and a dequeue on the "empty" queue still returns the stale 10. This is the ambiguity from the previous section, reached by skipping the check.

We rebuilt the same program with -fsanitize=address,undefined: no report. Every read and write stayed inside the 4-element array, so from the sanitizer's point of view nothing was wrong. Logic errors in a ring buffer have to be caught by tests and by checks in the code, not by tools.

Re-running the 2021 code: why the sample output differs

The 2021 sample printed, for each dequeue, the value plus getFront() and getRear() in one cout chain. Its published first and last lines were:

2021 article:   dequeued 10, Front: 3, Rear: 1   ...   dequeued 520, Front: 0, Rear: 1
clang 21:       dequeued 10, Front: 4, Rear: 1   ...   dequeued 520, Front: 1, Rear: 1

clang printed the same values with both -std=c++14 and -std=c++17. The 2021 output is what you get if getFront() runs before dequeue() in the same expression. Before C++17, the order in which the operands of a << chain were evaluated was unspecified, so a compiler was allowed to do that. Since C++17 (proposal P0145) the operands of << are evaluated left to right, which gives clang's output. The article's own explanation ("front and rear both end at index 1") matches the C++17 result, not its printed output. The fix is simple: never call a function with side effects and read the state it changes in the same expression; dequeue into a variable first.

The article also said that when rear passes the end, "the capacity is subtracted from the rear index". What actually happens is a wrap: rear goes from index 10 back to 0, so after 3 + 9 enqueues into 11 slots it sits at (3 + 9) mod 11 = 1.

Two correct circular queues

Both versions check before they write or read and return false instead of corrupting state.

// A) one slot left empty: n = cap + 1
class SlotQueue {
    int* d_; int n_; int front_ = 0, rear_ = 0;
    int next(int i) const { return (i + 1) % n_; }
public:
    explicit SlotQueue(int cap) : d_(new int[cap + 1]), n_(cap + 1) {}
    ~SlotQueue() { delete[] d_; }
    SlotQueue(const SlotQueue&) = delete; SlotQueue& operator=(const SlotQueue&) = delete;
    bool empty() const { return front_ == rear_; }
    bool full()  const { return next(rear_) == front_; }
    int  size()  const { return (rear_ - front_ + n_) % n_; }
    bool enqueue(int v) { if (full()) return false; d_[rear_] = v; rear_ = next(rear_); return true; }
    bool dequeue(int& o) { if (empty()) return false; o = d_[front_]; front_ = next(front_); return true; }
};

// B) count-based: every slot usable
class CountQueue {
    int* d_; int cap_; int head_ = 0, count_ = 0;
public:
    explicit CountQueue(int cap) : d_(new int[cap]), cap_(cap) {}
    ~CountQueue() { delete[] d_; }
    CountQueue(const CountQueue&) = delete; CountQueue& operator=(const CountQueue&) = delete;
    bool empty() const { return count_ == 0; }
    bool full()  const { return count_ == cap_; }
    bool enqueue(int v) { if (full()) return false; d_[(head_ + count_) % cap_] = v; ++count_; return true; }
    bool dequeue(int& o) { if (empty()) return false; o = d_[head_]; head_ = (head_ + 1) % cap_; --count_; return true; }
};

The same four enqueues into capacity 3:

enqueue(10): slot ok   size 1 | count ok   size 1
enqueue(20): slot ok   size 2 | count ok   size 2
enqueue(30): slot ok   size 3 | count ok   size 3
enqueue(40): slot FULL size 3 | count FULL size 3
10 20 30 | dequeue on empty -> false

The size() formula (rear - front + n) % n also replaces the 2021 two-branch getSize. Which to pick: the slot version needs no extra field and suits single-producer/single-consumer lock-free rings, where each side writes only its own index; the count version uses every slot and is easier to read.

Modulo vs bitmask indexing (measured)

Every enqueue and dequeue computes a wrapped index. Three ways to do it:

i = (i + 1) % cap;           // modulo, any capacity
i = (i + 1) & (cap - 1);     // bitmask, capacity must be a power of two
if (++i == cap) i = 0;       // compare and reset, any capacity

We put each into the count-based ring with a capacity of 1,024 read from the command line, so the compiler could not treat it as a constant. Workload: fill half, then 200 million enqueue+dequeue pairs. Apple clang 21 -O2, Apple M1 Pro, three runs:

The modulo version was about four times slower. The generated arm64 code shows why:

(i + 1) % 1024u    (constant)   ->  add, and #0x3ff
(i + 1) % cap      (run time)   ->  add, udiv, msub
(i + 1) % 1024     (signed int) ->  add, negs, and, and, csneg

With a constant power-of-two capacity the compiler already emits the mask for you, so writing & by hand gains nothing. With a capacity chosen at run time it must emit a real division, and that is what the 849 ms measures. Signed int indexes cost extra instructions to handle negative values even with a constant, which is one more reason to use unsigned indexes. If you cannot force a power-of-two size, the compare-and-reset branch was almost as fast as the mask, because the branch is almost always predicted correctly.

Built-in equivalents

For the LIFO counterpart and the same overflow/underflow checks on an array, see stack. A ring made of nodes rather than array slots is covered in circular linked list.

Tested with Apple clang 21.0.0 (-std=c++14/17/20 -Wall -Wextra, -fsanitize=address,undefined -g) and .NET SDK 10.0.403 / runtime 10.0.14 on an Apple M1 Pro.