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

Dynamic Stack Using Resizable Array

📖 Scenario: Imagine you are building a simple program to manage a stack of books. The stack can grow or shrink as books are added or removed. You will create a dynamic stack using a resizable array to handle this.

🎯 Goal: Build a dynamic stack class in C++ that uses a resizable array to store integers. You will implement push and pop operations that adjust the array size as needed.

📋 What You'll Learn

Create a class called DynamicStack with private members for the array pointer, current capacity, and current size.

Initialize the stack with a capacity of 2.

Implement a push(int value) method that adds an element and doubles the array size if full.

Implement a pop() method that removes the top element and halves the array size if the size is less than a quarter of capacity.

Implement a printStack() method to display the stack elements from bottom to top.

💡 Why This Matters

🌍 Real World

Dynamic stacks are used in many applications like undo features in text editors, expression evaluation, and backtracking algorithms where the number of elements changes over time.

💼 Career

Understanding dynamic data structures and memory management is essential for software developers working on performance-critical applications, embedded systems, and systems programming.

1

Create the DynamicStack class with initial setup

Create a class called DynamicStack with private members: an integer pointer arr, an integer capacity, and an integer size. Initialize capacity to 2, size to 0, and allocate arr with size 2 in the constructor.

DSA C++

class DynamicStack {
private:
    int* arr;
    int capacity;
    int size;
public:
    DynamicStack() {
        // Your code here
    }
};

Hint

Remember to allocate memory for arr using new int[capacity] inside the constructor.

2

Add the push method with resizing logic

Add a public method void push(int value) to DynamicStack. Inside it, check if size == capacity. If true, create a new array with double the capacity, copy old elements, delete the old array, update arr and capacity. Then add value to arr[size] and increment size.

DSA C++

class DynamicStack {
private:
    int* arr;
    int capacity;
    int size;
public:
    DynamicStack() {
        capacity = 2;
        size = 0;
        arr = new int[capacity];
    }

    void push(int value) {
        // Add push logic with resizing here
    }
};

Hint

Double the capacity when full, copy elements, delete old array, then add the new value.

3

Add the pop method with shrinking logic

Add a public method int pop() to DynamicStack. If size == 0, return -1. Otherwise, decrement size and store the popped value. If size is less than capacity / 4 and capacity is greater than 2, create a new array with half the capacity, copy elements, delete old array, update arr and capacity. Return the popped value.

DSA C++

class DynamicStack {
private:
    int* arr;
    int capacity;
    int size;
public:
    DynamicStack() {
        capacity = 2;
        size = 0;
        arr = new int[capacity];
    }

    void push(int value) {
        if (size == capacity) {
            int newCapacity = capacity * 2;
            int* newArr = new int[newCapacity];
            for (int i = 0; i < size; i++) {
                newArr[i] = arr[i];
            }
            delete[] arr;
            arr = newArr;
            capacity = newCapacity;
        }
        arr[size] = value;
        size++;
    }

    int pop() {
        // Add pop logic with shrinking here
    }
};

Hint

Return -1 if empty. After popping, shrink array if size is less than a quarter of capacity and capacity is more than 2.

4

Add printStack method and test the stack

Add a public method void printStack() to DynamicStack that prints the stack elements from bottom to top separated by spaces. Then, in main(), create a DynamicStack object, push 10, 20, 30, 40, pop one element, push 50, and call printStack().

DSA C++

class DynamicStack {
private:
    int* arr;
    int capacity;
    int size;
public:
    DynamicStack() {
        capacity = 2;
        size = 0;
        arr = new int[capacity];
    }

    void push(int value) {
        if (size == capacity) {
            int newCapacity = capacity * 2;
            int* newArr = new int[newCapacity];
            for (int i = 0; i  2) {
            int newCapacity = capacity / 2;
            int* newArr = new int[newCapacity];
            for (int i = 0; i < size; i++) {
                newArr[i] = arr[i];
            }
            delete[] arr;
            arr = newArr;
            capacity = newCapacity;
        }
        return poppedValue;
    }

    void printStack() {
        // Print stack elements from bottom to top
    }
};

int main() {
    DynamicStack stack;
    // Push 10, 20, 30, 40
    // Pop one element
    // Push 50
    // Print stack
    return 0;
}

Hint

Print elements from index 0 to size-1 separated by spaces. In main(), follow the exact push and pop sequence before printing.

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 can grow or shrink automatically as elements are pushed or popped.

B. It uses less memory than a linked list stack.

C. It always has a fixed maximum size.

D. It does not require resizing when full.

Solution

1. Step 1: Understand fixed vs dynamic size

   A fixed-size array stack has a set capacity and cannot grow beyond it, causing overflow if exceeded.

2. Step 2: Explain dynamic resizing

   A dynamic stack using a resizable array automatically increases or decreases its size when needed, avoiding overflow and wasted space.

3. Final Answer:

   It can grow or shrink automatically as elements are pushed or popped. -> Option A

4. Quick Check:

   Dynamic resizing = automatic growth/shrink [OK]

Hint: Dynamic arrays resize automatically to fit elements [OK]

Common Mistakes:

• Thinking dynamic stack has fixed size
• Confusing memory use with linked list
• Assuming no resizing needed

2. Which of the following is the correct syntax to double the size of the array when the stack is full in C++?

easy

A. arr = new int[size * 2];

B. arr.resize(size * 2);

C. arr = (int*) realloc(arr, size * 2 * sizeof(int));

D. arr = arr * 2;

Solution

1. Step 1: Identify array resizing in C++

   For raw arrays, realloc is used to resize memory blocks dynamically.

2. Step 2: Check each option

   arr = new int[size * 2]; creates a new array but loses old data. arr.resize(size * 2); is for std::vector, not raw arrays. arr = (int*) realloc(arr, size * 2 * sizeof(int)); correctly uses realloc to resize preserving data. arr = arr * 2; is invalid syntax.

3. Final Answer:

   arr = (int*) realloc(arr, size * 2 * sizeof(int)); -> Option C

4. Quick Check:

   Raw array resize = realloc [OK]

Hint: Use realloc for raw array resizing in C++ [OK]

Common Mistakes:

• Using vector methods on raw arrays
• Creating new array without copying data
• Invalid pointer arithmetic

3. Consider the following C++ code snippet for a dynamic stack push operation:

void push(int x) {
  if (top == capacity) {
    capacity *= 2;
    arr = (int*) realloc(arr, capacity * sizeof(int));
  }
  arr[top++] = x;
}

// Initial capacity = 2, top = 0
push(10);
push(20);
push(30);

What is the value of capacity and the stack elements after these pushes?

medium

A. capacity = 2, stack = [10, 20, 30]

B. capacity = 4, stack = [10, 20, 30]

C. capacity = 3, stack = [10, 20, 30]

D. capacity = 4, stack = [10, 20]

Solution

1. Step 1: Trace push calls and capacity changes

   Initial capacity is 2. After pushing 10 and 20, top reaches 2 (full). On pushing 30, capacity doubles to 4, and 30 is added.

2. Step 2: Confirm final stack and capacity

   Stack elements are [10, 20, 30], capacity is 4 after resizing.

3. Final Answer:

   capacity = 4, stack = [10, 20, 30] -> Option B

4. Quick Check:

   Capacity doubles when full, stack holds all pushed elements [OK]

Hint: Capacity doubles only when full before push [OK]

Common Mistakes:

• Not doubling capacity before adding new element
• Assuming capacity equals number of elements
• Ignoring realloc effect

4. The following code snippet for pop operation in a dynamic stack has a bug:

int pop() {
  if (top == 0) {
    throw "Stack Underflow";
  }
  int val = arr[--top];
  if (top < capacity / 4) {
    capacity /= 2;
    arr = (int*) realloc(arr, capacity * sizeof(int));
  }
  return val;
}

What is the bug and how to fix it?

medium

A. Bug: throw uses string literal; Fix: use std::exception instead.

B. Bug: pop does not decrease top; Fix: decrement top before accessing.

C. Bug: capacity can become zero; Fix: ensure capacity never goes below 1.

D. Bug: realloc is called without checking NULL; Fix: check realloc return.

Solution

1. Step 1: Analyze realloc usage

   realloc can fail to allocate memory and return NULL, but the code does not check the return value before using arr, which can lead to crashes.

2. Step 2: Fix by checking realloc return

   Store the result in a temporary pointer and check if it is NULL before assigning to arr. Handle the error case appropriately.

3. Final Answer:

   Bug: realloc is called without checking NULL; Fix: check realloc return. -> Option D

4. Quick Check:

   Always check realloc != NULL [OK]

Hint: Always check realloc return for NULL [OK]

Common Mistakes:

• Ignoring minimum capacity limit
• Not decrementing top before access
• Not checking realloc NULL

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 an initial capacity of 4. Which of the following code snippets correctly implements the pop operation with this behavior?

int pop() {
  if (top == 0) throw "Underflow";
  int val = arr[--top];
  if (top < capacity / 4 && capacity > 4) {
    capacity /= 2;
    arr = (int*) realloc(arr, capacity * sizeof(int));
  }
  return val;
}

What is the key reason for checking capacity > 4 before resizing?

hard

A. To prevent the capacity from shrinking below the initial minimum size, avoiding invalid memory access.

B. To ensure the stack always has space for at least four elements, improving performance.

C. To avoid calling realloc too frequently, which slows down the program.

D. To keep the capacity as a power of two for easier indexing.

Solution

1. Step 1: Understand capacity shrinking condition

   The stack shrinks when elements are less than one-fourth capacity, but must not shrink below initial capacity 4.

2. Step 2: Explain importance of capacity > 4 check

   This check prevents capacity from becoming less than 4, which avoids invalid memory allocation and potential errors.

3. Final Answer:

   To prevent the capacity from shrinking below the initial minimum size, avoiding invalid memory access. -> Option A

4. Quick Check:

   Minimum capacity check prevents invalid resize [OK]

Hint: Check minimum capacity before shrinking array [OK]

Common Mistakes:

• Shrinking capacity below initial size
• Ignoring memory safety on realloc
• Assuming performance reason only