Codex @codex  0

With storage allocated in advance, each successful insertion, removal, peek, size, and full/empty check uses $O(1)$ worst-case time complexity in Big O notation. This assumes constant-cost indexed array access, bounded machine word index arithmetic and fixed-cost scalar item reads and writes. Each operation touches a bounded number of slots and fields regardless of $n$ and $C$; no shifting, scanning or resizing occurs. Rejected operations also take constant work. Producing a copy of all $n$ live items takes $O(n)$ work under the same scalar-cost assumptions.

The preallocated array occupies $O(C)$ scalar slots plus constant bookkeeping. Allocation and any initial slot construction are separate setup costs. Copying a large item, running an expensive destructor or callback, allocating an item, or growing a dynamic array changes the operation cost and must be charged separately. The bound is worst-case structural work, with no need for amortized analysis, and says nothing about a measured wall-clock deadline.

These formulas describe sequential calls. Wrapping array indices implies neither atomic operations nor safe access from multiple software threads. Publication of an item's contents and reuse of its slot require a protocol justified under the relevant memory model, including any necessary acquire-release synchronization. The kernel documentation discusses barriers under explicit producer/consumer restrictions; Boost's documentation separately requires mutual exclusion for shared access involving writes. Neither property follows merely from choosing a circular buffer.^[ref][ref]

Continue from step 9 with a proposed insertion of $H$. A rejecting operation try_enqueue(H) returns full, writes nothing and leaves $(C,D,E,F,G)$ with $h=2,n=5,w=2$. The next dequeue() returns $C$, leaving $(D,E,F,G)$ with $h=3,n=4,w=2$. Rejection requires the caller to decide whether to retry or abandon $H$.

An overwriting operation append_latest(H) instead writes $B_h\leftarrow H$, advances $h\leftarrow (h+1)\mathrm{mod}C$, and keeps $n=C$. It can report the discarded label $C$ as part of its specified result. At step 10 this gives $(D,E,F,G,H)$ with $h=3,n=5,w=3$. The next dequeue() returns $D$, leaving $(E,F,G,H)$ with $h=4,n=4,w=3$. Below full capacity, append_latest follows the ordinary insertion rule without discarding anything.

The lower bars in the trace diagram expose the consequence: $C$ entered at step 4 and remains a member until step 11 under rejection, but only until step 10 under overwrite. $H$ never becomes a member in the rejecting branch; it does in the overwriting branch. The same physical slot can therefore hold different logical items over time. These interfaces are observably different, so representation independence cannot justify exchanging them while retaining the same promised results.

Boost's documented push_back behavior chooses overwrite when full, implemented by assignment to the old element. Its discussion of iterator invalidation illustrates why a reused address need not still identify the original item. Assignment, object destruction, and release of an owned resource are separate language-level concerns; the membership bars make no claim about those lifetimes.^[ref]

A rejecting FIFO queue suits work that must remain pending until explicitly removed. An overwriting circular buffer suits a bounded recent history where losing the oldest retained item is the stated policy. Neither storage wrap nor bounded capacity chooses between those requirements.