Dynamic Stack Using Resizable Array in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after these stack operations?

Consider a dynamic stack implemented using a resizable array. The stack doubles its capacity when full.

Starting with an empty stack of capacity 2, perform these operations:

Push(10)
Push(20)
Push(30)
Pop()
Push(40)

What is the printed stack content from top to bottom?

DSA C#

class DynamicStack {
    private int[] arr = new int[2];
    private int top = -1;

    public void Push(int val) {
        if (top == arr.Length - 1) {
            int[] newArr = new int[arr.Length * 2];
            for (int i = 0; i < arr.Length; i++) newArr[i] = arr[i];
            arr = newArr;
        }
        arr[++top] = val;
    }

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

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

var stack = new DynamicStack();
stack.Push(10);
stack.Push(20);
stack.Push(30);
stack.Pop();
stack.Push(40);
Console.WriteLine(stack.ToString());

A 30 -> 20 -> 10 -> null

B 40 -> 20 -> 10 -> null

C 20 -> 10 -> null

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

💡 Hint

Remember the stack grows and shrinks. The top is the last pushed item not popped.

After pushing 10, 20, 30, the stack is [10, 20, 30]. Popping removes 30. Then pushing 40 adds it on top. So stack is [10, 20, 40] with 40 on top.

🧠 Conceptual

intermediate

What happens when the stack is full and a new element is pushed?

In a dynamic stack using a resizable array, what is the typical behavior when the internal array is full and a new element is pushed?

A The stack throws an overflow error and stops.

B The stack halves the array size to save space before adding the new element.

C The stack doubles the array size, copies old elements, then adds the new element.

D The stack ignores the new element and keeps the old elements.

💡 Hint

Think about how dynamic arrays grow to accommodate more elements.

When the array is full, the stack creates a new array twice as big, copies all elements, then adds the new element. This avoids overflow.

🔧 Debug

advanced

Identify the bug in this Pop method

Given this Pop method in a dynamic stack, what is the bug?

public int Pop() {
    if (top == 0) throw new InvalidOperationException("Stack empty");
    return arr[top--];
}

A The condition should be 'top == -1' to check for empty stack.

B There is no bug; the code works correctly.

C The method should throw NullReferenceException instead.

D The method should not decrement top after returning the value.

💡 Hint

Think about how the top index is initialized and what value means empty.

Top starts at -1 when empty. Checking 'top == 0' misses empty state and causes errors when popping from empty stack.

❓ Predict Output

advanced

What is the capacity after these pushes?

Starting with an empty dynamic stack with initial capacity 1, what is the capacity after pushing these elements?

Push(5)
Push(10)
Push(15)
Push(20)

DSA C#

class DynamicStack {
    private int[] arr = new int[1];
    private int top = -1;

    public void Push(int val) {
        if (top == arr.Length - 1) {
            int[] newArr = new int[arr.Length * 2];
            for (int i = 0; i < arr.Length; i++) newArr[i] = arr[i];
            arr = newArr;
        }
        arr[++top] = val;
    }

    public int Capacity() {
        return arr.Length;
    }
}

var stack = new DynamicStack();
stack.Push(5);
stack.Push(10);
stack.Push(15);
stack.Push(20);
Console.WriteLine(stack.Capacity());

A 4

B 8

C 2

D 1

💡 Hint

Remember the array doubles capacity when full.

Initial capacity 1 doubles to 2 after first push fills it, then doubles to 4 after pushing third element. So capacity is 4 after 4 pushes.

🧠 Conceptual

expert

Why is dynamic resizing important in stack implementation?

Why do we use dynamic resizing (like doubling array size) in stack implementations using arrays?

A To prevent the stack from ever becoming empty.

B To avoid wasting memory by always allocating a large fixed array.

C To make pop operations faster by shrinking the array frequently.

D To ensure the stack can grow beyond initial capacity without errors and maintain efficient push operations.

💡 Hint

Think about balancing memory use and ability to add many elements.

Dynamic resizing allows the stack to grow as needed without fixed limits, while keeping push operations efficient by doubling size only when full.

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