Dynamic Stack Using Resizable Array in DSA C

Mental Model

A dynamic stack grows its storage automatically when full by creating a bigger array and copying items over.

Analogy: Imagine a stack of plates on a small tray. When the tray is full, you get a bigger tray and move all plates there so you can keep stacking more.

Stack array: [1, 2, 3, _, _]
Top index: ↑3 (points to next free slot)
Capacity: 5

Dry Run Walkthrough

Input: Push values 1, 2, 3, 4, 5, 6 onto an initially empty stack with capacity 4

Goal: Show how the stack resizes when pushing the 5th element and continues pushing

Step 1: Push 1 onto stack

Stack array: [1, _, _, _]
Top index: ↑1
Capacity: 4

Why: Add first element at index 0, top moves to 1

Step 2: Push 2 onto stack

Stack array: [1, 2, _, _]
Top index: ↑2
Capacity: 4

Why: Add second element at index 1, top moves to 2

Step 3: Push 3 onto stack

Stack array: [1, 2, 3, _]
Top index: ↑3
Capacity: 4

Why: Add third element at index 2, top moves to 3

Step 4: Push 4 onto stack

Stack array: [1, 2, 3, 4]
Top index: ↑4
Capacity: 4

Why: Add fourth element at index 3, top moves to 4 (stack full)

Step 5: Push 5 triggers resize: create new array double size (8), copy old elements

Stack array: [1, 2, 3, 4, _, _, _, _]
Top index: ↑4
Capacity: 8

Why: Old array full, resize to hold more elements

Step 6: Add 5 at index 4 after resize

Stack array: [1, 2, 3, 4, 5, _, _, _]
Top index: ↑5
Capacity: 8

Why: Push continues after resizing

Step 7: Push 6 onto stack

Stack array: [1, 2, 3, 4, 5, 6, _, _]
Top index: ↑6
Capacity: 8

Why: Add sixth element at index 5, top moves to 6

Result:

Stack array: [1, 2, 3, 4, 5, 6, _, _]
Top index: 6
Capacity: 8
Stack content (bottom to top): 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *array;
    int top;
    int capacity;
} DynamicStack;

DynamicStack *createStack(int capacity) {
    DynamicStack *stack = malloc(sizeof(DynamicStack));
    stack->capacity = capacity;
    stack->top = 0;
    stack->array = malloc(sizeof(int) * capacity);
    return stack;
}

void resizeStack(DynamicStack *stack) {
    int newCapacity = stack->capacity * 2;
    int *newArray = malloc(sizeof(int) * newCapacity);
    for (int i = 0; i < stack->top; i++) {
        newArray[i] = stack->array[i]; // copy old elements
    }
    free(stack->array);
    stack->array = newArray;
    stack->capacity = newCapacity;
}

void push(DynamicStack *stack, int value) {
    if (stack->top == stack->capacity) {
        resizeStack(stack); // resize when full
    }
    stack->array[stack->top] = value;
    stack->top++;
}

int pop(DynamicStack *stack) {
    if (stack->top == 0) {
        printf("Stack is empty\n");
        return -1; // error value
    }
    stack->top--;
    return stack->array[stack->top];
}

void printStack(DynamicStack *stack) {
    for (int i = 0; i < stack->top; i++) {
        printf("%d", stack->array[i]);
        if (i < stack->top - 1) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    DynamicStack *stack = createStack(4);
    push(stack, 1);
    push(stack, 2);
    push(stack, 3);
    push(stack, 4);
    push(stack, 5); // triggers resize
    push(stack, 6);
    printStack(stack);
    free(stack->array);
    free(stack);
    return 0;
}

if (stack->top == stack->capacity) { resizeStack(stack); }

resize stack array when full to double capacity

stack->array[stack->top] = value; stack->top++;

add new element at top index and increment top

for (int i = 0; i < stack->top; i++) { newArray[i] = stack->array[i]; }

copy old elements to new larger array

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Complexity Analysis

Time: O(n) for resizing steps because copying all elements; O(1) amortized for push otherwise

Space: O(n) for the array storing n elements

vs Alternative: Compared to fixed size stack, dynamic stack avoids overflow by resizing but uses extra time during resize

Edge Cases

Push on empty stack

Stack adds element at index 0 without resizing

DSA C

if (stack->top == stack->capacity) { resizeStack(stack); }

Push exactly at capacity triggers resize

Stack doubles capacity and copies elements before adding new one

DSA C

if (stack->top == stack->capacity) { resizeStack(stack); }

Pop from empty stack

Prints 'Stack is empty' and returns -1

DSA C

if (stack->top == 0) { printf("Stack is empty\n"); return -1; }

When to Use This Pattern

When you need a stack that can grow beyond a fixed size without errors, use a dynamic stack with resizing to handle unknown or large input sizes.

Common Mistakes

Mistake: Not resizing the array when full causes overflow or memory errors
Fix: Check if top equals capacity before push and resize array by copying elements to a bigger array

Summary

It implements a stack that grows automatically by resizing its array when full.

Use it when you want a stack but don't know the maximum number of elements in advance.

The key insight is to double the array size and copy elements to avoid overflow while keeping push efficient on average.

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