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

Recall & Review

beginner

What is a dynamic stack using a resizable array?

A stack that can grow or shrink in size by resizing its underlying array when needed, allowing flexible storage without fixed limits.

beginner

Why do we resize the array in a dynamic stack?

To add more space when the stack is full or reduce space when many elements are removed, optimizing memory use.

intermediate

What happens during the push operation if the stack is full?

The array size is doubled, existing elements are copied to the new larger array, then the new element is added.

intermediate

How does the pop operation affect the array size in a dynamic stack?

If the number of elements becomes much smaller than the array size (usually less than a quarter), the array size is halved to save space.

intermediate

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

Amortized time complexity is O(1) for both push and pop, because resizing happens rarely and copying cost is spread out.

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

A When the stack has exactly one element

B When the stack is full or too empty

C Only when the stack is full

D Only when the stack is empty

The array resizes when full (to grow) or when too empty (to shrink).

What is the usual factor by which the array size is increased during resizing?

A Doubled

B Tripled

C Increased by one

D Halved

The array size is usually doubled to balance between resizing frequency and memory use.

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

A It is slower

B It uses less memory always

C It never needs resizing

D It can handle more elements without running out of space

Dynamic stacks can grow as needed, unlike fixed-size stacks with limited capacity.

What happens to elements during resizing of the stack's array?

A They are deleted

B They stay in the old array

C They are copied to the new array

D They are reversed

Elements are copied to the new larger or smaller array to preserve the stack content.

What is the amortized time complexity of push operation in a dynamic stack?

A O(1)

B O(n)

C O(log n)

D O(n^2)

Push is O(1) amortized because resizing happens rarely and cost is spread out.

Explain how a dynamic stack resizes its array during push and pop operations.

Think about when the stack grows and shrinks.

Describe the benefits of using a dynamic stack with a resizable array compared to a fixed-size stack.

Consider memory and capacity.