Dynamic Stack Using Resizable Array in DSA C - Build from Scratch

Dynamic Stack Using Resizable Array

📖 Scenario: You are building a stack data structure that can grow dynamically as more items are added. This is like a stack of plates that can get taller when you add more plates, and shrink when you remove plates.

🎯 Goal: Create a dynamic stack using a resizable array in C. You will initialize the stack, set its initial capacity, implement push and pop operations that resize the array when needed, and finally print the stack contents.

📋 What You'll Learn

Create a struct called Stack with an integer pointer items, integer capacity, and integer top.

Initialize the stack with a capacity of 2 and top as -1.

Write a function resize to double the capacity of the stack's array.

Write a function push that adds an element to the stack and resizes if full.

Write a function pop that removes the top element and returns it.

Print the stack contents from bottom to top.

💡 Why This Matters

🌍 Real World

Dynamic stacks are used in programming language interpreters, undo features in applications, and expression evaluation where the number of elements is not fixed.

💼 Career

Understanding dynamic data structures like resizable stacks is important for software developers working on performance-critical applications and memory management.

1

Create the Stack struct and initialize it

Create a struct called Stack with an integer pointer items, integer capacity, and integer top. Then create a function initStack that initializes a Stack with capacity 2, top -1, and allocates memory for items accordingly.

DSA C

# Define the Stack struct and initStack function
// Your code here

Hint

Use typedef struct to define Stack. Initialize capacity to 2 and top to -1. Allocate memory for items using malloc.

2

Add a resize function to double the stack capacity

Write a function resize that takes a pointer to Stack and doubles its capacity. It should allocate a new array with double size, copy existing items, free the old array, and update the stack's items pointer and capacity.

DSA C

# Write the resize function to double the capacity
// Your code here

Hint

Allocate a new array with double capacity, copy old items with a loop, free old memory, then update items and capacity.

3

Implement push and pop functions with dynamic resizing

Write a function push that adds an integer to the stack. If the stack is full (top == capacity - 1), call resize before adding. Also write a function pop that removes and returns the top element. If the stack is empty (top == -1), return -1.

DSA C

# Implement push and pop functions
// Your code here

Hint

Check if stack is full before pushing and call resize. For pop, check if empty and return -1 if so, else return top item and decrease top.

4

Push values, pop one, and print the stack contents

In main, create a Stack variable called stack and initialize it with initStack. Push the values 10, 20, 30, and 40 onto the stack. Then pop one value and store it in popped. Finally, print the stack contents from bottom to top separated by spaces.

DSA C

# Print stack contents from bottom to top separated by spaces
// Your code here

Hint

Use a for loop from 0 to stack.top to print each item separated by spaces.

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