Dynamic Stack Using Resizable Array in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the stack size.

DSA C

stack->capacity = [1];

Drag options to blanks, or click blank then click option'

A10

B0

C-1

D100

Attempts:

3 left

💡 Hint

Common Mistakes

Setting capacity to 0 or negative values causes no space allocation.

The initial capacity of the dynamic stack is usually set to a positive number like 10 to allocate space.

2fill in blank

medium

Complete the code to double the stack capacity when resizing.

DSA C

stack->capacity = stack->capacity [1] 2;

Drag options to blanks, or click blank then click option'

A/

B*

C-

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of multiplication for doubling.

Doubling capacity means multiplying the current capacity by 2.

3fill in blank

hard

Fix the error in the push function to check if resizing is needed.

DSA C

if (stack->top == stack->capacity [1]) {
    resize_stack(stack);
}

Drag options to blanks, or click blank then click option'

A>

B<

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than or less than instead of equality check.

When top equals capacity, the stack is full and needs resizing.

4fill in blank

hard

Fill both blanks to correctly pop an element from the stack.

DSA C

if (stack->top [1] 0) {
    return stack->array[[2]];
} else {
    return -1; // stack empty
}

Drag options to blanks, or click blank then click option'

A>

B>=

Cstack->top - 1

Dstack->top

Attempts:

3 left

💡 Hint

Common Mistakes

Checking top >= 0 allows empty stack access.

Using top index directly returns invalid element.

We check if top is greater than 0 to ensure stack is not empty, then return element at top-1 index.

5fill in blank

hard

Fill all three blanks to correctly resize the stack array.

DSA C

int *new_array = malloc(stack->capacity [1] sizeof(int));
for (int i = 0; i [2] stack->top; i++) {
    new_array[i] = stack->array[i];
}
free(stack->array);
stack->array = [3];

Drag options to blanks, or click blank then click option'

A*

B<

Cnew_array

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition instead of multiplication for malloc size.

Using i <= top causes out-of-bounds access.

Not assigning new_array back to stack->array.

We allocate new array with capacity * sizeof(int), copy elements while i < top, then assign new_array to stack->array.

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