The Deque

A deque pushes and pops at both ends in constant time, and that is the whole of its interface: four operations, nothing reordered, no element ever moved. A stack is a deque with one end ignored. A queue is a deque with the pushes at one end and the pops at the other. That is why a deque sits underneath both in most collection libraries, and why the operations are as cheap as either: a push writes one slot and adjusts one integer. The design work in a deque is all in growth. An array that has wrapped around its own end cannot be extended at either end, and the two ways out of that lead to two different structures.

An array, a start index, and a count

Draw eight boxes in a row and bend the row into a circle so the eighth box sits beside the first. Put an arrow labelled head on one box and write a number, count, beside the circle. The live elements are the count boxes from head forward, travelling clockwise; everything else is free space. Element i of the deque lives at (head + i) mod cap.

The four operations fall straight out of that. Pushing at the back writes element number count and increments the count. Pushing at the front moves head one step anticlockwise, writes there, and increments the count. Popping at the front reads the box head points at, moves head one step clockwise, and decrements the count. Popping at the back reads element count-1 and decrements the count. No element is ever shifted and no index ever moves more than one step, so the invariant holds trivially. The elements present are exactly the slots in that forward range, in that order, and count is between zero and cap.

Keeping a separate count is a departure from the fixed-capacity ring, which gets by with two monotonic indices. There the slot for element i is i & mask and the indices are allowed to run forever, which is what distinguishes a full ring from an empty one without a count. That trick needs the mask to be constant for the life of the structure. A growable deque changes capacity, so the mapping from element number to slot changes with it, and the indices have to be rebased every time the array is replaced. A count costs one integer and one write per operation, and it makes full-versus-empty a comparison rather than an argument.

When count == cap, a push has nowhere to put its element, so the array is replaced by a larger one and the live elements are copied across. The live range may cross the end of the old array, so the copy is two copy calls rather than one. The natural destination is position zero of the new array, writing the elements in logical order, which leaves head at zero and the live range contiguous again. That is the unwrapping, and every growth does it: a deque that has wrapped is straightened out on the way into its new home.

The alternative is to keep the wrap and place the tail segment at the far end of the new array, so the free space lands between the back and the front rather than after the back. It copies the same number of elements and makes the index arithmetic afterwards harder to check, so unwrapping to zero is the version worth writing.

What neither version avoids is that a growth touches every live element. An array of a million large structs is a million struct copies inside one push, and the amortised argument says only that it happens rarely, not that it happens quickly when it happens. The chunked deque is the answer to that, and it is a different structure rather than a tuning of this one.

Blocks instead of one array

Keep the elements in fixed-size blocks, say 64 slots each, and keep a separate array holding a pointer to each block, in order: the block index. The front of the deque lives at some offset inside the first block and the back at some offset inside the last. Pushing at the back writes into the last block, and when that block is full, allocates another and appends its pointer to the index. Pushing at the front does the same thing at the other end. Element i is found by dividing rather than masking: block number (firstOffset+i) / B, then slot (firstOffset+i) % B.

Two properties follow. No operation copies a large number of elements, because the elements never move. The block index does have to grow eventually, and it holds one pointer per B elements, so that copy is a fraction of the size of the single-array copy and moves pointers rather than element values. And the address of an element stays valid for as long as the element is in the deque. A caller can hold a *T into the structure across pushes at either end, which the single-array deque cannot offer at all. Deques in other languages’ standard libraries are often built along these lines. The block size, the growth policy and whether the block index is itself a deque all vary between them, so read the source of the one you are using rather than assuming it matches a description like this one.

What each operation costs

Pushes are amortised rather than worst case for the same reason a dynamic array’s appends are: the capacity grows by a factor rather than a fixed amount, so the total copying across n pushes is a geometric series that sums to a constant multiple of n. The code below doubles. Treat that as this implementation’s choice and not as Go’s policy: the standard library documents append as growing as needed without specifying a factor, and the factor the runtime uses has changed between releases.

Shrinking is the part of the amortised argument people get wrong, because the obvious rule breaks the bound. Halve the array when the count falls to half the capacity, and a caller who alternates one push and one pop across that boundary makes every operation copy every element. Halve it when the count falls to a quarter instead, and there is slack on both sides of the boundary. The next resize in either direction is then a long way off, and the amortised bound survives.

The constants favour the single array, because the slots are adjacent in memory. A traversal of a ring deque is a linear walk through one block of memory with one wrap in it, which is the access pattern hardware prefetchers are built for. The arithmetic per access is an add and a mask, and the mask is why capacities are powers of two. For a non-negative i and a power-of-two cap, i % cap and i & (cap-1) give the same answer, and the bitwise and is one instruction with no division in it. A compiler can make that substitution itself when the capacity is a constant it can see; when the capacity is a struct field decided at construction, it cannot, and the division stays in the loop.

Three costs are specific to Go. A deque cannot hand out its contents as one slice, because the live range may cross the end of the array, so the honest signatures are either two slices or an append-into-caller’s-slice method. Both of those come with the aliasing hazard in its deque-shaped form: a slice handed out over the backing array stays valid only until the next push, and nothing in the type system records that. A method on a value receiver copies the struct, which for this type compiles and then loses every push. The element lands in the shared backing array while the count increment goes into the discarded copy. And where the backing array lives is not something the language settles. A make([]T, n) whose size the compiler cannot see generally goes on the heap, while a fixed-size array field inside a struct that does not escape its function is a candidate for the stack. Both answers come out of escape analysis, which the compiler redoes per build, so go build -gcflags=-m is the only account of what it concluded for the version you are compiling with.

The chunked deque gives up those constants to get its two properties. Access takes a load of the block pointer before the load of the element, iteration is a dependent load at every block boundary, and a push at a boundary allocates. If you want numbers for any of this on your hardware, write the benchmark below and read its output, because the answer belongs to the processor and the allocator rather than to Go.

Problems that need both ends

The sliding-window maximum is the problem the structure was made for. Given a sequence of n numbers and a window of width w, report the maximum inside every window as the window slides one position at a time. Comparing w values per window is O(nw) and is fine until w is large. A heap with lazy deletion adds a logarithmic factor. It also needs a way to recognise the entries that have fallen out of the window, since an expired element reaches the top of the heap only once nothing larger is still live. The deque solution is O(n) total, and it works by holding indices into the sequence rather than values, in an order whose values are strictly decreasing.

When a new element arrives, the back is popped while the index sitting there holds a value no larger than the new one. The new element is both larger and more recent, so none of those indices can be the maximum of any window from here on. They are gone for good rather than set aside. The new index goes on the back. Then the front is checked once and dropped if it has left the window, since at most one index can expire per step. The front index is now the maximum of the window ending at this position. A stack cannot expire the oldest candidate and a queue cannot discard the dominated ones, so neither restriction of the deque is enough.

Work-stealing schedulers give each worker its own deque of pending tasks and divide the ends by owner. The worker pushes new work on one end and takes work from that same end. The task it picks up next is the one it created most recently, which is the one most likely to be in its cache and, in a divide-and-conquer workload, the smallest remaining piece. An idle worker steals from the other end, taking the oldest task, which in the same workload is the largest remaining subtree and so returns the most work for the one synchronised operation. The division of ends is what keeps the common case cheap: the owner’s end is touched by one goroutine, and only the shared end needs atomics.

A bounded history needs both ends for a simpler reason. Think of a browser’s back list, an editor’s undo trail capped at a thousand steps, or a diagnostic ring of the last few hundred events. New entries arrive at one end and, once the bound is reached, the oldest leaves from the other. A stack would grow without limit, and a queue pops the end a reader navigates into.

Breadth-first search on a graph whose edges are all weight zero or weight one does a priority queue’s job with a deque. Push a neighbour reached by a zero-weight edge onto the front and one reached by a weight-one edge onto the back. The deque then stays sorted by distance in two groups, which yields shortest paths with no priority queue and no logarithmic factor anywhere.

When not to, and what instead

Use a plain slice when only one end is live. append and s[:len(s)-1] are a stack, with no type to write and no capacity arithmetic to get wrong, and the slices package covers more of the rest than people expect: slices.Index, slices.BinarySearch, slices.Sort, slices.Reverse, slices.Compact. Indexing by position, sorting, searching and iterating in order all assume one contiguous run of elements with a single start. A structure whose contents are split across the end of an array makes every one of them harder for nothing in return.

Use a fixed-capacity ring when the memory has to be decided in advance. An audio callback or a network driver has no use for growth, and a ring with no resize path has no amortised qualifier on anything and no allocation after construction.

Use a buffered channel for a FIFO handoff between goroutines. make(chan T, 64) is a bounded queue with the blocking written, the memory model satisfied, and no restriction on how many goroutines touch either end. A deque behind a mutex is a worse version of it unless you need an operation a channel does not have.

The deque below is not safe for concurrent use, and the single-producer trick that makes a fixed ring lock-free does not transfer. That trick works because each index has exactly one writer. Here, PushFront and PopFront both write head, and all four operations write count, so no partition of the fields gives each one a single owner. A mutex or a channel is the answer, and a hand-rolled concurrent deque is a research-paper-sized problem rather than an afternoon.

container/list deserves a straight comparison, because a doubly linked list is a deque and gives O(1) at both ends without any of the array arithmetic. It also gives two things this structure cannot: stable element addresses, and removal of an element you already hold in O(1), which is what an LRU cache needs and why the package exists. Against that, its Value field is any, so every element of a value type is boxed and allocated on the way in. Each node is its own allocation, and traversal is a dependent load per element, which the prefetcher cannot help with. Reach for it when you need to splice or to remove from the middle by handle, and not for a plain deque.

Store pointers once the element is large. A ring deque copies each element twice in the ordinary case, once on push and once on pop, and once more for every element alive at a growth. A deque of 4 KB structs moves a lot of memory that a deque of pointers does not. The consequence is that an abandoned slot keeps whatever it points at reachable until something overwrites it, which is what the zeroing in PopFront and PopBack is for.

Do not start with the chunked design. The ring deque is a hundred lines and faster for small elements, and the chunked one is more code to get wrong and more cache misses per traversal. Three situations justify it. Two are properties of the elements: addresses that have to stay valid while the deque changes at either end, or elements large enough that moving all of them at a growth dominates everything else. The third is latency, where a single O(n) copy inside one push is a problem no average smooths over.

Writing it in Go

The type is three fields, and the comment above it is the specification.

// Package dequekit is a growable double-ended queue over one array. Element i
// lives at (head+i) & (len(buf)-1), so the capacity is always a power of two
// and the mask stands in for the modulus. The zero Deque is empty and usable;
// the first push allocates.
package dequekit

import (
	"fmt"
	"math/bits"
)

// minCap is the smallest array the first push allocates. Below 8 the doubling
// runs several times on the way to any useful size.
const minCap = 8

// Deque holds count elements starting at array position head. The invariants,
// which check verifies, are that len(buf) is either 0 or a power of two at
// least minCap, that count is between 0 and len(buf), and that head is inside
// buf (or 0 when there is no buf).
type Deque[T any] struct {
	buf   []T
	head  int
	count int
}

// New returns a Deque with room for at least n elements, rounded up to a power
// of two. The zero Deque works as well; New only skips the early doublings.
func New[T any](n int) *Deque[T] {
	d := &Deque[T]{}
	switch {
	case n > minCap:
		d.buf = make([]T, 1<<bits.Len(uint(n-1)))
	case n > 0:
		d.buf = make([]T, minCap)
	}
	return d
}

func (d *Deque[T]) Len() int { return d.count }
func (d *Deque[T]) Cap() int { return len(d.buf) }

// slot returns the array position of element i, for any i the caller can
// justify. It is arithmetic, not a bounds check.
func (d *Deque[T]) slot(i int) int {
	return (d.head + i) & (len(d.buf) - 1)
}

The pushes and pops are short enough that the comments carry more than the code does.

// PushBack adds v after the last element. The receiver is a pointer because a
// value receiver copies the struct: the element would land in the shared
// backing array while the count increment went into the copy, which compiles
// and loses every push.
func (d *Deque[T]) PushBack(v T) {
	if d.count == len(d.buf) {
		d.resize(d.growTo())
	}
	d.buf[d.slot(d.count)] = v
	d.count++
}

// PushFront adds v before the first element.
func (d *Deque[T]) PushFront(v T) {
	if d.count == len(d.buf) {
		d.resize(d.growTo())
	}
	// head-1 can be negative, and the mask is not used on it: the branch says
	// what is meant without depending on how a negative int is represented.
	h := d.head - 1
	if h < 0 {
		h += len(d.buf)
	}
	d.head = h
	d.buf[h] = v
	d.count++
}

// PopFront removes and returns the first element. The zero assignment matters
// for any T holding a reference: without it the abandoned slot keeps the
// element reachable from the backing array until some later push overwrites
// that slot.
func (d *Deque[T]) PopFront() (T, bool) {
	var zero T
	if d.count == 0 {
		return zero, false
	}
	v := d.buf[d.head]
	d.buf[d.head] = zero
	d.head = d.slot(1)
	d.count--
	d.shrink()
	return v, true
}

// PopBack removes and returns the last element.
func (d *Deque[T]) PopBack() (T, bool) {
	var zero T
	if d.count == 0 {
		return zero, false
	}
	i := d.slot(d.count - 1)
	v := d.buf[i]
	d.buf[i] = zero
	d.count--
	d.shrink()
	return v, true
}

func (d *Deque[T]) Front() (T, bool) {
	var zero T
	if d.count == 0 {
		return zero, false
	}
	return d.buf[d.head], true
}

func (d *Deque[T]) Back() (T, bool) {
	var zero T
	if d.count == 0 {
		return zero, false
	}
	return d.buf[d.slot(d.count-1)], true
}

// At returns element i counting from the front. It panics outside the range,
// the way a slice index does, rather than returning a zero value the caller
// cannot tell apart from a stored one.
func (d *Deque[T]) At(i int) T {
	if i < 0 || i >= d.count {
		panic(fmt.Sprintf("dequekit: index %d out of range for %d elements", i, d.count))
	}
	return d.buf[d.slot(i)]
}

// Append appends the elements, front to back, to dst. A deque cannot return
// one slice of its own storage, because the live range may cross the end of
// the array and the two halves are not adjacent.
func (d *Deque[T]) Append(dst []T) []T {
	if d.count == 0 {
		return dst
	}
	first := min(d.count, len(d.buf)-d.head)
	dst = append(dst, d.buf[d.head:d.head+first]...)
	return append(dst, d.buf[:d.count-first]...)
}

Growth, shrink and resize hold the three decisions, and each one reads in the comment rather than in the code.

// growTo doubles the capacity, or allocates minCap for an empty deque. The
// factor is this implementation's choice: the standard library documents
// append as growing as needed without specifying a factor, and the one the
// runtime uses has changed between releases, so nothing here should be read as
// the language's policy.
func (d *Deque[T]) growTo() int {
	if len(d.buf) == 0 {
		return minCap
	}
	return len(d.buf) * 2
}

// shrink halves the array once the elements fit in a quarter of it. A quarter
// rather than a half: halving at count == cap/2 lets a caller alternate one
// push and one pop across the boundary and copy every element on each
// operation, which breaks the amortised bound.
func (d *Deque[T]) shrink() {
	if c := len(d.buf); c > minCap && d.count <= c/4 {
		d.resize(c / 2)
	}
}

// resize moves the live elements into a new array of newCap slots and rebases
// head to 0. Two copies, because the live range may cross the end of the old
// array; writing them in logical order from position 0 is the unwrapping, and
// it leaves the arithmetic afterwards identical to a deque that never wrapped.
// newCap must be at least count. min is a builtin from Go 1.21.
func (d *Deque[T]) resize(newCap int) {
	buf := make([]T, newCap)
	first := min(d.count, len(d.buf)-d.head)
	n := copy(buf, d.buf[d.head:d.head+first])
	copy(buf[n:], d.buf[:d.count-first])
	d.buf = buf
	d.head = 0
}

// check verifies the structural invariants and is called by the tests after
// every mutation. It says nothing about the elements, because no constraint on
// T lets it compare them; the tests check the abandoned slots themselves,
// where T is known to be comparable.
func (d *Deque[T]) check() error {
	c := len(d.buf)
	if c != 0 && (c < minCap || c&(c-1) != 0) {
		return fmt.Errorf("capacity %d is not a power of two at least %d", c, minCap)
	}
	if d.count < 0 || d.count > c {
		return fmt.Errorf("%d elements in an array of %d", d.count, c)
	}
	if c == 0 && d.head != 0 {
		return fmt.Errorf("head is %d with no array", d.head)
	}
	if c != 0 && (d.head < 0 || d.head >= c) {
		return fmt.Errorf("head is %d, outside an array of %d", d.head, c)
	}
	return nil
}

The sliding-window maximum is a couple of dozen lines on top of that, and the zero Deque means it needs no constructor.

// WindowMax returns the maximum of every window of width w over xs, left to
// right. It holds indices into xs rather than values, because expiry is
// decided by position; the values at those indices are strictly decreasing,
// which is what makes the front index the answer.
func WindowMax(xs []int, w int) []int {
	if w <= 0 || w > len(xs) {
		return nil
	}
	out := make([]int, 0, len(xs)-w+1)
	var d Deque[int]
	for i, x := range xs {
		// Discard from the back every index this element dominates: it is both
		// larger and more recent, so none of them is the maximum of any window
		// from here on. Each index is pushed once and popped once, which is
		// where the linear total comes from.
		for {
			j, ok := d.Back()
			if !ok || xs[j] > x {
				break
			}
			d.PopBack()
		}
		d.PushBack(i)
		// At most one index leaves the window per step, so one check.
		if j, _ := d.Front(); j <= i-w {
			d.PopFront()
		}
		if i >= w-1 {
			j, _ := d.Front()
			out = append(out, xs[j])
		}
	}
	return out
}

How to test it

The defects this structure ships are off-by-one errors in the index arithmetic, and they produce correct-looking output for a long time before they produce a wrong element. So the first thing to write is the invariant checker, and the second is a harness that calls it after every mutation. Everything below is in dequekit_test.go in the same package, which is what lets the tests reach buf, head, count and check.

Table-driven tests cover the boundaries you can name, and for a deque those are all about where the live range sits relative to the end of the array. A script of single-character operations keeps the table readable: f and b push the next value at the front and the back, F and B pop.

package dequekit

import (
	"fmt"
	"math/rand/v2"
	"slices"
	"testing"
)

func run(t *testing.T, d *Deque[int], script string) {
	t.Helper()
	next := 1
	for i, op := range script {
		switch op {
		case 'f':
			d.PushFront(next)
			next++
		case 'b':
			d.PushBack(next)
			next++
		case 'F':
			d.PopFront()
		case 'B':
			d.PopBack()
		default:
			t.Fatalf("script position %d: unknown operation %q", i, op)
		}
		if err := d.check(); err != nil {
			t.Fatalf("after %q at position %d: %v", op, i, err)
		}
	}
}

func TestOrderAcrossTheWrap(t *testing.T) {
	tests := []struct {
		name   string
		script string
		want   []int
	}{
		{"empty", "", nil},
		{"back only", "bbb", []int{1, 2, 3}},
		{"front only", "fff", []int{3, 2, 1}},
		{"alternating ends", "bfbf", []int{4, 2, 1, 3}},
		{"one front push wraps immediately", "f", []int{1}},
		{"full, drained at the front, refilled at the front", "bbbbbbbbFFff",
			[]int{10, 9, 3, 4, 5, 6, 7, 8}},
		{"grown past the first array", "bbbbbbbbbb",
			[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}},
		{"drained to empty", "bbbfffFFFBBB", nil},
		{"pops on an empty deque", "FBFB", nil},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			var d Deque[int]
			run(t, &d, tt.script)
			if got := d.Append(nil); !slices.Equal(got, tt.want) {
				t.Errorf("contents %v, want %v", got, tt.want)
			}
		})
	}
}

The one invariant check cannot express is that the slots outside the live range hold the zero value, because it has no constraint on T that allows a comparison. A helper in the test file does it where T is known.

// requireZeroedOutside checks that a popped element is not left reachable from
// the backing array. The map is used as a set and never iterated in order:
// Go does not specify map iteration order or guarantee it repeats, and the
// runtime randomises it, so a test that depends on an order fails
// intermittently.
func requireZeroedOutside[T comparable](t *testing.T, d *Deque[T]) {
	t.Helper()
	var zero T
	live := make(map[int]bool, d.count)
	for i := range d.count {
		live[d.slot(i)] = true
	}
	for i := range d.buf {
		if !live[i] && d.buf[i] != zero {
			t.Fatalf("slot %d, outside the live range, holds %v", i, d.buf[i])
		}
	}
}

The randomised test against a reference implementation finds more than any table. The reference is the thing the deque exists to replace: a slice grown by prepending at the front and appending at the back. It is correct by inspection and quadratic by construction, which is what a reference should be.

func TestAgainstAPrependReference(t *testing.T) {
	rng := rand.New(rand.NewPCG(1, 2))
	var d Deque[int]
	var ref []int
	next := 1
	for step := range 20000 {
		switch rng.IntN(4) {
		case 0:
			d.PushFront(next)
			// A fresh array and a full copy on every prepend, which is the
			// reference's whole method. Reslicing ref below means a later
			// append can write into spare capacity of an array ref no longer
			// starts at; that is safe only because nothing else holds it.
			ref = append([]int{next}, ref...)
			next++
		case 1:
			d.PushBack(next)
			ref = append(ref, next)
			next++
		case 2:
			got, ok := d.PopFront()
			if len(ref) == 0 {
				if ok {
					t.Fatalf("step %d: PopFront returned %v from an empty deque", step, got)
				}
				break
			}
			if !ok || got != ref[0] {
				t.Fatalf("step %d: PopFront gave (%v, %v), want (%v, true)", step, got, ok, ref[0])
			}
			ref = ref[1:]
		case 3:
			got, ok := d.PopBack()
			if len(ref) == 0 {
				if ok {
					t.Fatalf("step %d: PopBack returned %v from an empty deque", step, got)
				}
				break
			}
			last := ref[len(ref)-1]
			if !ok || got != last {
				t.Fatalf("step %d: PopBack gave (%v, %v), want (%v, true)", step, got, ok, last)
			}
			ref = ref[:len(ref)-1]
		}
		if err := d.check(); err != nil {
			t.Fatalf("step %d: %v", step, err)
		}
		if got := d.Append(nil); !slices.Equal(got, ref) {
			t.Fatalf("step %d: contents %v, want %v", step, got, ref)
		}
	}
	requireZeroedOutside(t, &d)
}

A fuzz target is worth adding even though a deque is not a parser, because the input it needs is an operation script and a script is a byte string. The fuzzer then searches the space of operation sequences rather than a space you thought of, and it keeps whatever it finds in testdata as a regression case.

func FuzzOperationScript(f *testing.F) {
	f.Add([]byte("bbbfffFFBB"))
	f.Add([]byte("bbbbbbbbbFFFFFFFF"))
	f.Fuzz(func(t *testing.T, script []byte) {
		// Bound the work per input: a long script here finds nothing the
		// fuzzer cannot find in a short one, and slow inputs starve the run.
		if len(script) > 4096 {
			script = script[:4096]
		}
		var d Deque[int]
		var ref []int
		next := 1
		for _, op := range script {
			switch op % 4 {
			case 0:
				d.PushFront(next)
				ref = append([]int{next}, ref...)
				next++
			case 1:
				d.PushBack(next)
				ref = append(ref, next)
				next++
			case 2:
				if got, ok := d.PopFront(); ok {
					if len(ref) == 0 || got != ref[0] {
						t.Fatalf("PopFront gave %v, reference holds %v", got, ref)
					}
					ref = ref[1:]
				} else if len(ref) != 0 {
					t.Fatalf("PopFront reported empty, reference holds %v", ref)
				}
			case 3:
				if got, ok := d.PopBack(); ok {
					if len(ref) == 0 || got != ref[len(ref)-1] {
						t.Fatalf("PopBack gave %v, reference holds %v", got, ref)
					}
					ref = ref[:len(ref)-1]
				} else if len(ref) != 0 {
					t.Fatalf("PopBack reported empty, reference holds %v", ref)
				}
			}
			if err := d.check(); err != nil {
				t.Fatal(err)
			}
		}
		if got := d.Append(nil); !slices.Equal(got, ref) {
			t.Fatalf("contents %v, want %v", got, ref)
		}
	})
}

The benchmark exists to demonstrate the asymptotic difference rather than to produce a number to quote. Build the same deque two ways at three sizes and read the ratios between sizes, not the nanoseconds.

// sink keeps the loops below from being eliminated as dead code.
var sink any

func BenchmarkBuildFromTheFront(b *testing.B) {
	for _, n := range []int{64, 1024, 16384} {
		b.Run(fmt.Sprintf("deque/%d", n), func(b *testing.B) {
			b.ReportAllocs()
			for range b.N {
				d := New[int](0)
				for i := range n {
					d.PushFront(i)
				}
				sink = d
			}
		})
		b.Run(fmt.Sprintf("prepend/%d", n), func(b *testing.B) {
			b.ReportAllocs()
			for range b.N {
				var s []int
				for i := range n {
					s = append([]int{i}, s...)
				}
				sink = s
			}
		})
	}
}

Run it with go test -bench BuildFromTheFront -benchmem. Multiplying n by 16 should multiply the deque’s time by roughly 16 and the prepend version’s by something nearer 256, with the prepend ratio climbing towards 256 as n grows and the per-allocation overhead stops dominating. The allocation counts tell the same story: the deque allocates once per doubling, the reference at least once per element. A ratio holding across three sizes is evidence about the structure. A single ns/op is a measurement of one machine on one day, with one Go version and one allocator, and it belongs in a commit message rather than in a document.

Two things the test suite above deliberately does not do. It never runs the deque under -race. Nothing in it is shared, and the race detector reports only the overlapping accesses a particular run performs. The documented claim is that the type is not safe for concurrent use. The test for a mutex-wrapped version belongs with the wrapper, run under -race with -count so the goroutines interleave differently each time. And it does not test the chunked variant, which is a separate type with separate invariants: a block index of the right length, no empty block in the middle, and offsets inside their blocks. Written as a second implementation behind the same four operations, it can share this file’s reference test and its fuzz target. That shared harness is the strongest argument for keeping the operation script as a byte string.