Circular Queue Wraparound and Linked-List Queue Pointers in C++

FIFO, and when a queue is the right shape

A queue exposes a deliberately narrow interface: you add at one end (enqueue) and remove from the other (front/dequeue). Nothing else. No indexing, no insert-in-the-middle, no search. That restriction is the whole point — it buys you O(1) on both operations and a guarantee that items come out in the order they went in.

Reach for a queue when arrival order is the correct service order:

• Breadth-first search. BFS is a queue. The frontier of a graph traversal is a FIFO, and swapping it for a stack silently turns your BFS into a DFS — the code still runs, the shortest-path guarantee just evaporates.
• Producer/consumer buffers. Keystrokes, network packets, print jobs, log lines. Something generates work faster or slower than something else consumes it, and reordering would be a bug.
• Level-order tree traversal, sliding-window scanning, round-robin scheduling.

Do not reach for a queue when you need priorities (that is a heap), or when the most recently added item should be handled first (that is a stack — undo, recursion, backtracking).

In production C++ you would write std::queue<T>, which wraps std::deque by default. The point of implementing one by hand is that the two failure modes below are the same two failure modes that show up in ring buffers, circular DMA descriptors, lock-free SPSC queues, and every intrusive linked list you will ever touch.

The naive array queue, and false overflow

The obvious first attempt: an array, an index front pointing at the first live item, an index rear pointing one past the last. Enqueue writes at rear and increments it; dequeue reads at front and increments it.

It works, right up until it doesn't. Run the code below: five enqueues fill the array, four dequeues empty most of it, and then the sixth enqueue is rejected while four of the five cells are free.

This is false overflow. Both indices only ever move right, so the live window slides toward the end of the array and the space behind front is abandoned. After k total enqueues the queue is permanently dead, no matter how many dequeues happened in between.

Two bad fixes, worth naming so you can reject them:

• Shift everything left on dequeue so front is always 0. Correct, but now dequeue copies up to n elements — O(n) per removal, O(n²) to drain the queue. You have destroyed the one property that made a queue worth using.
• Grow the array when rear hits the end. You are now allocating memory in proportion to the total traffic through the queue rather than its peak occupancy. A queue that holds three items but processes a million will allocate a million slots.

The real fix costs one operator.

// The naive version -- correct FIFO order, wrong capacity behaviour.
#include <iostream>
const int CAP = 5;

struct NaiveQueue {
    int data[CAP];
    int front = 0;   // index of the first live item
    int rear  = 0;   // index one past the last live item

    bool enqueue(int v) {
        if (rear == CAP) return false;   // "overflow" -- but is it really?
        data[rear++] = v;
        return true;
    }
    bool dequeue(int& out) {
        if (front == rear) return false;
        out = data[front++];
        return true;
    }
};

int main() {
    NaiveQueue q;
    int x;
    for (int v : {1, 2, 3, 4, 5}) q.enqueue(v);
    for (int i = 0; i < 4; ++i) q.dequeue(x);

    std::cout << "items held: " << (q.rear - q.front) << "\n";  // 1
    std::cout << "enqueue succeeds? " << q.enqueue(6) << "\n";  // 0  <-- false overflow
}

Modulo wraparound: the array bends into a ring

Stop treating the array as a line and start treating it as a circle. Index capacity - 1 is followed by index 0. Every index advance goes through the modulo operator:

front = (front + 1) % capacity;
rear  = (rear  + 1) % capacity;

That is the entire fix. % capacity maps the successor of the last cell back to the first, so the live window is now free to rotate around the buffer forever. The cells behind front are no longer abandoned — they are simply the cells the window has not come back around to yet. Physical storage stops being tied to logical position, and the only thing that limits you is how many items are live at once, which is exactly the right limit.

Three properties worth internalising:

1. The live region can be split in two. With capacity = 5, front = 3, and four items, the data occupies indices 3, 4, 0, 1. Any code that assumes contiguity — memcpy(buf + front, ...), rear - front, a for (i = front; i < rear; ++i) loop — is wrong the moment the window wraps. If you need contiguous output, copy in two runs.
2. The indices never need resetting. Draining the queue does not send front and rear back to 0, and it shouldn't. Emptiness is a relationship between them, not a particular value of either.
3. Operator precedence will get you. % binds tighter than +, so rear + 1 % capacity parses as rear + (1 % capacity) — that is just rear + 1, the bug you were trying to fix, compiling without a warning. Parenthesise: (rear + 1) % capacity.

One performance note for later: if you force capacity to be a power of two, % capacity becomes & (capacity - 1), replacing a division with a single AND. Real ring buffers do this. Do not attempt it unless the capacity is genuinely a power of two — the mask silently produces garbage otherwise.

Full or empty? Breaking the tie

Wraparound creates one new problem. When the queue is empty, front == rear. When the queue is completely full, the window has come all the way around and... front == rear again. Two opposite states, one representation. You have capacity + 1 distinct occupancy levels to encode and only capacity distinct values of (rear - front) mod capacity to encode them in — a counting argument, so some extra bit of information is unavoidable. Three standard ways to supply it:

1. Sacrifice a slot. Never let the queue hold more than capacity - 1 items. Then front == rear unambiguously means empty, and full is the state one step before the collision:

bool empty() const { return front == rear; }
bool full()  const { return (rear + 1) % capacity == front; }
std::size_t size() const { return (rear + capacity - front) % capacity; }

Costs you one cell and makes size() a computation. Buys you a queue whose entire state is two indices, with no third field that can drift out of sync. If a caller asks for room for k items, allocate k + 1 cells — getting this backwards is the classic off-by-one of this design.

2. Keep an explicit count. Store count alongside the indices. empty() is count == 0, full() is count == capacity, size() is free, and you get to use every cell. The cost is a third piece of state that both enqueue and dequeue must update correctly — one more place to be wrong, and a bug there is invisible until the queue is under load. A neat trick removes half the risk: store only front and count, and derive the rear as (front + count) % capacity. Now there is no second index to fall out of step with the counter.

3. Monotonic counters. Let head and tail be unsigned counters that only ever increase; index with head % capacity, and read the size as tail - head. Empty is head == tail, full is tail - head == capacity, all capacity cells are usable, and unsigned overflow is well-defined so the counters can wrap after 2⁶⁴ operations without incident. This is what high-performance and lock-free ring buffers use, because a single-writer/single-reader pair can update one counter each with no shared mutable index.

Which to pick. Sacrificed slot when the state must stay minimal or the memory is a fixed hardware buffer; explicit count when you want the full capacity and callers ask for size() often; monotonic counters when you are chasing throughput. What you must not do is mix conventions — pick one, and write the invariant in a comment at the top of the class, because six months later the code will not tell you whether rear means "last item" or "one past last".

A complete circular queue in C++

This is the front-plus-count variant: two stored fields, all cells usable, no separate rear index to desynchronise. Note that enqueue derives the write position rather than storing it — (front_ + count_) % cap_ is the slot one past the last live item, which is exactly where the new element belongs.

Read the wraparound in dequeue carefully. It does not clear the vacated cell, and it does not need to: the old value is simply outside the live window now, and it will be overwritten the next time the window rotates past it. (For a std::vector<T> of non-trivial types you would want to destroy the object; for int, leaving it is free and harmless.)

The program at the bottom exercises the wrap explicitly: it fills three of four cells, drains two, then enqueues three more so that the write index rolls over the end of the buffer. Output is 12 size=4 front=3, then 3456 — FIFO order preserved straight through the wraparound.

#include <cstddef>
#include <stdexcept>
#include <vector>
#include <iostream>

// Invariant: the live items occupy the cap_-modular range
//   [front_, front_ + count_)   with 0 <= count_ <= cap_.
class CircularQueue {
public:
    explicit CircularQueue(std::size_t capacity)
        : buf_(capacity), cap_(capacity), front_(0), count_(0) {
        if (capacity == 0) throw std::invalid_argument("capacity must be > 0");
    }

    bool empty() const { return count_ == 0; }
    bool full()  const { return count_ == cap_; }
    std::size_t size() const { return count_; }

    void enqueue(int value) {
        if (full()) throw std::overflow_error("queue is full");
        std::size_t rear = (front_ + count_) % cap_;   // derived, never stored
        buf_[rear] = value;
        ++count_;
    }

    int dequeue() {
        if (empty()) throw std::underflow_error("queue is empty");
        int value = buf_[front_];
        front_ = (front_ + 1) % cap_;   // the wraparound
        --count_;
        return value;
    }

    int peek() const {
        if (empty()) throw std::underflow_error("queue is empty");
        return buf_[front_];
    }

private:
    std::vector<int> buf_;
    std::size_t cap_;
    std::size_t front_;
    std::size_t count_;
};

int main() {
    CircularQueue q(4);
    q.enqueue(1); q.enqueue(2); q.enqueue(3);
    std::cout << q.dequeue() << q.dequeue();            // 12
    q.enqueue(4); q.enqueue(5); q.enqueue(6);           // write index wraps here
    std::cout << " size=" << q.size()
              << " front=" << q.peek() << "\n";        // size=4 front=3
    while (!q.empty()) std::cout << q.dequeue();        // 3456
    std::cout << "\n";
    try { q.dequeue(); }
    catch (const std::underflow_error& e) { std::cout << e.what() << "\n"; }
}

The linked queue: two pointers describing one list

When you do not know the peak occupancy in advance, back the queue with a singly linked list. Keep front_ at the head (so removal is O(1)) and rear_ at the tail (so insertion is O(1)). The direction of the next pointers matters: they must run front → rear, so that removing the head is a one-hop update. If you linked them the other way, dequeue would have to find the head's successor by traversal.

The two lines that carry all the risk are marked in the code:

• enqueue on an empty queue. There is no old tail to link from, so rear_->next = node would dereference null. Both pointers must be set to the new node: it is simultaneously the first and the last element. The check is rear_ == nullptr (equivalently front_ == nullptr — the invariant is that they are null together or non-null together).
• dequeue of the last node. After front_ = old->next, front_ is null. If you stop there, rear_ still points at the node you are about to delete — a dangling pointer. The queue now reports empty via front_, but the next enqueue takes the non-empty branch, writes rear_->next into freed memory, and you have heap corruption that surfaces somewhere else entirely. One line prevents it: if (front_ == nullptr) rear_ = nullptr;

Also note the ordering inside the non-empty enqueue branch. rear_->next = node; must come before rear_ = node;. Reversed, you overwrite the only pointer to the old tail, then set the new node's next to itself — a self-loop, an infinite dequeue, and a leaked list.

And note what this class does that a classroom sketch usually skips: it has a destructor, a copy constructor, and an assignment operator. The compiler-generated copy would duplicate the two raw pointers, giving you two queues sharing one node chain and two destructors racing to free it. Owning raw pointers means you own the rule of three.

#include <iostream>
#include <stdexcept>
#include <utility>

// Invariant: front_ and rear_ are both null (empty) or both non-null.
//            rear_->next is always nullptr.
class LinkedQueue {
    struct Node {
        int data;
        Node* next;
        explicit Node(int d) : data(d), next(nullptr) {}
    };
    Node* front_ = nullptr;
    Node* rear_  = nullptr;
    std::size_t count_ = 0;

public:
    LinkedQueue() = default;
    ~LinkedQueue() { clear(); }

    LinkedQueue(const LinkedQueue& other) {
        for (Node* p = other.front_; p != nullptr; p = p->next) enqueue(p->data);
    }
    LinkedQueue& operator=(LinkedQueue other) { swap(other); return *this; }
    LinkedQueue(LinkedQueue&& other) noexcept { swap(other); }

    void swap(LinkedQueue& other) noexcept {
        std::swap(front_, other.front_);
        std::swap(rear_,  other.rear_);
        std::swap(count_, other.count_);
    }

    bool empty() const { return front_ == nullptr; }
    std::size_t size() const { return count_; }

    void enqueue(int value) {
        Node* node = new Node(value);
        if (rear_ == nullptr) {
            front_ = rear_ = node;   // (1) empty queue: node is BOTH ends
        } else {
            rear_->next = node;      // link the old tail first...
            rear_ = node;            // ...then move the tail marker
        }
        ++count_;
    }

    int dequeue() {
        if (empty()) throw std::underflow_error("dequeue on empty queue");
        Node* old = front_;
        int value = old->data;       // read BEFORE delete
        front_ = old->next;
        if (front_ == nullptr) rear_ = nullptr;   // (2) removed the last node
        delete old;
        --count_;
        return value;
    }

    int& peek() {
        if (empty()) throw std::underflow_error("peek on empty queue");
        return front_->data;
    }

    void clear() { while (!empty()) dequeue(); }
};

int main() {
    LinkedQueue q;
    q.enqueue(1); q.enqueue(2);
    std::cout << q.dequeue() << q.dequeue()
              << " empty=" << q.empty() << "\n";   // 12 empty=1
    q.enqueue(7);                                   // re-enters via branch (1)
    std::cout << "front=" << q.peek()
              << " size=" << q.size() << "\n";     // front=7 size=1
}

Complexity, and why each bound holds

Why the array version is O(1) and the naive fix is not. Both front and rear move forward only, one step per operation. No element is ever relocated after it is written. The alternative — compacting the array so front stays at 0 — moves every surviving element on every removal, which is O(n) per dequeue and O(n²) to drain. Wraparound is what lets you keep the elements still while the window moves.

Why the modulo does not spoil the bound. % is a single instruction on a fixed-width integer; it is constant time even though it is slower than an AND. With a power-of-two capacity the compiler reduces it to a mask.

Constant factors, which matter more than the table suggests. The array queue keeps its data in one contiguous block, so consecutive reads are cache hits and the hardware prefetcher works. The linked queue calls the allocator on every enqueue and delete on every dequeue, and its nodes scatter across the heap, so every dequeue risks a cache miss on front_->next. Same O(1), routinely several times slower in practice. Prefer the array whenever you can bound the occupancy; use the list when you truly cannot, or when a hard capacity limit would be a correctness bug.

A note on resizable ring buffers. If you want unbounded capacity and contiguity, grow the array by doubling: enqueue becomes amortised O(1) (each element is copied O(log n) times across n insertions, totalling O(n) work). The subtlety is that you cannot memcpy the old buffer into the new one when the window is wrapped — you must un-wrap it, copying the run from front to the end first and the run from 0 to rear second, and then reset front to 0.

The mistakes people actually make

Circular array

1. rear + 1 % capacity. Precedence. % binds tighter than +, so this is rear + 1 and your queue overruns the buffer. Always (rear + 1) % capacity.
2. (i - 1) % capacity to step backwards. With signed indices, C++ % truncates toward zero, so -1 % 5 is -1, not 4 — a negative index. With std::size_t the subtraction wraps to an enormous value first. Write (i + capacity - 1) % capacity.
3. rear - front as the size. Wrong the instant the window wraps, and off-by-one-in-the-wrong-direction rather than crashing, so it survives testing. Use (rear + capacity - front) % capacity, or keep a counter.
4. Allocating k cells for a k-item sacrificed-slot queue. You get k - 1. Allocate k + 1.
5. Not deciding what rear means. "Index of the last item" and "index one past the last item" produce different full tests, different empty tests, and different enqueue bodies. Both are fine; mixing them within one class is not. Write the convention down in a comment.
6. Iterating with for (i = front; i < rear; ++i). Fails whenever rear < front. Iterate by count instead: for (k = 0; k < size(); ++k) use(buf[(front + k) % capacity]);
7. Testing only the happy path. A circular queue that is never filled past the wrap point is just the naive queue. Your test must enqueue past capacity, drain, and enqueue again.

Linked queue

1. The dangling rear_. Dequeue the last node without setting rear_ = nullptr and the tail pointer aims at freed memory. The queue looks fine — empty() reads front_ and says yes — and blows up on the next enqueue. This is the single most common queue bug there is, and the reason to run your tests under -fsanitize=address.
2. Forgetting front_ too, in the other direction. Enqueueing into an empty queue must set both pointers. Setting only rear_ leaves front_ null, so the queue permanently reports empty and the node leaks.
3. Assignment order in enqueue. rear_ = node; rear_->next = node; builds a self-loop and orphans the rest of the list. Link before you advance.
4. delete before you read. delete old; return old->data; is use-after-free. It will often print the right number, which is the worst possible outcome.
5. Moving front_ without deleting. A leak per dequeue. Similarly, a missing destructor leaks the entire list — clear() must actually run.
6. Letting the compiler copy your queue. Default copy duplicates raw pointers: two objects, one node chain, double free at scope exit. Define, delete, or otherwise handle the rule of three.
7. Keeping only a front pointer to save a field. Enqueue then costs a full traversal, turning your O(1) queue into O(n) without any error message. If you want a one-pointer queue, keep the rear of a circular list — see exercise 3.

Exercises with solutions

Work through each question before opening the solution below it.

std::size_t size() const { return (rear_ + cap_ - front_) % cap_; }

class RearOnlyQueue {
    struct Node { int data; Node* next; };
    Node* rear_ = nullptr;          // rear_->next is the front

public:
    RearOnlyQueue() = default;
    ~RearOnlyQueue() { int x; while (dequeue(x)) {} }
    RearOnlyQueue(const RearOnlyQueue&) = delete;
    RearOnlyQueue& operator=(const RearOnlyQueue&) = delete;

    bool empty() const { return rear_ == nullptr; }

    void enqueue(int v) {
        Node* n = new Node{v, nullptr};
        if (rear_ == nullptr) {
            n->next = n;            // a one-node cycle points at itself
            rear_ = n;
        } else {
            n->next = rear_->next;  // new node takes over as predecessor of the front
            rear_->next = n;        // old rear now precedes the new node
            rear_ = n;              // and the new node becomes the rear
        }
    }

    bool dequeue(int& out) {
        if (rear_ == nullptr) return false;
        Node* head = rear_->next;   // the front
        out = head->data;
        if (head == rear_) rear_ = nullptr;   // it was the only node: reset, do not dangle
        else rear_->next = head->next;        // splice the front out of the cycle
        delete head;
        return true;
    }
};

Related pages