Overview
A Deque is a double-ended queue. It supports pushing and popping from either end, commonly using a circular buffer or linked block representation.
FoundationSource checked
Deque
Stores items so insertion and removal are efficient at both the front and the back.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Beginner
- Family
- Linear Collection
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
Core Concepts
frontbackcircular bufferboth-end access
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(1)
Worst
O(1)
Space
O(n)
When to Use
- Use it for sliding windows, work queues, and algorithms that need both-end access.
- Use it when stack and queue behavior are both needed.
- Use it for monotonic queue patterns.
When Not to Use
- Avoid it when random access is the main operation and the implementation does not support it efficiently.
- Avoid it when a simpler stack or FIFO queue is enough.
- Avoid linked implementations when allocation overhead dominates.
What It Does
- Stores items so insertion and removal are efficient at both ends
- Uses front operation and back operation to guide the work.
- Produces stored structure.
Use Cases
- Fast lookup
- Maintaining ordered data
- Representing graphs or spatial data
Inputs
- Items
- Keys or indexes
- Operations to support
Outputs
- Stored structure
- Query results
- Updated state
Key Formulas (1)
Circular index
index = (base + offset) mod capacity
index = (base + offset) mod capacityMaps logical deque positions into a circular array.
Pseudocode
- 1.Prepare the inputs and state needed for Deque.
- 2.Apply the front operation step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return stored structure.
Canonical Example
- Input
- pushBack(A), pushFront(B), popBack()
- Output
- A
- Explanation
- The deque supports insertion at both ends; after B is placed at the front, A remains at the back.
Implementation Notes
- Track size separately from head and tail indices.
- Test alternating push and pop operations at both ends.
- Resize circular buffers by copying elements in logical order.
Common Pitfalls
- Mishandling wraparound indices in circular-buffer implementations.
- Confusing front and back semantics in tests.
- Letting empty and full states look identical without tracking size.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the structure layout and how operations move through or update it.
Step 1 of 4: Prepare the inputs and state needed for Deque.
data-structures-mechanismNotes
Deque operations are useful building blocks for BFS variants and sliding-window algorithms.
Sources (1)
What each reference supports for this entry.
CLRS
BookTextbook reference for the algorithmic family and analysis of Deque.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsed byBreadth-First Search
A deque or queue supports breadth-first frontier order.
Conceptual neighborCircular Buffer
Circular buffers are a common way to implement deque-like storage.
Related Algorithms
Tags
Data StructureQueueBufferClassic