Dynamic Stack Using Resizable Array in DSA C# - Execution Trace

Concept Flow - Dynamic Stack Using Resizable Array

Start

↓

Push Operation?

No→Pop Operation?

↓

Is array full?

↓

Add element

↓

Update top index

↓

Resize array if full

↓

Back to Start

Shows how push and pop operations work on a dynamic stack using a resizable array, including checks for resizing and empty stack.

Execution Sample

DSA C#

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

Push 10, 20, 30; pop top element; then push 40 on the dynamic stack.

Execution Table

Step	Operation	Nodes in Array	Top Index	Array Capacity	Visual State
1	Initialize stack	[]	-1	2	[]
2	Push 10	[10]	0	2	[10]
3	Push 20	[10, 20]	1	2	[10, 20]
4	Push 30 (resize)	[10, 20, 30, _]	2	4	[10, 20, 30, _]
5	Pop top element	[10, 20, 30, _]	1	4	[10, 20, _, _]
6	Push 40	[10, 20, 40, _]	2	4	[10, 20, 40, _]
7	End	[10, 20, 40, _]	2	4	[10, 20, 40, _]

💡 Execution stops after final push; stack contains 3 elements with capacity 4.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
Top Index	-1	0	1	2	1	2	2
Array Capacity	2	2	2	4	4	4	4
Array Elements	[]	[10]	[10, 20]	[10, 20, 30, _]	[10, 20, _, _]	[10, 20, 40, _]	[10, 20, 40, _]

Key Moments - 3 Insights

Why do we resize the array when pushing the third element?

Because the initial capacity is 2, pushing the third element exceeds it, so we double the capacity to 4 before adding the new element (see Step 4 in execution_table).

Why does the top index decrease after popping an element?

Popping removes the top element, so the top index moves down by one to point to the new top (see Step 5 in execution_table).

What happens to the array elements after popping?

The element is logically removed by decreasing top index; the array slot remains but is considered empty (shown as '_' in Visual State at Step 5).

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the array capacity after resizing?

A 4

B 3

C 2

D 5

💡 Hint

Check the 'Array Capacity' column at Step 4 in execution_table.

At which step does the top index become 1?

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look at the 'Top Index' column in variable_tracker after Step 3.

If we pop one more time after Step 5, what will be the top index?

A 0

B 1

C -1

D 2

💡 Hint

Popping decreases top index by 1; see how top index changes in execution_table Step 5.

Concept Snapshot

Dynamic Stack Using Resizable Array:
- Uses array with initial capacity.
- Push adds element; if full, array size doubles.
- Pop removes top element, decreases top index.
- Top index tracks current top position.
- Visual state shows array with '_' as empty slots.

Full Transcript

This visual trace shows a dynamic stack implemented with a resizable array. Initially, the stack is empty with capacity 2. Pushing elements 10 and 20 fills the array. Pushing the third element triggers resizing, doubling capacity to 4. Popping removes the top element by decreasing the top index, leaving the slot empty but unchanged in the array. Pushing 40 adds it to the next available slot. The top index and array capacity update accordingly. This helps understand how dynamic resizing and stack operations work together.

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