This post is part of a series on implementing classic data structures in modern C++ (C++20), without new/delete scattered around and with the sanitizers watching every step. The code lives in collections101.

A queue is the data structure of waiting lines: the first element in is the first one out (FIFO). It shows up everywhere, from task schedulers to breadth-first search. Its interface is tiny:

OperationWhat it does
enqueueinserts an element at the back
dequeueremoves the element at the front
frontreads the element at the front
is_emptytells whether there is anything in it

When we restrict ourselves to these four operations, we can implement a queue on (at least amortized) constant time. The restriction is the point: a queue cannot do much, and in exchange it can do it fast and communicate intent clearly.

The naive array, and why it fails

The obvious approach is to keep the elements in an array, append at the end, and remove from the beginning. Appending is cheap. Removing from the beginning is not: every remaining element must shift one position to the left, which costs O(n). Reversing the roles just moves the problem to enqueue.

A linked list solves this (keep a pointer to the first and to the last node), and it is a fine implementation. But each element pays for a pointer and a separate allocation, and walking the nodes jumps around in memory. Can we keep the contiguous array and still get O(1) at both ends?

Don’t move the elements, move the indices

The trick is to stop treating position 0 of the array as the front of the queue. Instead, we store where the front currently is, and let the queue wrap around the end of the array as if the memory were a circle.

Here is a queue (e₁, e₂, e₃) in an array of capacity 8, sitting in the middle:

index: 0   1   2   3   4   5   6   7
       [  ][  ][  ][e₁][e₂][e₃][  ][  ]
                   ^ begin = 3, size = 3

And the same queue after a few enqueues and dequeues pushed it past the end:

index: 0   1   2   3   4   5   6   7
       [e₂][e₃][  ][  ][  ][  ][  ][e₁]
                                   ^ begin = 7, size = 3

Both are valid. To find the i-th element of the queue, we compute its physical position with a modulo:

position(i) = (begin + i) mod capacity

The front is at position(0), the next free slot is at position(size). Dequeuing just advances begin; enqueuing writes at position(size). Nothing ever shifts.

The class

template <std::movable T>
class Queue {
public:
  Queue() = default;
  Queue(const Queue&) = delete;
  auto operator=(const Queue&) -> Queue& = delete;
  ~Queue() noexcept;

  void enqueue(T);
  auto dequeue() -> T;
  [[nodiscard]] auto front() const -> const T&;
  [[nodiscard]] auto is_empty() const noexcept -> bool;

private:
  void double_capacity();
  auto wrap(std::size_t) const noexcept -> std::size_t;

  [[no_unique_address]] std::allocator<T> alloc_;
  T* values_ = nullptr;
  std::size_t begin_ = 0;
  std::size_t size_ = 0;
  std::size_t capacity_ = 0;
};

A few things worth noticing:

The mapping from logical to physical index is one line:

template <std::movable T>
auto Queue<T>::wrap(std::size_t i) const noexcept -> std::size_t {
  return i % capacity_;
}

The operations

enqueue grows the buffer when it is full, then constructs the new element in the first free slot with std::construct_at:

template <std::movable T>
void Queue<T>::enqueue(T value) {
  if (size_ == capacity_)
    double_capacity();
  std::construct_at(values_ + wrap(begin_ + size_),
                    std::move(value));
  ++size_;
}

Taking value by value and moving it in serves both callers: a temporary is moved twice (cheap), an lvalue is copied once, which is unavoidable anyway.

dequeue moves the front element out, destroys what is left in its slot, advances begin_, and hands the element to the caller:

template <std::movable T>
auto Queue<T>::dequeue() -> T {
  if (is_empty())
    throw std::runtime_error{"no element to dequeue"};
  T value(std::move(values_[begin_]));
  std::destroy_at(values_ + begin_);
  begin_ = wrap(begin_ + 1);
  --size_;
  return value;
}

std::destroy_at is the mirror of std::construct_at: one starts an object’s lifetime in raw memory, the other ends it and leaves raw memory behind. (They are the C++20 spelling of placement new and an explicit destructor call, p->~T(), with names that make the pairing obvious.) Because we separated allocation from construction, we are now responsible for keeping them paired: every slot in [begin, begin + size) (wrapped) holds a live object, every other slot is raw memory. That invariant is the whole implementation.

Note that moving from the slot does not end the object’s lifetime. A moved-from std::string is still a std::string (typically empty), and its destructor must still run, which is why the destroy_at stays. What the move buys us is that this destruction is cheap: the expensive part (the characters, the pointee of a unique_ptr) now belongs to value.

And value is no longer the queue’s problem. It is returned to the caller, who owns it from then on. In practice the compiler constructs it directly in the caller’s variable (named return value optimization), so there is no second move. If the caller ignores the result, as in a plain queue.dequeue();, the compiler materializes a temporary at the call site and destroys it at the end of that statement. Either way, every object is destroyed exactly once, and the queue does not need to know which case happened.

Why does std::queue::pop return void, then?

The standard library’s pop returns nothing, and you are expected to write auto x = q.front(); q.pop();. That design predates move semantics. In C++98, returning the element meant copying it after it had been removed; if that copy threw, the element was gone for good, and the operation could not offer the strong exception guarantee.

With moves, the risk mostly disappears. We move into value before touching the queue, so if that move throws, nothing was removed. The remaining gap is narrow: the return is not guaranteed to be elided for a named variable, so a compiler that skipped the elision would perform a second move, after removal, and a throwing move there would lose the element. Real compilers elide here, and moves rarely throw. In exchange we get a queue that works with move-only types such as std::unique_ptr and a one-step auto x = q.dequeue();. Other designs made the same call: Rust’s pop_front, and concurrent queues, where a separate front() and pop() would race against other threads.

front only reads. Standard containers also offer a non-const overload that lets the caller modify the element in place, but we leave it out on purpose: once an element is in the queue, it is not modified. To change it, dequeue it and enqueue the new value. The queue keeps to the four operations in the table, and since dequeue hands the element back, that round trip is cheap. is_empty is what you would expect:

template <std::movable T>
auto Queue<T>::front() const -> const T& {
  if (is_empty())
    throw std::runtime_error{"empty queue has no front"};
  return values_[begin_];
}

template <std::movable T>
auto Queue<T>::is_empty() const noexcept -> bool {
  return size_ == 0;
}

Growing without breaking anything

When the buffer is full, we allocate one twice as large and move the elements over, unwrapping them on the way so that the new queue starts at index 0:

template <std::movable T>
void Queue<T>::double_capacity() {
  auto new_capacity = capacity_ == 0 ? 1 : 2 * capacity_;
  auto buffer = alloc_.allocate(new_capacity);

  std::size_t i;
  try {
    for (i = 0; i < size_; ++i)
      std::construct_at(
        buffer + i,
        std::move_if_noexcept(values_[wrap(begin_ + i)]));
  } catch (...) {
    std::destroy_n(buffer, i);
    alloc_.deallocate(buffer, new_capacity);
    throw;
  }

  for (i = 0; i < size_; ++i)
    std::destroy_at(values_ + wrap(begin_ + i));
  if (values_) // deallocate only takes what allocate gave
    alloc_.deallocate(values_, capacity_);

  begin_ = 0;
  values_ = buffer;
  capacity_ = new_capacity;
}

Two details make this robust:

Doubling is what makes enqueue amortized constant time: a reallocation costs O(n), but it happens after n cheap insertions, so the average cost per insertion stays bounded. The price is memory: right after a resize, up to half of the buffer is empty.

The destructor

template <std::movable T>
Queue<T>::~Queue() noexcept {
  for (std::size_t i = 0; i < size_; ++i)
    std::destroy_at(values_ + wrap(begin_ + i));
  if (values_) // deallocate only takes what allocate gave
    alloc_.deallocate(values_, capacity_);
}

Destroy the live objects (wrapped, again), then release the memory. Same invariant, last time.

The if (values_) guard (also in double_capacity, for the first growth) covers a queue that never allocated. Unlike delete, which accepts a null pointer, std::allocator::deallocate requires a pointer that allocate returned. Passing nullptr usually works in practice, since the default allocator ends up in operator delete, which ignores null. But it breaks the allocator’s contract, and nothing guarantees it works.

The bug that copying would have caused

Here is the version without the two = delete lines, and a two-line program:

Queue<std::string> a;
a.enqueue("x");
auto b = a;   // compiles!

The compiler happily generates a copy constructor that copies the four members. Now a and b point at the same buffer, and when both go out of scope, both destructors destroy the same string and free the same memory. Compiled with -fsanitize=address, this program stops immediately:

ERROR: AddressSanitizer: heap-use-after-free
SUMMARY: AddressSanitizer: heap-use-after-free ... in Queue<std::string>::~Queue()

Without the sanitizer, it may crash, corrupt the heap silently, or appear to work. This is the rule of five in action: a class that manages a resource in its destructor must decide what copying and moving mean. Deleting the copy operations is the simplest correct answer (and, as a side effect, suppresses the equally broken implicit move operations). Implementing a real deep copy and a pointer-stealing move are good exercises; the second one is short.

This is also why the tests in collections101 are always built with -fsanitize=address,undefined,leak: in hand-written containers, the bugs that matter are the ones that do not crash right away.

Linked or circular?

Both implementations give O(1) operations. They differ in everything else:

Linked nodesCircular buffer
enqueueO(1) worst caseO(1) amortized
Extra memoryone pointer per elementup to half the buffer, unused
Allocationsone per elementone per doubling
Cache localitypoor (nodes are scattered)good (elements are contiguous)

In practice the circular buffer usually wins, thanks to locality and far fewer allocations. The linked version is the one to pick when you need a hard worst-case bound on every single enqueue (no occasional O(n) resize).

Exercises

  1. Since the capacity is always a power of two, i % capacity_ can be replaced by a bit mask. Write it. Does it make a measurable difference?
  2. Add size() in constant time. (It is almost free here. Why is it not free in the linked version without an extra member?)
  3. Implement a move constructor and a move assignment for Queue.
  4. Shrink the buffer when the queue is less than a quarter full. Why a quarter and not a half?
  5. Add clear(), which empties the queue but keeps its capacity.

The complete implementation and a small test are in collections101.