Deques
A Deque (Double-Ended Queue, pronounced 'deck') is a versatile data structure that combines the capabilities of both a stack and a queue. It supports O(1) insertions and deletions at both ends.
Both Ends Open
A deque — double-ended queue, usually pronounced 'deck' — is a linear structure that permits insertion and removal at both ends in O(1). It exposes four operations: push_front, push_back, pop_front, and pop_back, plus the usual front, back, and size accessors.
That symmetry is the whole definition. Where a stack restricts you to one end and a queue forces entry at one end and exit at the other, a deque removes the restriction and leaves the choice to the caller at each call.
It follows immediately that a deque generalises both. Use only push_back and pop_front and its behaviour is indistinguishable from a queue. Use only push_back and pop_back and it is a stack. Both are the deque with half its interface ignored.
The practical warning is the flip side of that power. Because a deque permits everything, its type signature promises nothing about how the code uses it. Declaring a queue tells the next reader that nothing is ever popped from the back — a fact they would otherwise have to verify by reading every line. Reach for the narrowest structure that fits; use a deque when you genuinely need both ends.
push_front,push_back,pop_front,pop_back— all O(1)- Restricting the interface yields a queue or a stack
- The generality costs you the documentation a narrow type provides
- Choose it when both ends are genuinely needed
The Cost of Generality
Because a deque can act as either a stack or a queue, it is tempting to use one everywhere and stop thinking about the choice. That is worth resisting for a reason that has nothing to do with performance.
A type is a claim about what the code does. Declaring a queue states that nothing is ever removed from the rear — a reader gets that guarantee for free, and the compiler enforces it. Declaring a deque states nothing, so anyone reasoning about the code must read every call site to reconstruct the ordering discipline by hand.
There is a performance dimension too, though a smaller one. A deque must track and bounds-check two ends rather than one, and the block-based implementations described below add a level of indirection on every access. For a hot loop that only ever pushes and pops at one end, a plain dynamic array used as a stack is measurably faster.
The rule that follows is the ordinary one for choosing a data structure: take the narrowest type that expresses the requirement, and widen only when an operation you actually need is missing. Reach for a deque when both ends are genuinely in play — a sliding window, a bounded history, a work-stealing queue — not as a hedge against a requirement that might appear later.
- A narrow type documents and enforces the access discipline
- Two ends mean more bookkeeping and an extra indirection
- A dynamic array beats a deque for pure stack use
- Widen the type when an operation is genuinely needed, not preemptively
How It Is Built
Two implementations dominate, and they trade the same things arrays and linked lists always trade.
A doubly linked list makes the requirement obvious: with head and tail references and a prev pointer in every node, all four operations are a few pointer writes, strictly O(1) with no amortisation and no reallocation. The costs are a pointer pair per element and scattered memory, so iteration suffers cache misses.
The block-based array is what production libraries actually use. Rather than one contiguous buffer, memory is allocated as a sequence of fixed-size chunks, tracked by a map of pointers to those chunks. Growing at either end allocates a new block and records it; the elements inside each block stay contiguous, so iteration is nearly as cache-friendly as a plain array.
This is how C++'s std::deque works, and it explains its unusual guarantee: pushing or popping at either end never invalidates references to existing elements, because no element ever moves — unlike std::vector, where a reallocation invalidates everything. Python's collections.deque is a doubly linked list of fixed-size blocks and is the reason list.pop(0)'s O(n) shift has a fast alternative.
Indexing is where the two diverge sharply. A block-backed deque can compute which block holds element k and reach it in O(1); a linked-list deque cannot, and needs an O(n) walk. If you need both ends and random access, the block implementation is the one that delivers.
| Doubly linked list | Block-based array | |
|---|---|---|
| Push/pop at either end | O(1) strict | O(1) amortised |
| Index element k | O(n) | O(1) |
| Memory per element | Two pointers | Near zero |
| Iteration speed | Cache misses | Near-contiguous |
| Used by | Teaching, intrusive lists | std::deque, collections.deque |
- Doubly linked list — simple, strictly O(1), poor locality
- Block map — contiguous runs, O(1) indexing, cache-friendly
std::dequekeeps references valid across end insertions- Only the block form supports fast random access
Terms, operations, and practical uses
Core capabilities
- Double-EndedPermits insertions and deletions at both the front and the rear boundaries.
- Superset StructureA deque can act purely as a stack (using one end) or purely as a queue (using opposite ends).
- SymmetryAlgorithms that require processing data from both ends simultaneously, like palindrome checking, fit deques perfectly.
Implementation strategies
- Doubly Linked ListThe simplest way to build a deque, providing strict O(1) operations by tracking head and tail nodes.
- Block ArraysThe standard C++ and Python approach. Allocates memory in chunks (blocks) and links the blocks together for cache efficiency.
- Circular DequeImplementing a deque within a single fixed-size array using modulo arithmetic for both front and rear pointers.
Algorithmic uses
- Sliding Window MaximumUsing a deque to store indices of useful elements in a moving window, solving the problem in O(N) time.
- Undo/Redo HistoryUsing a deque to store actions. If the history limit is reached, the oldest action is popped from the front.
- Stealing SchedulerWork-stealing thread pools use deques. A thread pops tasks from the rear of its own deque, but steals from the front of others.
Checking for a Palindrome
from collections import deque
def is_palindrome(word):
d = deque(word)
while len(d) > 1:
if d.popleft() != d.pop():
return False
return True
print('It is a palindrome' if is_palindrome("racecar") else 'Not a palindrome')#include <iostream>
#include <deque>
using namespace std;
bool isPalindrome(string word) {
deque<char> d;
for (char c : word) d.push_back(c);
while (d.size() > 1) {
if (d.front() != d.back()) return false;
d.pop_front();
d.pop_back();
}
return true;
}
int main() {
cout << (isPalindrome("racecar") ? "It is a palindrome" : "Not a palindrome") << endl;
return 0;
}import java.util.*;
class Main {
public static boolean isPalindrome(String word) {
Deque<Character> d = new ArrayDeque<>();
for (char c : word.toCharArray()) d.addLast(c);
while (d.size() > 1) {
if (d.removeFirst() != d.removeLast()) return false;
}
return true;
}
public static void main(String[] args) {
System.out.println(isPalindrome("racecar") ? "It is a palindrome" : "Not a palindrome");
}
}Step through it
Running on Word: 'r a c e c a r'
Read all 12 Steps
- A deque opens both ends A double ended queue supports push and pop at the front and at the back, all in O(1). We use that here to check whether 'racecar' is a palindrome by comparing inward from both ends.
- Read both ends at once front is 'r', back is 'r'. A plain queue could read only the front; a stack only the back. The deque reads both without moving anything, which is what makes this a two-line loop.
- They match — pop both pop_front and pop_back each remove one character in O(1). The word shrinks from the outside in and 'aceca' is left.
- Compare 'a' and 'a' The second pair matches too. Note that no character has been copied or shifted — only the two end pointers moved.
- Pop both again 'cec' remains. Each round removes two characters, so the loop runs n/2 times and the whole check is O(n).
- Compare 'c' and 'c' The third and final pair matches.
- Pop both, one character left A single 'e' remains. An odd-length word always ends this way.
- Stop at size <= 1 The loop condition is size > 1. One character is trivially a palindrome and has nothing to compare against, so the loop ends and the answer is true.
- What a mismatch would do Had any pair differed — 'racecax', where 'r' meets 'x' — the function returns false immediately, without examining the rest. Early exit is why the average case is far below n/2 rounds.
- Even-length words end differently 'abba' pops 'a','a' then 'b','b' and finishes with size 0, not 1. The same condition handles both parities, which is why it is written size > 1 rather than size != 1.
- Using it as a queue Restrict yourself to push_back and pop_front and this same structure is a FIFO queue. Nothing about the implementation changes — only which operations you call.
- Using it as a stack Restrict yourself to push_back and pop_back and it is a LIFO stack. This is why std::stack and std::queue in C++ are adaptors over a deque rather than separate structures.
Sliding Window Maximum
The deque's signature algorithmic use is finding the maximum of every window of size k as it slides across an array. Recomputing each window is O(n·k); the deque brings it to O(n).
The structure holds indices, not values, and is maintained so the values they refer to are in decreasing order. Before pushing index i, repeatedly pop_back while the value at the back is less than or equal to the value at i — those elements can never be the maximum again, because i is both larger and stays in the window longer.
The front is then always the maximum of the current window, readable in O(1). Both ends are doing distinct work simultaneously, which is exactly why neither a stack nor a queue suffices: the back discards dominated candidates, the front discards expired ones.
Expiry is the other half. After pushing, pop_front while the front index is outside the window, i - k. Each index is pushed once and popped once across the entire run, so despite the inner loops the total work is linear.
A deque maintained under an ordering rule like this is called a monotonic deque, and the same shape solves shortest-subarray and constrained-DP problems where a window's best candidate must be tracked as the window moves.
- Store indices, keep their values monotonically decreasing
pop_backremoves dominated candidates;pop_frontremoves expired ones- Front is the window maximum, available in O(1)
- Each index enters and leaves once — O(n) overall