A queue open at both ends
A deque, short for double ended queue, generalizes both the stack and the queue. It permits insertion and removal at both the front and the back. The four core operations are push front, push back, pop front, and pop back, each running in constant time.
Why one structure serves many roles
Because it is open at both ends, a deque can imitate other structures.
- Use only the back and you have a stack.
- Use the back to add and the front to remove and you have a queue.
- Use both ends and you handle problems neither alone can.
A classic example is the sliding window maximum, where a deque keeps candidate indices ordered so the largest value in the current window sits at the front and stale values are dropped from the back.
How it is implemented
A doubly linked list supports both ends naturally with head and tail pointers. For better cache behavior, libraries often use a circular dynamic array or a list of fixed size blocks, allowing constant time growth at either end while still giving fast indexed access.
Key idea
A deque allows constant time insertion and removal at both ends, generalizing the stack and the queue, and it powers sliding window problems where candidates enter and leave from either side.