Stack Implementation Using Array in DSA C# - Execution Trace

Concept Flow - Stack Implementation Using Array

Start

↓

Initialize array and top = -1

↓

Push operation?

Yes→Check if top < max size - 1

↓

Stack Overflow

↓

Stop

No↓

Pop operation?

Yes→Check if top >= 0

↓

Stack Underflow

↓

Stop

No↓

Peek or Display

↓

Stop

The stack starts empty with top at -1. Push adds element if space is available. Pop removes element if stack is not empty. Overflow and underflow are checked.

Execution Sample

DSA C#

int[] stack = new int[3];
int top = -1;
// Push 10
stack[++top] = 10;
// Push 20
stack[++top] = 20;
// Pop
int x = stack[top--];

This code pushes 10 and 20 onto the stack, then pops the top element.

Execution Table

Step	Operation	Top Index	Array State	Pointer Changes	Visual State
1	Initialize stack	-1	[null, null, null]	top = -1	Stack is empty: []
2	Push 10	0	[10, null, null]	top: -1 -> 0	10 -> null
3	Push 20	1	[10, 20, null]	top: 0 -> 1	10 -> 20 -> null
4	Pop	0	[10, 20, null]	top: 1 -> 0	10 -> null
5	Push 30	1	[10, 30, null]	top: 0 -> 1	10 -> 30 -> null
6	Push 40	2	[10, 30, 40]	top: 1 -> 2	10 -> 30 -> 40 -> null
7	Push 50 (Overflow)	2	[10, 30, 40]	top: 2 (no change)	Stack Overflow - no change
8	Pop	1	[10, 30, 40]	top: 2 -> 1	10 -> 30 -> null
9	Pop	0	[10, 30, 40]	top: 1 -> 0	10 -> null
10	Pop	-1	[10, 30, 40]	top: 0 -> -1	Stack is empty: []
11	Pop (Underflow)	-1	[10, 30, 40]	top: -1 (no change)	Stack Underflow - no change

💡 Execution stops after underflow or overflow conditions prevent further push/pop.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11
top	-1	0	1	0	1	2	2	1	0	-1	-1
stack	[null, null, null]	[10, null, null]	[10, 20, null]	[10, 20, null]	[10, 30, null]	[10, 30, 40]	[10, 30, 40]	[10, 30, 40]	[10, 30, 40]	[10, 30, 40]	[10, 30, 40]

Key Moments - 3 Insights

Why does top start at -1 instead of 0?

Top starts at -1 to indicate the stack is empty. When we push, top increments first to 0, pointing to the first element. See Step 1 and Step 2 in execution_table.

What happens when we try to push but the stack is full?

If top equals max size - 1 (2 here), pushing more causes overflow. The top does not change and the array stays the same. See Step 7 in execution_table.

Why does popping when stack is empty cause underflow?

When top is -1, no elements exist to pop. Trying to pop then does nothing and signals underflow. See Step 11 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of top after Step 5?

A 1

B 0

C 2

D -1

💡 Hint

Check the 'Top Index' column at Step 5 in execution_table.

At which step does the stack overflow occur?

A Step 6

B Step 7

C Step 8

D Step 11

💡 Hint

Look for 'Stack Overflow' in the 'Visual State' column in execution_table.

If we remove Step 7 (overflow attempt), what would be the top index after Step 6?

A 2

B 1

C 0

D -1

💡 Hint

Step 6 shows top moving to 2 after pushing 40, before overflow attempt.

Concept Snapshot

Stack using array:
- Use array and 'top' index
- top = -1 means empty
- Push: top++, add element
- Pop: remove element, top--
- Check overflow (top == max-1)
- Check underflow (top == -1)

Full Transcript

This visualization shows how a stack is implemented using an array. The stack starts empty with top at -1. Each push operation increases top by one and adds the element at that position. Each pop removes the element at top and decreases top. Overflow happens if we try to push when the stack is full, and underflow happens if we pop when empty. The execution table tracks each step, showing the array contents, top index, and visual state of the stack. Key moments clarify why top starts at -1, what overflow and underflow mean. The quiz tests understanding of top changes and overflow detection.

Practice

1. What is the main purpose of using an array in a stack implementation?

easy

A. To allow random access to elements anywhere in the stack

B. To store elements in a fixed-size, ordered collection

C. To automatically resize the stack when full

D. To sort elements as they are added

Solution

1. Step 1: Understand stack storage

   A stack stores elements in order, last-in first-out, so it needs a structure to hold elements sequentially.

2. Step 2: Role of array in stack

   An array provides a fixed-size, ordered collection to hold stack elements efficiently.

3. Final Answer:

   To store elements in a fixed-size, ordered collection -> Option B

4. Quick Check:

   Stack uses array for fixed order storage [OK]

Hint: Stack uses array for fixed order storage, not random access [OK]

Common Mistakes:

• Thinking array resizes automatically
• Confusing stack with queue behavior
• Assuming array sorts elements

2. Which of the following is the correct way to declare an integer stack array of size 5 in C#?

easy

A. int[] stack = new int[5];

B. int stack = new int[5];

C. int[] stack = int[5];

D. stack int[] = new int(5);

Solution

1. Step 1: Recall C# array declaration syntax

   In C#, arrays are declared with type[], variable name, and new type[size].

2. Step 2: Match correct syntax

   int[] stack = new int[5]; matches this pattern: int[] stack = new int[5];

3. Final Answer:

   int[] stack = new int[5]; -> Option A

4. Quick Check:

   C# array declaration = int[] name = new int[size]; [OK]

Hint: Use type[] name = new type[size]; for arrays in C# [OK]

Common Mistakes:

• Missing [] after type
• Using parentheses instead of brackets
• Incorrect variable declaration order

3. What will be the output after the following operations on a stack implemented using an array of size 3?

Push(10); Push(20); Pop(); Push(30); Pop(); Pop();

Assume the stack is initially empty and prints the popped values.

medium

A. 20 30 10

B. 20 30 20

C. 20 30 30

D. 10 20 30

Solution

1. Step 1: Trace each operation step-by-step

   Push(10) stack=[10]
   Push(20) stack=[10,20]
   Pop() removes 20, output=20, stack=[10]
   Push(30) stack=[10,30]
   Pop() removes 30, output=30, stack=[10]
   Pop() removes 10, output=10, stack=[]

2. Step 2: Collect popped outputs in order

   The popped values printed are 20, then 30, then 10.

3. Final Answer:

   20 30 10 -> Option A

4. Quick Check:

   Stack LIFO pop order = 20 30 10 [OK]

Hint: Pop prints last pushed element, follow LIFO order [OK]

Common Mistakes:

• Confusing push and pop order
• Assuming FIFO instead of LIFO
• Missing last pop output

4. Identify the error in this stack push method code snippet in C#:

public void Push(int item) {
  if (top == stack.Length) {
    Console.WriteLine("Stack Overflow");
  }
  stack[top] = item;
  top++;
}

medium

A. top should be compared with stack.Length - 1

B. top++ should be before assigning stack[top]

C. No return after overflow check causes overwrite

D. stack array should be resized when full

Solution

1. Step 1: Analyze overflow check logic

   The code checks if top == stack.Length and prints overflow, but continues to assign and increment top anyway.

2. Step 2: Identify missing control flow after overflow

   Without a return or exit after overflow message, the code overwrites stack[top] causing error.

3. Final Answer:

   No return after overflow check causes overwrite -> Option C

4. Quick Check:

   Overflow check must stop push to avoid overwrite [OK]

Hint: Stop push after overflow check to prevent overwrite [OK]

Common Mistakes:

• Assuming top comparison off by one
• Moving top++ before assignment causes wrong index
• Ignoring need to stop after overflow

5. You want to implement a stack using an array that doubles its size automatically when full. Which approach correctly achieves this in C#?

hard

A. Increase the size of the existing array using stack.Resize() method

B. Overwrite oldest elements when stack is full to make space

C. Use a List<int> instead of array to avoid resizing manually

D. Create a new array double the size, copy elements, then assign it to the stack variable

Solution

1. Step 1: Understand array resizing in C#

   Arrays have fixed size; to resize, create a new larger array and copy elements over.

2. Step 2: Evaluate options for resizing stack array

   Create a new array double the size, copy elements, then assign it to the stack variable correctly describes creating a new array double the size, copying elements, and reassigning stack variable.

3. Final Answer:

   Create a new array double the size, copy elements, then assign it to the stack variable -> Option D

4. Quick Check:

   Resize array by new array + copy + assign [OK]

Hint: Arrays fixed size; resize by new array and copy [OK]

Common Mistakes:

• Assuming arrays can resize in place
• Using non-existent Resize method on arrays
• Overwriting data instead of resizing