Deque (double-ended queue) — operations, use cases
WHAT is a deque?
The four core operations:
| Operation | Meaning |
|---|---|
push_front(x) |
add x at the front |
push_back(x) |
add x at the rear |
pop_front() |
remove & return front element |
pop_back() |
remove & return rear element |
front() / back() |
peek without removing |
HOW is it built? (Derivation from scratch)
You can never "remember" — you must see why each implementation gives it.
Implementation 1 — Doubly Linked List
HEAD <-> [a] <-> [b] <-> [c] <-> TAIL
push_front: create node, splice after HEAD sentinel → .pop_back: TAIL.prev gives the last node directly → .
Why this works: every end-operation touches only 2–3 pointers, independent of size .
Implementation 2 — Circular Dynamic Array (the fast one)
Keep front index, size, capacity C. Indices wrap with modular arithmetic:
When size == C, double the capacity and copy — amortized (same logic as a dynamic array: pushes cost total ).
WHEN do you use one? (Use cases — the 80/20)
Other 20%-that-covers-80% uses:
- Both stack & queue behavior in one structure (undo + redo).
- Palindrome check: compare
pop_front()vspop_back()until they cross. - 0–1 BFS: edges of weight 0 →
push_front, weight 1 →push_back(deque replaces a priority queue). - Steal-work scheduling (work-stealing deques in parallel runtimes).
Worked Examples
Complexity Summary
Recall Feynman: explain to a 12-year-old
Imagine a line of kids holding hands. Normally a new kid joins at the end and the kid at the front leaves first — that's a queue. A deque is a magic line where a kid can join the front OR the back, and leave from the front OR the back, instantly. Nobody in the middle has to shuffle. That's all it is — a line you can poke from both sides.
Active Recall
What does "deque" stand for and how is it pronounced?
What are the four core deque operations?
How does a deque generalize both a stack and a queue?
Why is a doubly linked list needed for an O(1) deque?
In a circular array of capacity C, what is the formula to move front left for push_front?
Index of the k-th element from front in a circular deque?
Why not implement a deque with a plain array + shifting?
Killer use case for a deque and its complexity?
How does a deque solve 0-1 BFS?
What is the amortized cost of push on a dynamic-array deque and why?
Connections
- Stack — restricted deque (one end only)
- Queue — restricted deque (FIFO)
- Circular Buffer / Ring Buffer — the array implementation
- Doubly Linked List — the pointer implementation
- Dynamic Array Amortized Analysis — why doubling gives
- Sliding Window Maximum — flagship application
- 0-1 BFS — graph use case
- Priority Queue — what 0-1 BFS replaces with a deque
Concept Map
Hinglish (regional understanding)
Intuition Hinglish mein samjho
Dekho, deque ka simple matlab hai: ek aisi line jisme tum dono taraf se — front aur rear — dono jagah se element add bhi kar sakte ho aur remove bhi, aur har operation sirf time leta hai. Stack sirf ek end pe kaam karta hai, queue ek end pe daalti doosre se nikaalti hai — deque inn dono ka bada bhai hai jo sab kuch kar sakta hai. Isliye agar tum deque samajh gaye, to stack aur queue automatically samajh aa jaate hain.
Implementation do tarike se hoti hai. Pehla, doubly linked list — har node ko apna prev aur next dono pata hota hai, isliye pop_back me last node tak turant pahunch jaate ho. Singly list me back delete karne ke liye poora chalna padta, isliye double zaroori hai. Doosra tarika circular array hai — yahan data shift nahi karte, sirf front pointer ko move karte hain. Formula yaad rakho: front = (front - 1 + C) mod C. Yeh +C isliye lagaya kyunki agar front 0 ho to -1 aata, jo galat hai; +C se wrap hoke sahi index milta hai.
Sabse bada use case sliding window maximum hai — har window ka max nikaalna me, jisme naye element peeche se aate hain, purane out-of-window front se nikalte hain, aur chhote bekaar element peeche se hat jaate hain. Teen alag ends ka kaam ek saath — sirf deque hi kar sakta hai. Aur 0-1 BFS me weight-0 edge ko push_front, weight-1 ko push_back karke priority queue ki zaroorat hi khatam ho jaati hai.
Ek common galti: "array le lo aur front pe daalne ke liye shift kar do." Yeh chhote example me theek lagta hai, par har push_front ho jaata hai, total — deque ka pura fayda hi gaya. Isliye circular buffer ya doubly linked list use karo. Bas itna yaad rakho aur deque tumhara dost ban jaayega.