Dynamic Stack Using Resizable Array in DSA C++

Mental Model

A stack is like a pile where you add or remove items only from the top. When the pile gets full, we make it bigger automatically to hold more items.

Analogy: Imagine a stack of plates. You can only add or take the top plate. If the stack is too tall for your shelf, you get a bigger shelf and move all plates there.

Stack array: [ 1, 2, 3, null, null ]
Top index: ↑ 2 (points to 3)
null means empty space ready for new items

Dry Run Walkthrough

Input: Start with stack holding [1, 2, 3] with capacity 5, push 4, push 5, then push 6 (trigger resize)

Goal: Show how the stack grows when full and how items are added on top

Step 1: push 4 onto stack

[1, 2, 3, 4, null]
Top index: ↑ 3

Why: Add 4 at next free spot on top

Step 2: push 5 onto stack

[1, 2, 3, 4, 5]
Top index: ↑ 4

Why: Add 5 at next free spot; stack is now full

Step 3: push 6 triggers resize: create new array double size (10), copy old items

[1, 2, 3, 4, 5, 6, null, null, null, null]
Top index: ↑ 5

Why: Stack full, so double capacity and add 6 on top

Result:

[1, 2, 3, 4, 5, 6, null, null, null, null]
Top index: 5
Stack content top to bottom: 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

Annotated Code

DSA C++

#include <iostream>
#include <vector>

class DynamicStack {
private:
    int* arr;
    int capacity;
    int top;

    void resize() {
        int newCapacity = capacity * 2;
        int* newArr = new int[newCapacity];
        for (int i = 0; i <= top; i++) {
            newArr[i] = arr[i]; // copy old items
        }
        delete[] arr;
        arr = newArr;
        capacity = newCapacity;
    }

public:
    DynamicStack(int size = 5) {
        capacity = size;
        arr = new int[capacity];
        top = -1; // empty stack
    }

    ~DynamicStack() {
        delete[] arr;
    }

    void push(int val) {
        if (top == capacity - 1) {
            resize(); // double size when full
        }
        top++;
        arr[top] = val; // add new item on top
    }

    int pop() {
        if (top == -1) {
            std::cerr << "Stack is empty\n";
            return -1; // error value
        }
        int val = arr[top];
        top--;
        return val; // remove top item
    }

    void print() {
        for (int i = top; i >= 0; i--) {
            std::cout << arr[i] << " -> ";
        }
        std::cout << "null\n";
    }
};

int main() {
    DynamicStack stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);
    stack.push(6); // triggers resize
    stack.print();
    return 0;
}

if (top == capacity - 1) { resize(); }

check if stack is full and resize array to double capacity

top++; arr[top] = val;

increment top index and add new value on top

for (int i = 0; i <= top; i++) { newArr[i] = arr[i]; }

copy all existing items to new larger array

for (int i = top; i >= 0; i--) { std::cout << arr[i] << " -> "; }

print stack from top to bottom

Output

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

Complexity Analysis

Time: O(n) for push when resizing because all elements are copied; O(1) average for push without resize

Space: O(n) for the array storing stack elements, grows as needed

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

Edge Cases

pushing onto empty stack

stack accepts first element and top moves from -1 to 0

DSA C++

top == -1 means empty stack handled by top++ in push

popping from empty stack

prints error message and returns -1

DSA C++

if (top == -1) { std::cerr << "Stack is empty\n"; return -1; }

pushing elements to trigger multiple resizes

stack doubles capacity each time full, copying all elements

DSA C++

if (top == capacity - 1) { resize(); }

When to Use This Pattern

When you need a stack that can grow beyond a fixed size without errors, use a dynamic stack with resizable array to handle unknown input sizes smoothly.

Common Mistakes

Mistake: Not resizing array when full causes stack overflow error
Fix: Add a resize method that doubles array size and copy elements before pushing new item

Mistake: Forgetting to update top index after push or pop
Fix: Always increment top after push and decrement top after pop

Summary

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

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

The key is to double the array size and copy items when the stack is full to keep push operations working.

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