Double-ended Queue (Deque)
Overview
A Double-ended Queue, or Deque, is an abstract data type (ADT) that allows insertion and removal of elements from both ends of the queue. It generalizes both stacks and queues into a single flexible structure.
What Is a Deque?
A deque:
- Supports operations at both front and rear
- Can act as a stack or a queue
- Does not allow random access
Core Deque Operations
| Operation | Description |
|---|---|
| InsertFront | Add element at the front |
| InsertRear | Add element at the rear |
| RemoveFront | Remove front element |
| RemoveRear | Remove rear element |
| Front | View front element |
| Rear | View rear element |
How It Works
Deques are commonly implemented using:
- Doubly linked lists
- Circular arrays
The ADT specifies allowed operations, not storage.
Example
Pseudocode
deque.insertRear(10)
deque.insertFront(5)
deque.removeRear() // 10
deque.removeFront() // 5
Real-world Analogy
A deque is like a hallway with doors at both ends. You can enter or exit from either side 🚪↔🚪.
Time Complexity
| Operation | Time |
|---|---|
| InsertFront | O(1) |
| InsertRear | O(1) |
| RemoveFront | O(1) |
| RemoveRear | O(1) |
Use Cases
- Sliding window algorithms
- Undo/redo systems
- Palindrome checking
- Task scheduling
Advantages
- Highly flexible
- Efficient operations
- Combines stack and queue behavior
Limitations
- More complex than simple queues
- Slightly higher memory overhead
Variants
- Input-restricted deque
- Output-restricted deque