Data Structures
Deque (Double-Ended Queue)
Add or remove from either end: O(1). With the right structure, both ends are equally fast, not just one.
The idea, in plain English
A deque (say 'deck') is like a line where you can join or leave from either end. Think of a deck of cards, where you can add or draw from the top or the bottom. It combines a stack and a queue into one flexible tool.
How it works
- 1addFront / addBack: put a new item at either end.
- 2removeFront / removeBack: take an item off either end.
- 3peekFront / peekBack: look at either end without removing anything.
When you'd use it
Use a deque for sliding-window problems, like tracking the biggest number in the last K items. Also use it for browser back and forward history, or a 'recently used' list where items get pulled from either end.
Common beginner mistakes
- Don't use a plain array with shift() and unshift() a lot in real production code. These are slow for big lists, because every other item has to shift over. A real deque avoids this problem.
- Don't mix up which end is 'front' and which is 'back' when reading someone else's deque code.
Try it — edit and run
Click the code to edit · press ⌘/Ctrl+↵ to run
Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.
All: 1 2 3
Front: 1
Back: 3
Remove front: 1
Remove back: 3
Left: 2Note: Python's collections.deque is a true double-ended queue. It's O(1) at both ends. The JS version here uses a plain array with shift() and unshift() for simplicity. That's O(n) at the front in real large-scale code.
See it in motion
Ready. Press play — a deque lets you add or remove at either end.
Not sure this is the right topic? See the learning paths → or where this leads →