Deque is a queue-like Abstract Data Type that allows insertion and removal at both ends.
The name deque means double-ended queue.
Supported operations usually include:
- Push front
- Push back
- Pop front
- Pop back
- Peek front
- Peek back
A deque can be used as:
- A queue, by adding at one end and removing at the other
- A stack, by adding and removing at the same end
Deques are useful for sliding window algorithms, scheduling, undo buffers, and breadth-first search variants.
flowchart LR Left["front"] <--> A["A"] A <--> B["B"] B <--> Right["back"]
Anki
id: deque-definition deck: Computer Science::Data Structures tags: data-structures deque queue
Q: What can you do with a deque that you cannot do with a normal queue? A: Add or remove items from both the front and the back.
id: deque-vs-queue deck: Computer Science::Data Structures tags: data-structures deque queue
Q: Why might a sliding window algorithm use a deque? A: It often needs to discard old items from the front while adding new items at the back.