A Deque, or double-ended queue, is a generalized version of a Queue. Elements can be added or removed from either the front or the rear, providing maximum flexibility.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
{
"status": "Initializing deque"
}Overview
A deque (pronounced 'deck', short for double-ended queue) allows insertion and removal at both the front and the rear. It generalises both the stack (use one end) and the queue (add at one end, remove at the other).
Deques shine in sliding-window problems. To find the maximum of every window of size k, keep a deque of indices whose values are in decreasing order: drop indices from the front when they leave the window, and drop smaller values from the rear when a larger one arrives. Each index enters and leaves at most once, so the whole scan is O(n).
The default commands add 10 and 20 at the rear, add 5 at the front (giving [5, 10, 20]), remove from the rear (20) and remove from the front (5). Only 10 remains.
Step by step
addFront(x)/addRear(x): insert at either end.removeFront()/removeRear(): remove from either end, handling the empty case.peekFront()/peekRear(): read either end without removing.
Complexity
| Case | Cost | Why |
|---|---|---|
| Add / remove at either end | O(1) | With a doubly linked list or circular buffer. |
| Access by index | O(1) or O(n) | O(1) for array-backed deques, O(n) for linked ones. |
| Space | O(n) | One slot per element. |
When to use it
- Sliding window maximum/minimum problems.
- Palindrome checks: compare and remove from both ends.
- Work-stealing schedulers, where a thread takes work from its own end and others steal from the opposite end.
- Undo histories with a size limit: drop the oldest entry from the front.
Common mistakes
- The visualizer uses
unshiftforaddFront, which is O(n) on a JavaScript array; a real deque uses a circular buffer. - Mixing up which end is the 'front' between functions.
- Not checking for emptiness before removing from either end.
A dry run is the best way to check your understanding of Double-Ended Queue (Deque): follow each row, predict the next one, and compare. The run below takes 12 steps in total. The Line column refers to the line numbers in the code listing above.
- Input
- addRear 10,addRear 20,addFront 5,removeRear,removeFront
- Result
- status = Operations complete, final_deque = [10]
| Step | Line | Array | What happens |
|---|---|---|---|
| 1 | 1 | [] | status = Initializing deque |
| 2 | 8 | [] | action = addRear(10) |
| 3 | 9 | [10] | status = Added 10 to rear, front = 10, rear = 10 |
| 4 | 8 | [10] | action = addRear(20) |
| 5 | 9 | [10, 20] | status = Added 20 to rear, front = 10, rear = 20 |
| 6 | 5 | [10, 20] | action = addFront(5) |
| 7 | 6 | [5, 10, 20] | status = Added 5 to front, front = 5, rear = 20 |
| 8 | 15 | [5, 10, 20] | action = removeRear() |
| 9 | 17 | [5, 10] | status = Removed 20 from rear, front = 5, rear = 10 |
| 10 | 11 | [5, 10] | action = removeFront() |
| 11 | 13 | [10] | status = Removed 5 from front, front = 10, rear = 10 |
| 12 | 24 | [10] | status = Operations complete, final_deque = [10] |
What is a Deque?
What are the primary operations of a Deque?
- addFront: Adds an element to the beginning.
- addRear: Adds an element to the end.
- removeFront: Removes an element from the beginning.
- removeRear: Removes an element from the end.