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.

Practice

1. What is the main advantage of using a dynamic stack implemented with a resizable array compared to a fixed-size array stack?

easy

A. It uses less memory than a linked list stack.

B. It always has a fixed maximum size.

C. It can grow or shrink in size as needed during runtime.

D. It does not require any resizing operations.

Solution

1. Step 1: Understand fixed vs dynamic size

   A fixed-size array stack has a set capacity that cannot change during runtime.

2. Step 2: Identify dynamic array behavior

   A dynamic stack with a resizable array can increase or decrease its size as elements are pushed or popped.

3. Final Answer:

   It can grow or shrink in size as needed during runtime. -> Option C

4. Quick Check:

   Dynamic resizing means flexible size [OK]

Hint: Dynamic arrays resize to fit data, unlike fixed arrays [OK]

Common Mistakes:

• Thinking dynamic stack has fixed size
• Confusing memory usage with resizing
• Assuming no resizing is needed

2. Which of the following is the correct syntax to double the size of a dynamic stack's array in C when it is full?

easy

A. stack->array = realloc(stack->array, stack->capacity * 2 * sizeof(int));

B. stack->array = malloc(stack->capacity * sizeof(int));

C. stack->array = realloc(stack->array, stack->capacity / 2 * sizeof(int));

D. stack->array = realloc(stack->array, sizeof(int));

Solution

1. Step 1: Identify correct use of realloc

   realloc is used to resize the memory block; new size should be double current capacity times element size.

2. Step 2: Check each option

   stack->array = realloc(stack->array, stack->capacity * 2 * sizeof(int)); correctly doubles capacity and multiplies by sizeof(int). Others either allocate wrong size or use malloc instead of realloc.

3. Final Answer:

   stack->array = realloc(stack->array, stack->capacity * 2 * sizeof(int)); -> Option A

4. Quick Check:

   Double capacity with realloc [OK]

Hint: Use realloc with doubled capacity times element size [OK]

Common Mistakes:

• Using malloc instead of realloc for resizing
• Dividing capacity instead of doubling
• Not multiplying by sizeof element

3. Consider the following C code snippet for a dynamic stack push operation:

void push(Stack *stack, int value) {
  if (stack->top == stack->capacity - 1) {
    stack->capacity *= 2;
    stack->array = realloc(stack->array, stack->capacity * sizeof(int));
  }
  stack->array[++stack->top] = value;
}

Stack stack = {malloc(2 * sizeof(int)), 2, -1};
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);

What is the value of stack.capacity after these operations?

medium

A. 4

B. 3

C. 2

D. 6

Solution

1. Step 1: Initial capacity and pushes

   Initial capacity is 2. After pushing 2 elements, stack is full (top = 1).

2. Step 2: Push triggers resize

   On pushing third element, capacity doubles from 2 to 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Capacity doubles when full [OK]

Hint: Capacity doubles only when full before push [OK]

Common Mistakes:

• Assuming capacity increases by 1
• Forgetting to double capacity
• Confusing top index with capacity

4. The following code snippet for popping from a dynamic stack sometimes causes a segmentation fault. What is the likely cause?

int pop(Stack *stack) {
  if (stack->top == -1) {
    printf("Stack Underflow\n");
    return -1;
  }
  int value = stack->array[stack->top--];
  if (stack->top < stack->capacity / 4) {
    stack->capacity /= 2;
    stack->array = realloc(stack->array, stack->capacity * sizeof(int));
  }
  return value;
}

medium

A. Not freeing memory after pop.

B. Not checking for stack overflow before pop.

C. Using stack->top-- instead of --stack->top.

D. Reducing capacity below 1 causes invalid realloc size.

Solution

1. Step 1: Analyze capacity reduction condition

   Capacity halves when top is less than one-fourth capacity.

2. Step 2: Identify edge case

   If capacity becomes 0 or less, realloc with zero size causes segmentation fault.

3. Final Answer:

   Reducing capacity below 1 causes invalid realloc size. -> Option D

4. Quick Check:

   Capacity must not shrink below 1 [OK]

Hint: Never resize array to zero or negative size [OK]

Common Mistakes:

• Ignoring minimum capacity limit
• Confusing overflow with underflow
• Misusing post-decrement operator

5. You want to implement a dynamic stack using a resizable array that shrinks its capacity when the number of elements falls below one-fourth of the capacity, but never shrinks below 2. Which modification to the pop function below ensures this behavior?

int pop(Stack *stack) {
  if (stack->top == -1) {
    printf("Stack Underflow\n");
    return -1;
  }
  int value = stack->array[stack->top--];
  if (stack->top < stack->capacity / 4) {
    stack->capacity /= 2;
    stack->array = realloc(stack->array, stack->capacity * sizeof(int));
  }
  return value;
}

hard

A. Remove the resizing code entirely.

B. Add a check: if (stack->capacity > 2) before halving capacity.

C. Change condition to if (stack->top < stack->capacity / 2).

D. Set capacity to 1 after halving.

Solution

1. Step 1: Understand shrinking condition

   Stack shrinks when elements < 1/4 capacity but must not go below 2 capacity.

2. Step 2: Add capacity lower bound check

   Before halving capacity, check if capacity is greater than 2 to avoid shrinking below 2.

3. Final Answer:

   Add a check: if (stack->capacity > 2) before halving capacity. -> Option B

4. Quick Check:

   Prevent capacity below 2 by conditional check [OK]

Hint: Check capacity > 2 before shrinking to avoid too small array [OK]

Common Mistakes:

• Shrinking capacity below minimum allowed
• Changing condition incorrectly
• Removing resizing causes memory waste