Deque

Also known as: double-ended queue

On this page 7

A deque, short for double-ended queue, is an abstract data type that allows elements to be added and removed at both ends in constant time. Among data structures in programming, the deque generalizes both the stack and the queue: restricting it to one end gives last-in, first-out behavior, while inserting at one end and removing at the other gives first-in, first-out behavior.

The name is usually pronounced like “deck” to distinguish it from the dequeue operation. Deques appear in standard libraries of most mainstream languages and power algorithms such as sliding window maximum, work-stealing schedulers and 0-1 breadth-first search.

Core operations of a deque

A deque exposes a small, symmetric set of operations that act on its front and back ends. In a well-implemented deque, each of these operations runs in O(1) time, either strictly or amortized, regardless of how many elements the structure holds.

The table below lists the standard operations with their usual names and costs.

OperationEffectTypical complexity
Push frontInserts an element at the frontO(1) amortized
Push backInserts an element at the backO(1) amortized
Pop frontRemoves and returns the front elementO(1)
Pop backRemoves and returns the back elementO(1)
Peek front or backReads an end element without removing itO(1)
Random access by indexReads the element at position iO(1) or O(n), by implementation
Standard deque operations

Operations on an empty deque must be defined explicitly: some libraries throw an exception, others return a sentinel value, and some leave the behavior undefined. Insertion or removal in the middle of a deque is not part of the core contract and usually costs O(n) time.

How deques are implemented

A deque is an abstract interface, so its performance depends on the underlying representation. Three implementation strategies dominate in practice, each with different trade-offs in memory layout, cache behavior and index access.

A circular buffer stores elements in a contiguous array and tracks head and tail indices that wrap around using modular arithmetic. When the buffer fills, it is reallocated at roughly double the capacity, which keeps pushes amortized O(1). A doubly linked list gives strict O(1) operations at both ends but scatters nodes across memory. A segmented array, also called a block list, keeps a central map of pointers to fixed-size blocks and grows at either end by adding blocks.

ImplementationIndex accessMemory localityMain drawback
Circular bufferO(1)Excellent, contiguousOccasional full reallocation
Doubly linked listO(n)Poor, scattered nodesTwo pointers of overhead per element
Segmented arrayO(1)Good within blocksMore complex bookkeeping
Deque implementation strategies compared

The C++ std::deque typically uses the segmented approach, which guarantees that references to elements remain valid when pushing at either end. Java’s ArrayDeque and Rust’s VecDeque use circular buffers, while Python’s collections.deque uses a doubly linked list of fixed-size blocks, a hybrid that combines low allocation overhead with stable end operations.

Deque compared with stack, queue and dynamic array

A deque is best understood alongside the neighboring structures it can replace. It offers a superset of stack and queue capabilities, at the price of a slightly more complex implementation and, in some languages, somewhat higher constant factors.

StructureInsert positionsRemove positionsAccess pattern
StackTop onlyTop onlyLast in, first out
QueueBack onlyFront onlyFirst in, first out
DequeFront and backFront and backEither discipline, or mixed
Dynamic arrayBack efficientlyBack efficientlyFast random access
Priority queueAny, ordered by keyHighest priority onlyOrdered by priority, not position
Deque and related linear structures

The most frequent practical confusion is between a deque and a dynamic array. Inserting at the front of a dynamic array shifts every element and costs O(n), so code that repeatedly prepends to a Python list or Java ArrayList should switch to a deque instead.

Algorithms that rely on a deque

Several important algorithms depend on the ability to work at both ends efficiently. In these cases, a stack or queue alone would either fail or lose its complexity guarantee.

  • Sliding window maximum or minimum: a monotonic deque keeps candidate indices in decreasing order, giving O(n) total time for all windows.
  • 0-1 BFS: edges with weight 0 push to the front and edges with weight 1 push to the back, finding shortest paths in O(V + E).
  • Work-stealing schedulers: each worker pops tasks from its own end while idle workers steal from the opposite end, reducing contention.
  • Undo and redo histories with a size cap: new actions go to one end and the oldest entries are discarded from the other.
  • Palindrome checking: characters are compared by popping simultaneously from front and back.

Choosing and using a deque correctly

Selecting a deque is a matter of matching the access pattern of the workload to the structure. The decision table below covers common situations.

SituationRecommended structureReason
Frequent inserts and removals at both endsDequeO(1) at each end
Mostly random index access, appends onlyDynamic arrayBetter locality and simpler layout
Fixed-size recent historyBounded dequeOldest items drop automatically
Removal by priorityPriority queueDeque has no ordering by key
Many threads sharing tasksConcurrent dequeLock-free or work-stealing variants
When a deque is the right choice

Common mistakes include indexing into the middle of a linked-list-based deque in a loop, which silently turns an O(n) algorithm into O(n squared), and iterating while modifying the deque, which many libraries reject with an exception. Developers should also remember that a bounded deque discards elements without warning once its maximum length is reached, as collections.deque does with its maxlen parameter.

The idea in brief

A deque is like a line of people with two open ends. Newcomers may join at either end. People may also leave from either end. A normal queue only lets people join at the back and leave at the front. A stack is like a pile of plates where you only touch the top.

Because a deque allows both ends, it can act as a queue, a stack or a mix of the two. Programmers use it to add or remove items quickly at both ends of a list.

A practical scenario

An engineer at a network monitoring company builds a dashboard that shows the highest latency in the last 60 seconds for each of 5,000 servers, with new measurements arriving every second. Recomputing the maximum over all 60 values for every server each second would mean 300,000 comparisons per second and wasted CPU time.

Instead, the engineer keeps a monotonic deque per server. Each new measurement removes smaller values from the back before being appended, and measurements older than 60 seconds are removed from the front. The current maximum is always the front element, so each update costs amortized O(1), and the service handles the full fleet on a single small instance with steady, predictable CPU usage.