A queue looks simple until both ends need to be cheap.
With an Array, appending at the end is a natural fit for its contiguous storage. Repeatedly inserting or removing at the front is different: existing elements may need to move. Swift Collections provides Deque for workloads where both ends matter.
The interesting part is not just that Deque has prepend and popFirst. Its public API still feels much like an array: integer indices, random access, value semantics, slices, and familiar collection protocols. Under that interface, however, the elements live in a circular buffer.
That storage choice explains most of the design.
A queue without giving up collection semantics
A basic work queue can use both ends directly:
import DequeModule
var jobs: Deque<String> = [
"resize-avatar",
"generate-preview"
]
jobs.append("send-email")
jobs.prepend("refresh-token")
while let job = jobs.popFirst() {
print(job)
}prepend(_:) is amortized O(1). popFirst() is O(1) when the deque uniquely owns its storage, and O(count) when copy-on-write first has to make a private copy.
Those details matter because Deque is a value type. Cheap operations at the ends do not mean mutations can ignore Swift’s value semantics.
Logical indices are not physical positions
Deque conforms to RandomAccessCollection, and its indexing model is deliberately familiar:
let values: Deque = [10, 20, 30]
values.startIndex // 0
values.endIndex // 3
values[1] // 20The public index is an Int. startIndex is always zero, and endIndex is the element count.
Internally, that index does not directly name a memory position.
The storage tracks a start slot inside its buffer. A logical offset is translated into a physical slot relative to that start. When the end of the allocated buffer is reached, storage wraps around to the beginning.
Imagine a capacity of eight where the first logical element currently lives in physical slot six:
physical slot: 0 1 2 3 4 5 6 7
stored value: C D . . . . A B
logical index: 0 1 2 3
logical value: A B C DThe caller still sees 0...3. The ring-buffer machinery handles the split.
This separation is what lets the collection keep array-like indices without forcing the first element to remain at the first physical address.
Why the buffer is circular
Prepending to a contiguous array usually means creating room before the first element. A circular buffer can instead move its logical start backward into available capacity.
The current prepend(_:) implementation first ensures that storage is unique and has room for one more element. It then inserts through the deque’s internal storage handle. The documentation specifies amortized O(1) behavior because capacity grows exponentially.
Removing the first element works in the opposite direction: once storage is unique, the implementation removes the element at the logical front and advances the stored start position rather than shifting every remaining element toward zero.
The same storage therefore supports efficient operations at either end.
This is not a claim that Deque is generally faster than Array. Swift Collections’ own documentation makes the narrower distinction: mutations near the front are expected to be significantly faster in a deque, while arrays may be slightly faster for general random-access lookups.
The right structure depends on the workload.
One logical collection can occupy two memory segments
Wrapping introduces a consequence: a deque is not necessarily contiguous in memory.
The implementation handles storage as one or two segments. If the logical sequence crosses the end of the allocation, its first segment runs from the current start slot to the physical end, and its second segment continues from physical slot zero.
The custom iterator in Deque+Collection.swift is built around this fact. It walks directly through the current storage segment. When it reaches that segment’s end, _swapSegment() switches to the wrapped segment.
That avoids repeatedly converting each public integer index into a storage slot during iteration.
The same two-segment model appears when Deque copies its contents into a ContiguousArray: it copies the first segment and then, when present, the second.
Random access does not imply contiguous storage
This distinction is easy to miss.
RandomAccessCollection describes the cost of moving between indices. It does not promise that the elements occupy one continuous memory region.
Deque can calculate a physical slot from a logical offset in constant time, so it can provide random access even when its ring buffer wraps.
The implementation makes that difference visible through withContiguousStorageIfAvailable.
let result = values.withContiguousStorageIfAvailable { buffer in
buffer.reduce(0, +)
}The closure only runs when the deque’s current logical contents form a contiguous physical region. If they wrap around the end of the circular allocation, the method returns nil.
That API is useful precisely because contiguity is a runtime property of the current storage layout, not part of the collection’s general contract.
Value semantics require copy-on-write
The circular buffer lives in reference-backed storage, but Deque itself behaves as a Swift value.
Consider two copies:
import DequeModule
var original: Deque = [1, 2, 3]
var copy = original
copy.prepend(0)
print(original) // [1, 2, 3]
print(copy) // [0, 1, 2, 3]Initially, both values can share the same underlying storage. A mutation calls into ensureUnique. If another deque still references that storage, the mutating value receives its own copy before the change proceeds.
You can see the cost reflected in the API documentation. Reading an element is O(1). Writing an element is O(1) when storage is uniquely owned, but O(count) when shared storage has to be copied. The same qualification appears on popFirst().
So the ring buffer solves movement at the ends, while copy-on-write solves a different problem: preserving independent value semantics without eagerly copying storage every time a deque value is assigned.
The buffer also owns initialization correctly
The internal _DequeBuffer<Element> is a ManagedBuffer carrying a header plus element storage.
Its deinitializer is a small but useful piece of code to read. It checks whether the initialized elements occupy one physical region or wrap around. A contiguous region is deinitialized in one range. A wrapped deque deinitializes the tail region first and then the region at the start of the buffer.
This is where the abstract ring-buffer picture becomes a concrete memory-management problem. Logical ordering is simple; initialized memory may still be split across two physical ranges.
Collection operations can use the shorter side
A ring buffer is useful beyond prepend and popFirst.
Deque also conforms to RangeReplaceableCollection. Its replaceSubrange implementation can make room by shifting elements before or after the changed range. The source explicitly describes the goal as minimizing how many existing elements need to move.
That is another consequence of having space available on both sides of the logical sequence. The implementation can reason about which side of a mutation is cheaper to rearrange rather than always treating the physical beginning of storage as fixed.
When Deque fits
Deque is a natural choice for queues, work lists, traversal frontiers, buffers, and other structures that frequently add or remove values at both ends.
It is less compelling when the workload mostly appends and iterates, or when guaranteed contiguous storage is important. In those cases, Array may already match the problem better.
There is also no public capacity property. Swift Collections deliberately treats the exact storage capacity as an implementation detail, although reserveCapacity(_:) is available when the expected element count is known.
That keeps application logic focused on the collection’s behavior instead of depending on the current buffer layout.
Source worth reading
Start with Deque.swift for the public model and documented trade-offs.
Then Deque+Collection.swift shows how logical integer indices, direct storage access, iteration, copy-on-write mutation, and optional contiguous access fit together.
Deque+Extras.swift contains the front-oriented operations, including popFirst() and prepend. Finally, _DequeBuffer.swift exposes the reference-backed ManagedBuffer that owns the circular storage.
The implementation is a useful example of a common Swift pattern: a value-semantic public type backed by carefully managed reference storage.
Project health
Swift Collections is an Apple and Swift project repository under the Apache License 2.0 with Runtime Library Exception.
The current main branch uses Swift tools 6.4 and contains stable collection modules alongside explicitly marked experimental components controlled by package traits. That distinction matters: this article is about the established Deque API, not the repository’s experimental container work.
The repository’s current Deque documentation describes it as an ordered random-access collection with copy-on-write value semantics and circular-buffer storage.
Engineering takeaway
The useful lesson in Deque is how little of the storage model leaks into the public collection model.
Callers get integer indices starting at zero, random access, value semantics, and familiar Swift collection protocols. Internally, the first element may live anywhere in the allocation, the logical sequence may wrap into two physical segments, and a mutation may first need to detach shared storage.
Those are separate concerns, and the implementation keeps them separate.
The ring buffer makes both ends practical. Index translation hides the ring. Copy-on-write preserves value semantics. The iterator understands split storage without exposing it to callers.
That combination is what makes Deque feel ordinary from the outside while solving a storage problem that Array is not designed around.