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

Deque Array Implementation

Implementing deques using circular arrays with front and rear operations.

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 front backward (wrapping around if necessary), then place the element there
  • Insert-rear: Place the element at rear, then move rear forward
  • Delete-front: Remove the element at front, then move front forward
  • Delete-rear: Move rear backward, 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 size variable
  • 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.