Both ends are open
A deque, short for double ended queue, allows adding and removing at both ends. It generalizes the stack and the queue: use only one end and it acts like a stack, use opposite ends for adding and removing and it acts like a queue.
The four core operations are push front, push back, pop front, and pop back.
How it is built
A deque is commonly implemented two ways:
- A doubly linked list, where the previous and next pointers let either end be modified by rewiring a few links.
- A circular buffer with a head and a tail, where both indices can move inward or outward and wrap around the fixed array.
Either way, every operation touches only the structures at one end, so all four run cheaply regardless of how many elements are stored.
Where it shows up
Deques power sliding window algorithms, where you push new items at the back and discard stale ones from the front, and they serve as the backbone for work stealing schedulers that take tasks from one end and donate from the other.
Key idea
A deque supports cheap insertion and removal at both ends, generalizing stacks and queues, and is built from either a doubly linked list or a wrapping circular buffer.