Dynamic Stack Using Resizable Array in DSA C - Execution Trace

Concept Flow - Dynamic Stack Using Resizable Array

Start

↓

Push Operation

↓

Check if array is full?

No→Add element at top

Yes↓

Double array size

↓

Copy old elements to new array

↓

Add element at top

↓

Update top pointer

↓

Done

↓

Pop Operation

↓

Check if stack empty?

Yes→Error: Underflow

No↓

Remove element at top

↓

Update top pointer

↓

Check if array too empty?

Yes↓

Halve array size

↓

Copy elements to smaller array

↓

Done

This flow shows how the stack uses an array that grows or shrinks dynamically when pushing or popping elements.

Execution Sample

DSA C

push(10)
push(20)
push(30)
pop()
push(40)

This code pushes three elements, pops one, then pushes another, showing dynamic resizing.

Execution Table

Step	Operation	Array Size	Top Index	Pointer Changes	Visual State
1	push(10)	2	0	top=0	[10, _] (top at index 0)
2	push(20)	2	1	top=1	[10, 20] (top at index 1)
3	push(30) triggers resize	4	2	resize array to 4, top=2	[10, 20, 30, _] (top at index 2)
4	pop()	4	1	top=1	[10, 20, _, _] (top at index 1)
5	push(40)	4	2	top=2	[10, 20, 40, _] (top at index 2)

💡 Execution stops after the last push; array resized once when full.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5
array_size	2	2	2	4	4	4
top_index	-1	0	1	2	1	2
stack_elements	[]	[10]	[10,20]	[10,20,30]	[10,20]	[10,20,40]

Key Moments - 3 Insights

Why does the array size double when pushing the third element?

At step 3 in execution_table, the array is full (size 2, top at 1). To add a new element, the array doubles to size 4 to have space.

Why does the top index decrease after pop at step 4?

Pop removes the top element, so top index moves down from 2 to 1, reflecting the new top element at index 1.

Why is the array size not reduced after popping one element?

The array size shrinks only when the number of elements is much smaller than the array size to save space, which does not happen at step 4.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array size after step 3?

A 2

B 4

C 3

D 5

💡 Hint

Check the 'Array Size' column at step 3 in execution_table.

At which step does the top index move from 1 to 2?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at 'Top Index' changes in execution_table between steps 2 and 3.

If we pop twice after step 5, what will happen to the array size?

A It will stay the same

B It will double

C It will halve

D It will reset to zero

💡 Hint

Recall that array size halves when stack is much emptier, as explained in key_moments.

Concept Snapshot

Dynamic Stack Using Resizable Array:
- Uses array to store stack elements
- Push adds element; if full, array size doubles
- Pop removes element; if too empty, array size halves
- Top index tracks current top
- Efficient memory use by resizing dynamically

Full Transcript

This visualization shows how a dynamic stack works using a resizable array. When pushing elements, if the array is full, it doubles in size to fit more elements. When popping elements, if the stack becomes too empty, the array halves its size to save space. The top index points to the current top element. The execution table traces each push and pop, showing array size, top index, and the stack's visual state. Key moments clarify why resizing happens and how the top index changes. The quiz tests understanding of array size changes and top index movements.

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