Dynamic Stack Using Resizable Array in DSA C#

Mental Model

A stack is a collection where you add and remove items from the top only. When the stack gets full, we make the storage bigger automatically to hold more items.

Analogy: Imagine a stack of plates. You can only add or remove the top plate. If the stack gets too tall for the shelf, you get a bigger shelf to hold more plates.

Stack array: [ 1, 2, 3, null, null ]
Top index: ↑ 2 (points to 3)
Capacity: 5

null means empty space ready to hold new items.

Dry Run Walkthrough

Input: Push 1, Push 2, Push 3, Push 4, Push 5, Push 6 on stack with initial capacity 5

Goal: Show how the stack grows automatically when pushing beyond capacity

Step 1: Push 1 onto stack

[1, null, null, null, null]
Top index: ↑ 0

Why: Add first item at position 0, top moves to 0

Step 2: Push 2 onto stack

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

Why: Add second item at position 1, top moves up

Step 3: Push 3 onto stack

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

Why: Add third item at position 2

Step 4: Push 4 onto stack

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

Why: Add fourth item at position 3

Step 5: Push 5 onto stack

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

Why: Add fifth item at position 4, stack is now full

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

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

Why: Stack full, so double capacity to hold more items

Result:

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

Annotated Code

DSA C#

using System;

public class DynamicStack
{
    private int[] stackArray;
    private int top;

    public DynamicStack(int initialCapacity = 5)
    {
        stackArray = new int[initialCapacity];
        top = -1; // empty stack
    }

    public void Push(int value)
    {
        if (top == stackArray.Length - 1)
        {
            Resize(); // double the array size
        }
        top++;
        stackArray[top] = value;
    }

    private void Resize()
    {
        int newCapacity = stackArray.Length * 2;
        int[] newArray = new int[newCapacity];
        for (int i = 0; i <= top; i++)
        {
            newArray[i] = stackArray[i];
        }
        stackArray = newArray;
    }

    public int Pop()
    {
        if (top == -1) throw new InvalidOperationException("Stack is empty");
        int value = stackArray[top];
        top--;
        return value;
    }

    public override string ToString()
    {
        if (top == -1) return "Stack is empty";
        string result = "";
        for (int i = 0; i <= top; i++)
        {
            result += stackArray[i] + (i == top ? "" : " -> ");
        }
        result += " -> null";
        return result;
    }
}

public class Program
{
    public static void Main()
    {
        DynamicStack stack = new DynamicStack(5);
        stack.Push(1);
        stack.Push(2);
        stack.Push(3);
        stack.Push(4);
        stack.Push(5);
        stack.Push(6); // triggers resize
        Console.WriteLine(stack.ToString());
    }
}

if (top == stackArray.Length - 1)

check if stack is full and needs resizing

Resize();

double the array size and copy existing items

top++;

move top pointer up to next free position

stackArray[top] = value;

store new value at top position

Output

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

Complexity Analysis

Time: O(n) for resize operation because we copy all existing elements; O(1) amortized for push because resize happens rarely

Space: O(n) because we store all elements in an array that grows as needed

vs Alternative: Compared to fixed-size stack, dynamic stack uses extra time and space during resize but avoids overflow errors and manual resizing

Edge Cases

Push on empty stack

Works normally, top moves from -1 to 0 and value stored

DSA C#

top == stackArray.Length - 1

Push when stack is full

Triggers resize doubling capacity before adding new item

DSA C#

if (top == stackArray.Length - 1)

Pop from empty stack

Throws InvalidOperationException to prevent underflow

DSA C#

if (top == -1) throw new InvalidOperationException("Stack is empty");

When to Use This Pattern

When you need a stack but don't know the max size upfront, use a dynamic stack with resizing to handle any number of pushes safely.

Common Mistakes

Mistake: Not resizing the array when full, causing index out of range errors
Fix: Add a resize method and call it before pushing when the array is full

Mistake: Forgetting to increment top before storing new value
Fix: Always increment top first, then assign the value at top

Summary

It stores items in a stack using an array that grows automatically when full.

Use it when you want a stack but the number of items is unknown or can grow beyond initial size.

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

Practice

1. What is the main advantage of using a dynamic stack with a resizable array over 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 fixed-size array stack.

C. It always has a fixed capacity to avoid resizing overhead.

D. It does not allow popping elements.

Solution

1. Step 1: Understand fixed-size array stack limitation

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

2. Step 2: Understand dynamic stack advantage

   A dynamic stack resizes its array automatically when full, allowing more elements without overflow.

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 stacks resize arrays automatically when full [OK]

Common Mistakes:

• Thinking dynamic stack uses less memory always
• Believing dynamic stack has fixed capacity
• Confusing dynamic stack with linked list stack

2. Which of the following is the correct way to double the size of the internal array in a dynamic stack in C#?

easy

A. array = new int[array.Length * 2];

B. array.Length = array.Length * 2;

C. array = array.Concat(array).ToArray();

D. Array.Resize(ref array, array.Length * 2);

Solution

1. Step 1: Understand array resizing in C#

   Arrays in C# have fixed length; to resize, use Array.Resize(ref array, newSize) which copies old elements.

2. Step 2: Analyze options

   Array.Resize(ref array, array.Length * 2); uses Array.Resize correctly. array = new int[array.Length * 2]; creates a new array but loses old data. array.Length = array.Length * 2; is invalid syntax. array = array.Concat(array).ToArray(); uses LINQ but is inefficient and not typical for stack resizing.

3. Final Answer:

   Array.Resize(ref array, array.Length * 2); -> Option D

4. Quick Check:

   Array.Resize method resizes arrays properly [OK]

Hint: Use Array.Resize(ref array, newSize) to resize arrays in C# [OK]

Common Mistakes:

• Trying to set array.Length directly
• Creating new array without copying old data
• Using LINQ Concat for resizing inefficiently

3. Consider the following C# code for a dynamic stack using a resizable array:

DynamicStack stack = new DynamicStack();
stack.Push(10);
stack.Push(20);
stack.Push(30);
stack.Pop();
stack.Push(40);
stack.PrintStack();

What will be the printed output?

medium

A. 30 -> 20 -> 10 -> null

B. 40 -> 20 -> 10 -> null

C. 20 -> 10 -> null

D. 40 -> 30 -> 20 -> 10 -> null

Solution

1. Step 1: Trace stack operations

   Push 10, stack: 10
   Push 20, stack: 20 -> 10
   Push 30, stack: 30 -> 20 -> 10
   Pop removes 30, stack: 20 -> 10
   Push 40, stack: 40 -> 20 -> 10

2. Step 2: Determine printed output

   PrintStack prints from top to bottom ending with null: 40 -> 20 -> 10 -> null

3. Final Answer:

   40 -> 20 -> 10 -> null -> Option B

4. Quick Check:

   Stack top after operations = 40 [OK]

Hint: Track push/pop order carefully to find top element [OK]

Common Mistakes:

• Forgetting pop removes top element
• Printing stack in wrong order
• Including popped elements in output

4. The following code snippet for a dynamic stack has a bug. What is the error?

public void Push(int item) {
  if (top == array.Length) {
    Array.Resize(ref array, array.Length * 2);
  }
  array[top] = item;
  top++;
}

medium

A. No bug; the code resizes and pushes correctly.

B. The top variable should be incremented before assigning the item.

C. The condition should be top == array.Length to resize, but top starts at 1 instead of 0.

D. The condition should be top == array.Length - 1 to resize.

Solution

1. Step 1: Analyze resizing condition

   top equals array.Length means array is full, so resizing is needed before adding new item.

2. Step 2: Check push logic

   Assign item at array[top], then increment top. This correctly places item and moves top pointer.

3. Final Answer:

   No bug; the code resizes and pushes correctly. -> Option A

4. Quick Check:

   Resize when full, assign then increment top [OK]

Hint: Resize when top equals length; assign then increment top [OK]

Common Mistakes:

• Using wrong resize condition (off by one)
• Incrementing top before assignment
• Assuming top starts at 1 instead of 0

5. You want to implement a dynamic stack that shrinks its internal array size by half when the number of elements falls below one-quarter of the array capacity. Which approach correctly handles this resizing to optimize memory without losing data?

hard

A. Resize array to array.Length * 2 after popping elements to avoid frequent resizing.

B. Resize array to array.Length / 4 whenever an element is popped.

C. After popping, check if top <= array.Length / 4, then resize array to array.Length / 2 using Array.Resize(ref array, newSize).

D. Never shrink the array to avoid complexity; only grow it when full.

Solution

1. Step 1: Understand shrinking condition

   To save memory, shrink when usage is low: top ≤ 1/4 capacity triggers halving the array size.

2. Step 2: Apply resizing correctly

   Use Array.Resize(ref array, array.Length / 2) to shrink safely after popping, preserving existing elements.

3. Final Answer:

   After popping, check if top <= array.Length / 4, then resize array to array.Length / 2 using Array.Resize(ref array, newSize). -> Option C

4. Quick Check:

   Shrink when quarter full using Array.Resize [OK]

Hint: Shrink array when usage ≤ 25% by halving size [OK]

Common Mistakes:

• Shrinking too often causing overhead
• Shrinking to quarter size instead of half
• Not preserving data during resize