Stack Implementation Using Array in DSA C#

Mental Model

A stack is like a pile where you add or remove items only from the top. Using an array, we keep track of the top position to add or remove elements.

Analogy: Imagine a stack of plates. You can only put a new plate on top or take the top plate off. The array is like a shelf with fixed spots, and the top pointer shows where the last plate is.

Array: [ _ , _ , _ , _ , _ ]
Top: -1 (means empty stack)

Dry Run Walkthrough

Input: Create stack of size 5, push 10, push 20, pop, push 30

Goal: Show how the stack changes after each push and pop operation using an array

Step 1: Push 10 onto stack

Array: [ 10 , _ , _ , _ , _ ]
Top: 0

Why: We add 10 at index 0 and update top to 0 to mark the new top

Step 2: Push 20 onto stack

Array: [ 10 , 20 , _ , _ , _ ]
Top: 1

Why: We add 20 at index 1 and move top to 1

Step 3: Pop top element

Array: [ 10 , 20 , _ , _ , _ ]
Top: 0

Why: We remove 20 by moving top back to 0, 20 is no longer considered in stack

Step 4: Push 30 onto stack

Array: [ 10 , 30 , _ , _ , _ ]
Top: 1

Why: We add 30 at index 1 and update top to 1

Result:

Array: [ 10 , 30 , _ , _ , _ ]
Top: 1
Stack content: 10 -> 30 -> null

Annotated Code

DSA C#

using System;

class Stack {
    private int[] arr;
    private int top;
    private int capacity;

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

    public void Push(int item) {
        if (top == capacity - 1) {
            Console.WriteLine("Stack Overflow");
            return;
        }
        top++; // move top up
        arr[top] = item; // place item at top
    }

    public int Pop() {
        if (top == -1) {
            Console.WriteLine("Stack Underflow");
            return -1; // indicates empty
        }
        int item = arr[top];
        top--; // move top down
        return item;
    }

    public void PrintStack() {
        if (top == -1) {
            Console.WriteLine("Stack is empty");
            return;
        }
        for (int i = 0; i <= top; i++) {
            Console.Write(arr[i]);
            if (i != top) Console.Write(" -> ");
        }
        Console.WriteLine(" -> null");
    }
}

class Program {
    static void Main() {
        Stack stack = new Stack(5);
        stack.Push(10); // step 1
        stack.Push(20); // step 2
        stack.Pop();    // step 3
        stack.Push(30); // step 4
        stack.PrintStack();
    }
}

if (top == capacity - 1) { Console.WriteLine("Stack Overflow"); return; }

check if stack is full before pushing

top++; arr[top] = item;

increment top and add new item at top

if (top == -1) { Console.WriteLine("Stack Underflow"); return -1; }

check if stack is empty before popping

int item = arr[top]; top--; return item;

retrieve top item and decrement top to remove it

for (int i = 0; i <= top; i++) { Console.Write(arr[i]); if (i != top) Console.Write(" -> "); }

print all elements from bottom to top with arrows

Output

10 -> 30 -> null

Complexity Analysis

Time: O(1) for push and pop because we add or remove only at the top without looping

Space: O(n) where n is the capacity because we store elements in a fixed-size array

vs Alternative: Compared to linked list stack, array stack uses fixed memory but is faster and simpler without pointers

Edge Cases

Push when stack is full

Prints 'Stack Overflow' and does not add element

DSA C#

if (top == capacity - 1) { Console.WriteLine("Stack Overflow"); return; }

Pop when stack is empty

Prints 'Stack Underflow' and returns -1

DSA C#

if (top == -1) { Console.WriteLine("Stack Underflow"); return -1; }

Print empty stack

Prints 'Stack is empty'

DSA C#

if (top == -1) { Console.WriteLine("Stack is empty"); return; }

When to Use This Pattern

When you need last-in-first-out order with fixed size and fast access, use stack with array to manage elements by a top pointer.

Common Mistakes

Mistake: Incrementing top after assigning value causes off-by-one error
Fix: Increment top first, then assign the new value at arr[top]

Mistake: Not checking for overflow before push leads to array index error
Fix: Always check if top == capacity - 1 before pushing

Mistake: Not checking for underflow before pop leads to invalid access
Fix: Check if top == -1 before popping

Summary

Implements a stack using a fixed-size array and a top pointer to add/remove elements.

Use when you want a simple last-in-first-out structure with known maximum size.

The key is to track the top index to know where to push or pop elements efficiently.

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