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

Dynamic Array-Based Queue

Implementing a queue with automatic resizing to handle arbitrary numbers of elements.

Dynamic Array-Based Queue

What you'll learn: How to build a queue that automatically grows and shrinks to handle any number of elements without running out of space.

The Problem with Fixed-Size Queues

In your previous circular queue implementation, you used a fixed-size array. This works great until you try to add more elements than the array can hold—then you're stuck. A dynamic array-based queue solves this by resizing itself automatically when needed.

How It Works

Think of it like a waiting room with movable walls. When the room gets full, you expand the walls to add more seats. When it's mostly empty, you can contract to save space.

The core idea combines two concepts you already know:

  1. Circular queue logic (with front and rear pointers wrapping around)
  2. Dynamic resizing (allocating a new, larger array when full)

The Resizing Process

When your queue fills up:

  • Allocate a new array (typically double the current size)
  • Copy all elements from the old array to the new one in proper order
  • Update your pointers to work with the new array
  • Deallocate the old array

The tricky part is copying elements correctly—you can't just copy the raw array because your data might wrap around. You need to copy starting from front, wrapping through to rear, so elements appear in logical order in the new array.

When to Resize

  • Grow when the array is full and you attempt an enqueue
  • Shrink (optional) when the queue becomes mostly empty (e.g., 25% full) to conserve memory

Key Takeaway: A dynamic array-based queue combines circular queue efficiency with automatic resizing, allowing it to handle arbitrary numbers of elements while maintaining O(1) amortized time for enqueue and dequeue operations.