Deque Array Implementation
What you'll learn: How to build a double-ended queue (deque) using a circular array that allows efficient insertions and deletions from both ends.
The Core Idea
A deque (pronounced "deck") lets you add or remove elements from both the front and back. To implement this with an array, we use a circular array approach with two pointers: front and rear. Unlike a regular queue where you only enqueue at the rear and dequeue from the front, a deque needs to support four primary operations: insert-front, insert-rear, delete-front, and delete-rear.
How It Works
Think of the array as a circular track. Both front and rear can move clockwise or counterclockwise around this track:
- Insert-front: Move
frontbackward (wrapping around if necessary), then place the element there - Insert-rear: Place the element at
rear, then moverearforward - Delete-front: Remove the element at
front, then movefrontforward - Delete-rear: Move
rearbackward, then remove the element there
The wraparound is handled with modulo arithmetic: (index + 1) % capacity for forward movement and (index - 1 + capacity) % capacity for backward movement.
Key Challenges
You must track whether the deque is empty or full. Common strategies include:
- Keeping a separate
sizevariable - Leaving one slot empty (full when
(rear + 1) % capacity == front) - Using a boolean flag
All four core operations run in O(1) time, making array-based deques very efficient for their intended use cases.
Key Takeaway: A deque array implementation uses a circular array with front and rear pointers that can move bidirectionally, enabling constant-time insertions and deletions at both ends.