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:
- Circular queue logic (with front and rear pointers wrapping around)
- 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.