Array-Based Deque Implementation
What you'll learn: How to build a deque (double-ended queue) using a circular array so you can add and remove elements efficiently from both ends.
The Core Idea
A deque lets you insert and delete from both the front and back. While you've already seen array-based queue implementations with a circular buffer, a deque needs to handle movement in both directions. You'll use a circular array and two index pointers (front and rear) that can both move forward and backward with wrap-around logic.
How It Works
Think of your array as a circular track. You maintain:
frontindex: points to the first elementrearindex: points just past the last elementsize: tracks how many elements are present
Key Operations
Insert at front: Move front backward (with wrap-around), then place the element.
Insert at rear: Place the element at rear, then move rear forward.
Delete from front: Remove the element at front, then move front forward.
Delete from rear: Move rear backward (with wrap-around), then remove that element.
The wrap-around formula for moving backward is: (index - 1 + capacity) % capacity
For moving forward: (index + 1) % capacity
Handling Full Capacity
When the array fills up (size == capacity), you need to resize: allocate a larger array and copy elements in order, then reset front to 0 and rear to size.
Efficiency
All four operations (insert/delete from front/rear) run in O(1) time, except when resizing triggers (amortized O(1)).
Key Takeaway: A circular array-based deque uses bidirectional index movement with modular arithmetic to efficiently support insertion and deletion at both ends in constant time.