Hello, dear student! Today's lesson will take you on an exciting journey through Stacks, a powerful tool in C#. In programming, Stacks are fundamental data structures utilized in various applications. Our goal for this lesson is to understand the concept of Stacks, learn how to implement and manipulate them in C#, and delve deep into their complexities. Let's get started!

First and foremost, let's understand what a Stack is. Imagine a stack of plates that you can only remove from the top. That's precisely what a Stack is: a Last-In, First-Out (LIFO) structure. Stacks are used in memory management, backtracking algorithms, and more. The key operations involved are Push (adding an element to the top of the stack), Pop (removing the topmost element), and Peek (looking at the topmost element without removing it).

C# provides two common ways to implement Stacks: Array-based and Linked-list-based. An array-based stack uses a fixed-size array for element storage, allowing fast access but limited by capacity, while a linked-list-based stack uses dynamically allocated nodes, offering flexible growth without space wastage. We will be focusing on array-based stacks due to their simplistic implementation and constant-time operation when working within capacity. Let's look into creating a Stack using an array in C#:

C#
Copy to clipboard
1class Stack{
2    int size;
3    int top = -1;
4    int[] stackArray;
5  
6    public Stack(int size){
7        this.size = size;
8        stackArray = new int[size];
9    }
10}

top represents the index in the stackArray that is currently the top element of the stack. It is initialized to -1, showing the stack is empty, and there is no valid index for the top element.

A Stack involves three operations — Push, Pop, and Peek. In an array-based Stack, the Push operation adds a new element at the top of the Stack. Here’s how we can write a push function:

C#
Copy to clipboard
1public void Push(int data){
2    if(top < size - 1){
3        stackArray[++top] = data;
4    } else {
5        Console.WriteLine("Stack Overflows");
6    }
7}

Before adding the element, the method checks if the stack is full by comparing top with size-1 (maximum array index). If it's less, we still have room to insert the element; otherwise, it gives a "Stack Overflows" message. The ++top operation increments the top variable (which represents the top element index in the stack) by one and then uses this new value as an index to add the data element into the stackArray.

The Pop operation removes the topmost element from the Stack.

C#
Copy to clipboard
1public int Pop() {
2    if (top > -1) {
3        return stackArray[top--];
4    } else {
5        Console.WriteLine("Stack Underflows");
6        return -1;
7    }
8}

This method removes and returns the top item of the stack. It checks if the stack is empty by checking if top is greater than -1. If it is, it decrements top and returns the element that was just removed from the top of the stack. Notice that we do not actually remove the element from the array. We decrease the top variable, so it no longer points to the popped element.

Lastly, the Peek operation returns the topmost element without removing it from the Stack.

C#
Copy to clipboard
1public int Peek() {
2    if (top > -1) {
3        return stackArray[top];
4    } else {
5        Console.WriteLine("Stack is Empty");
6        return -1;
7    }
8}

Since we perform them at one end of the data structure, the Push, Pop, and Peek operations take constant time, represented as O(1). Space complexity refers to the space taken by the Stack, proportional to the number of elements. Hence, it is represented as O(n), where n is the number of elements in the Stack.

While understanding the inner structure of a stack is essential to grasp its capabilities, implementing it manually is not a necessity. C# offers the built-in Stack<T> class in the System.Collections.Generic namespace, which provides methods such as Push(), Pop(), and Peek(). The Stack<T> class is dynamic, automatically adjusting its capacity as elements are added or removed. This flexibility stems from its efficient internal management, allowing it to seamlessly handle a varying number of elements without the need for a predefined size.

Here's an example of how you can use the built-in Stack<T> class:

C#
Copy to clipboard
1using System;
2using System.Collections.Generic;
3
4class Program { 
5    public static void Main(string[] args) { 
6        Stack<int> stack = new Stack<int>(); 
7
8        // Performing the push operation
9        stack.Push(10); 
10        stack.Push(20); 
11        stack.Push(30); 
12
13        Console.WriteLine("Stack: [" + string.Join(", ", stack) + "]"); 
14
15        // Performing the pop operation
16        int popped = stack.Pop();
17        Console.WriteLine("Popped from stack: " + popped);
18
19        // Performing the peek operation
20        int peeked = stack.Peek();
21        Console.WriteLine("Peeked from stack: " + peeked);
22    } 
23}

The output will be:

Copy to clipboard
1Stack: [30, 20, 10]
2Popped from stack: 30
3Peeked from stack: 20

This example showcases the creation of a Stack and the utilization of the Push(), Pop(), and Peek() methods. Besides these operations, C#'s Stack<T> class also includes methods like IsEmpty() to check if the stack is empty by comparing the count and Contains(Object o) to check if the stack contains a specific element.

Congratulations, you've completed the lesson on Stacks in C#! You will now proceed to the practice sessions using the concepts learned here. These hands-on practice exercises will help solidify your knowledge and improve your problem-solving skills. So, get ready to roll up your sleeves and dive right in!