Dynamic Stack Using Resizable Array in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a dynamic stack using a resizable array?

A dynamic stack using a resizable array is a stack data structure that grows or shrinks its underlying array automatically when elements are pushed or popped, so it can handle any number of elements without fixed size limits.

beginner

Why do we resize the array in a dynamic stack?

We resize the array to save memory and allow the stack to grow beyond its initial capacity. When the array is full, we create a bigger array and copy elements. When the stack is mostly empty, we shrink the array to avoid wasting space.

intermediate

What happens when you push an element and the array is full?

When pushing and the array is full, the stack doubles the size of the array, copies all elements to the new array, then adds the new element. This ensures there is always space for new elements.

intermediate

How does popping elements affect the size of the array?

When popping elements, if the number of elements becomes less than a quarter of the array size, the stack shrinks the array to half its current size to save memory.

intermediate

What is the time complexity of push and pop operations in a dynamic stack using a resizable array?

Push and pop operations are usually O(1) (constant time). Occasionally, resizing takes O(n) time, but amortized over many operations, the average time remains O(1).

What triggers the resizing of the array in a dynamic stack?

A Only when the array is full

B When the array is full or less than a quarter full

C Only when the array is empty

D When the array is half full

The array resizes by growing when full and shrinking when less than a quarter full.

What is the initial size of the array in a dynamic stack?

A It can be any fixed size, often small like 1 or 2

B Always 100

C Always 0

D It must be very large to avoid resizing

The initial size is usually small and grows dynamically as needed.

What is the main advantage of using a dynamic stack over a fixed-size stack?

A It is faster for all operations

B It uses less memory always

C It can handle any number of elements without overflow

D It never needs resizing

Dynamic stacks grow as needed, so they avoid overflow errors.

Which operation might take longer than O(1) time in a dynamic stack?

A Resizing the array during push or pop

B Simple push without resizing

C Simple pop without resizing

D Checking if the stack is empty

Resizing requires copying elements, which takes O(n) time.

What happens if you pop from an empty dynamic stack?

A It returns a default value

B The stack resizes automatically

C Nothing happens

D An error or exception occurs

Popping from an empty stack is invalid and usually causes an error.

Explain how a dynamic stack using a resizable array manages memory when pushing and popping elements.

Think about when and why the array size changes.

Describe the time complexity of push and pop operations in a dynamic stack and why resizing does not make them slow on average.

Consider how often resizing occurs compared to normal operations.