Dynamic Stack Using Resizable Array in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this dynamic stack push sequence?

Consider a dynamic stack implemented using a resizable array starting with capacity 2. After pushing elements 10, 20, 30, and 40 in order, what is the content of the stack from top to bottom?

DSA C

DynamicStack stack;
initStack(&stack);
push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);
printStack(&stack);

A 10 -> 20 -> 30 -> 40 -> null

B 30 -> 40 -> 20 -> 10 -> null

C 40 -> 20 -> 30 -> 10 -> null

D 40 -> 30 -> 20 -> 10 -> null

💡 Hint

Remember that stack is Last In First Out (LIFO). The last pushed element is on top.

The stack pushes elements in order: 10, 20, 30, 40. The top is the last pushed element, 40. So the stack from top to bottom is 40, 30, 20, 10.

❓ Predict Output

intermediate

What is the stack size after these operations?

Given a dynamic stack with initial capacity 2, perform these operations: push 5, push 15, push 25, pop, push 35. What is the size of the stack after these operations?

DSA C

DynamicStack stack;
initStack(&stack);
push(&stack, 5);
push(&stack, 15);
push(&stack, 25);
pop(&stack);
push(&stack, 35);
int size = stackSize(&stack);
printf("%d", size);

A 4

B 3

C 2

D 1

💡 Hint

Count pushes and pops carefully.

Push 5, 15, 25 → size 3. Pop removes top (25) → size 2. Push 35 → size 3.

🔧 Debug

advanced

Identify the error in this dynamic stack pop function

What error will occur when running this pop function on a dynamic stack implemented with a resizable array?

DSA C

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

A Possible memory leak or invalid memory access due to realloc without checking NULL

B Stack overflow error

C No error, works correctly

D Division by zero error

💡 Hint

Check how realloc is used and what happens if it fails.

If realloc fails, it returns NULL but the original memory is not freed. Assigning directly to stack->array without checking causes memory leak or invalid access.

🧠 Conceptual

advanced

Why does the dynamic stack double its capacity when full?

In a dynamic stack implemented with a resizable array, why is the capacity doubled when the stack is full instead of increasing by a fixed amount?

A Doubling capacity prevents stack underflow

B Doubling capacity wastes less memory than fixed increments

C Doubling capacity reduces the number of resizes, improving amortized time complexity

D Doubling capacity is easier to implement than fixed increments

💡 Hint

Think about how often resizing happens and the cost of copying elements.

Doubling capacity reduces the frequency of resizing, so push operations have amortized O(1) time. Fixed increments cause frequent resizing and higher total cost.

🚀 Application

expert

What is the output after this sequence of push and pop operations?

Given a dynamic stack with initial capacity 2, perform these operations in order: push 1, push 2, push 3, pop, pop, push 4, push 5, pop. What is the content of the stack from top to bottom?

DSA C

DynamicStack stack;
initStack(&stack);
push(&stack, 1);
push(&stack, 2);
push(&stack, 3);
pop(&stack);
pop(&stack);
push(&stack, 4);
push(&stack, 5);
pop(&stack);
printStack(&stack);

A 4 -> 1 -> null

B 5 -> 4 -> 1 -> null

C 2 -> 1 -> null

D 1 -> 4 -> null

💡 Hint

Track each push and pop carefully, remembering LIFO order.

Push 1,2,3 → stack top:3,2,1. Pop removes 3, then pop removes 2 → stack top:1. Push 4,5 → stack top:5,4,1. Pop removes 5 → stack top:4,1.

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