Course contentsShow
← Computer Science
Lesson 397 of 2,8729. Stacks and QueuesFree lesson

Array-Based Deque Implementation

Implementing a deque using a circular array with efficient operations at both ends.

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:

  • front index: points to the first element
  • rear index: points just past the last element
  • size: 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.