Queue & deque
Scenario
Think of waiting in line at a grocery store. The first person to line up is the first to check out.
How do we build a structure that strictly respects this 'first come, first served' fairness?
Why it exists
Problem: Some problems require strict chronological fairness (processing exactly in order of arrival). A naive array queue takes O(n) to dequeue because removing the front element forces shifting all remaining elements to the left.
Naive approach: Using a standard array and removing from the front, which requires shifting all remaining elements left in O(n) time.
Better idea: Use a circular buffer with head/tail pointers, or a doubly-linked list. A Double-Ended Queue (Deque) generalizes this, allowing O(1) insertions and deletions from both ends simultaneously.
Mental model
A queue is a checkout line at a grocery store (First-In-First-Out). A deque is a line where people can join or leave from both the front and the back.
The Queue ADT enforces a FIFO policy (insert at tail, remove at head). To avoid O(n) array shifts, an array-based circular queue wraps pointers using modulo arithmetic (`ptr = (ptr + 1) % cap`). Python's `collections.deque` uses a hybrid linked list of memory blocks. Java's `ArrayDeque` uses a circular array, vastly outperforming legacy `LinkedList` queues due to cache locality.
Repeated decision: For FIFO: append to the tail, pop from the head. For Deque: choose the optimal boundary (front or back) to insert or extract.
Explanation
While Stacks enforce LIFO chronological reversal, Queues enforce strict FIFO fairness. The foundational engineering hurdle of queues is that popping from the front of an array is destructive, requiring an O(n) shift to fill the gap.
To bypass this, systems implement queues either through pointers (linked lists) or via mathematical pointer wrapping (circular buffers with modulo arithmetic). The Deque (Double-Ended Queue) represents the ultimate generalization, allowing O(1) modifications at both boundaries. Because of this dual-access property, deques are fundamentally required for complex range limit algorithms like Sliding Window Maximum, which need to expire elements chronologically from the front while enforcing monotonicity from the back.
The flagship hard application of a deque is the monotonic sliding-window technique. To find the maximum in a sliding window of size k: keep a deque of indices; before reading the front, pop it if it's outside the window (`front <= i - k`); before pushing i, pop from the back while the back's value < arr[i] so the deque stays decreasing; the front is always the window max.
Deep dive
**Deque vs Dequeue** — There is a notoriously confusing naming overlap in queues. To **dequeue** (verb) is the action of removing an item from a queue. A **deque** (noun, pronounced "deck") is a Double-Ended Queue data structure. When someone asks about a "dequeue in data structure", they almost always mean the Deque (the double-ended buffer), not the action of removing an item.
A deque is a data structure. To dequeue is an action.
Key points
- Invariant: Elements are processed strictly First-In-First-Out (FIFO), or from both ends (Deque).
- Complexity: O(1) time for enqueue and dequeue operations.
- Gotcha: Removing from the front of a naive array is O(n); a proper queue uses pointers or a linked structure.
Pattern: FIFO and Double-Ended Buffering
Recognition cues:
- Processing level-by-level (BFS)
- Maintaining a moving window of data
- Strict fairness guarantees
Failure signals
- Using standard array `.pop(0)` in Python or `ArrayList.remove(0)` in Java, causing catastrophic O(n) shifts.
Engineering examples
Task Scheduling & Message Brokers
Distributing asynchronous work fairly
Message brokers like RabbitMQ and Celery use FIFO queues so work is generally processed in arrival order (strict ordering can relax under multiple consumers or requeues, but the queue is the core primitive).
Sliding Window Maximums
Maintaining trailing state constraints
A Monotonic Deque dynamically manages temporal expiration at the front boundary and magnitude superiority at the back boundary.
Common mistakes
- Using Naive Arrays for Queues: Dequeueing from the front of a naive dynamic array leaves a gap, requiring an O(n) shift of all elements. Always use `collections.deque` or `ArrayDeque`.
- Using Java's LinkedList: While functionally a queue, `LinkedList` causes severe memory fragmentation and cache misses. Java officially advises using `ArrayDeque`.
Recall questions
- What is the defining property of a Queue?
- How does a circular array queue prevent O(n) shifting penalties?
- Why is a Deque fundamentally more powerful than a standard Queue or Stack?
Questions & answers
Find the maximum in each sliding window of size k.
Use a Monotonic Deque storing indices. Expire old elements from the front. Evict smaller elements from the back to maintain decreasing order. The front is always the max.
Approach: Synthesize monotonicity with double-ended temporal expiration.
Return the level order traversal of a binary tree's nodes' values.
Use a FIFO Queue. Push the root, then loop while the queue isn't empty: for each node popped from the front, push its children to the back. This naturally processes nodes level by level.
Approach: Recognize that Breadth-First Search (BFS) on a tree maps perfectly to the FIFO structure of a queue.
Continue learning
Related: Stack fundamentals