Stack & Queue • Architecture

Dynamic Queues

A standard array-based queue has a fixed capacity. A Dynamic Queue can automatically grow its internal storage when it gets full, similar to std::vector or ArrayList.

The Growth Strategy

When the `rear` pointer attempts to exceed the current capacity (and the queue is genuinely full), the queue allocates a new array, usually double the size of the current one.

The Migration Process

During resizing, all existing elements must be copied from the old array to the new, larger array. If it's a circular queue, elements must be "unwrapped" and aligned sequentially starting from index 0 in the new array.

Amortized O(1) Time

The enqueue operation that triggers the resize takes O(N) time because of the copy. However, because resizing happens rarely (exponentially less often), the average (amortized) time per enqueue remains O(1).

Loading Lab...

Stack & Queue • Architecture

Dynamic Queues

A standard array-based queue has a fixed capacity. A Dynamic Queue can automatically grow its internal storage when it gets full, similar to std::vector or ArrayList.

The Growth Strategy

When the `rear` pointer attempts to exceed the current capacity (and the queue is genuinely full), the queue allocates a new array, usually double the size of the current one.