C# Stack

The `Stack<T>` class in C# is a part of the `System.Collections.Generic` namespace and represents a last-in, first-out (LIFO) collection of objects. It is ideal for scenarios where you need to process items in the reverse order they were added. Understanding `Stack<T>` is essential for implementing efficient algorithms, managing undo operations, and handling recursive processes in C# applications.

Table of Contents

1. Introduction to Stack<T>
- What is Stack<T>?
- Benefits of Using Stack<T>

2. Declaring and Initializing Stack<T>
- Declaration Syntax
- Initialization Methods
- Collection Initializers

3. Adding and Removing Elements
- Push
- Pop
- Peek
- TryPop and TryPeek
- Clear

4. Accessing Elements
- Access by Index
- Converting to Array

5. Iterating Through Stack<T>
- Using foreach Loop
- Using LINQ Queries

6. Searching Elements
- Contains Method
- Find Methods (using LINQ)

7. Capacity and Performance
- Understanding Capacity vs. Count
- Managing Capacity
- Performance Considerations

8. Common Methods and Properties
- Key Methods
- Important Properties

9. Best Practices
- Choosing the Right Stack<T> Usage
- Handling Exceptions Gracefully
- Minimizing Locking Overhead in Multi-threaded Scenarios

10. Common Mistakes with Stack<T>
- Attempting to Pop from an Empty Stack
- Modifying the Stack During Iteration
- Using Incorrect Element Types

11. Advanced Topics
- Thread-Safe Stacks with ConcurrentStack<T>
- Implementing Custom Stack Behavior
- Serialization of Stacks

12. Real-World Example
13. Summary

1. Introduction to Stack<T>

What is Stack<T>?

using System.Collections.Generic;

Stack<T> stack = new Stack<T>();

Benefits of Using Stack<T>

2. Declaring and Initializing Stack<T>

2.1 Declaration Syntax

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Stack<int> numbersStack = new Stack<int>();
    }
}

2.2 Initialization Methods

Stack<string> fruitsStack = new Stack<string>();

Stack<string> fruitsStack = new Stack<string>(100);

2.3 Collection Initializers

Stack<string> fruitsStack = new Stack<string>(new[] { "Apple", "Banana", "Cherry" });

3. Adding and Removing Elements

3.1 Push

Stack<string> fruitsStack = new Stack<string>();
fruitsStack.Push("Apple");
fruitsStack.Push("Banana");

3.2 Pop

string topFruit = fruitsStack.Pop(); // "Banana"

3.3 Peek

string nextFruit = fruitsStack.Peek(); // "Apple"

3.4 TryPop and TryPeek

if(fruitsStack.TryPop(out string poppedFruit))
{
    Console.WriteLine($"Popped: {poppedFruit}");
}
else
{
    Console.WriteLine("Stack is empty.");
}

if(fruitsStack.TryPeek(out string peekedFruit))
{
    Console.WriteLine($"Next in Stack: {peekedFruit}");
}
else
{
    Console.WriteLine("Stack is empty.");
}

3.5 Clear

fruitsStack.Clear();

4. Accessing Elements

4.1 Access by Index

string[] fruitsArray = fruitsStack.ToArray();
string firstFruit = fruitsArray[0];

4.2 Converting to Array

Stack<string> fruitsStack = new Stack<string>();
fruitsStack.Push("Apple");
fruitsStack.Push("Banana");
fruitsStack.Push("Cherry");

string[] fruitsArray = fruitsStack.ToArray();

Console.WriteLine("Fruits Array:");
foreach(var fruit in fruitsArray)
{
    Console.WriteLine(fruit);
}

Sample Output:
Fruits Array:
Cherry
Banana
Apple

5. Iterating Through Stack<T>

5.1 Using foreach Loop

Stack<string> fruitsStack = new Stack<string>();
fruitsStack.Push("Apple");
fruitsStack.Push("Banana");
fruitsStack.Push("Cherry");

Console.WriteLine("Iterating using foreach:");
foreach(string fruit in fruitsStack)
{
    Console.WriteLine(fruit);
}

Sample Output:
Iterating using foreach:
Cherry
Banana
Apple

5.2 Using LINQ Queries

using System.Linq;

var selectedFruits = fruitsStack.Where(f => f.StartsWith("B"));

Console.WriteLine("Fruits starting with 'B':");
foreach(var fruit in selectedFruits)
{
    Console.WriteLine(fruit);
}

Sample Output:
Fruits starting with 'B':
Banana

6. Searching Elements

6.1 Contains Method

bool hasBanana = fruitsStack.Contains("Banana");
Console.WriteLine($"Contains Banana: {hasBanana}"); // Output: True

6.2 Finding Elements with LINQ

using System.Linq;

string firstC = fruitsStack.FirstOrDefault(f => f.StartsWith("C"));
Console.WriteLine($"First fruit starting with 'C': {firstC}"); // Output: Cherry

6.3 Finding All Matching Elements

using System.Linq;

var fruitsWithA = fruitsStack.Where(f => f.Contains("a") || f.Contains("A"));

Console.WriteLine("Fruits containing 'a' or 'A':");
foreach(var fruit in fruitsWithA)
{
    Console.WriteLine(fruit);
}

Sample Output:
Fruits containing 'a' or 'A':
Banana
Apple

7. Capacity and Performance

7.1 Understanding Capacity vs. Count

Stack<int> numbersStack = new Stack<int>();
Console.WriteLine($"Initial Count: {numbersStack.Count}"); // Output: 0

numbersStack.Push(1);
Console.WriteLine($"Count after adding one element: {numbersStack.Count}"); // Output: 1

numbersStack.Push(2);
Console.WriteLine($"Count after adding two elements: {numbersStack.Count}"); // Output: 2

7.2 Managing Capacity

numbersStack.TrimExcess();

7.3 Performance Considerations

8. Common Methods and Properties

8.1 Key Methods

8.2 Important Properties

9. Best Practices

9.1 Choosing the Right Stack<T> Usage

9.2 Handling Exceptions Gracefully

if(numbersStack.TryPop(out int number))
{
  Console.WriteLine($"Popped: {number}");
}
else
{
  Console.WriteLine("Stack is empty.");
}

9.3 Minimizing Locking Overhead in Multi-threaded Scenarios

using System.Collections.Concurrent;

ConcurrentStack<int> concurrentStack = new ConcurrentStack<int>();
concurrentStack.Push(1);
if(concurrentStack.TryPop(out int result))
{
  Console.WriteLine($"Popped: {result}");
}

9.4 Avoiding Unnecessary Operations

if(fruitsStack.Count > 0)
{
  string fruit = fruitsStack.Pop();
  Console.WriteLine($"Popped: {fruit}");
}
else
{
  Console.WriteLine("Stack is empty.");
}

9.5 Using Appropriate Data Types

10. Common Mistakes with Stack<T>

10.1 Attempting to Pop from an Empty Stack

Stack<int> numbersStack = new Stack<int>();
int number = numbersStack.Pop(); // Throws InvalidOperationException

if(numbersStack.TryPop(out int number))
{
    Console.WriteLine($"Popped: {number}");
}
else
{
    Console.WriteLine("Stack is empty.");
}

10.2 Modifying the Stack During Iteration

foreach(var item in fruitsStack)
{
    if(item == "Banana")
    {
        fruitsStack.Pop(); // InvalidOperationException
    }
}

while(fruitsStack.Count > 0)
{
    var fruit = fruitsStack.Pop();
    if(fruit == "Banana")
    {
        // Handle Banana
    }
}

10.3 Using Incorrect Element Types

11. Advanced Topics

11.1 Thread-Safe Stacks with ConcurrentStack<T>

using System;
using System.Collections.Concurrent;
using System.Threading.Tasks;

class Program
{
    static ConcurrentStack<int> concurrentStack = new ConcurrentStack<int>();

    static void Main()
    {
        Parallel.For(0, 1000, i =>
        {
            concurrentStack.Push(i);
        });

        Console.WriteLine($"Total Items Pushed: {concurrentStack.Count}"); // Output: 1000

        int result;
        while(concurrentStack.TryPop(out result))
        {
            // Process result
        }
    }
}

11.2 Implementing Custom Stack Behavior

using System;
using System.Collections.Generic;

public class LimitedStack<T> : Stack<T>
{
    private int maxSize;

    public LimitedStack(int maxSize)
    {
        this.maxSize = maxSize;
    }

    public new void Push(T item)
    {
        base.Push(item);
        while(this.Count > maxSize)
        {
            this.Pop();
        }
    }
}

class Program
{
    static void Main()
    {
        LimitedStack<int> limitedStack = new LimitedStack<int>(3);
        limitedStack.Push(1);
        limitedStack.Push(2);
        limitedStack.Push(3);
        limitedStack.Push(4); // This will remove 1

        foreach(var item in limitedStack)
        {
            Console.WriteLine(item); // Outputs: 4, 3, 2
        }
    }
}

11.3 Serialization of Stacks

using System;
using System.Collections.Generic;
using System.Text.Json;

class Program
{
    static void Main()
    {
        Stack<string> fruitsStack = new Stack<string>();
        fruitsStack.Push("Apple");
        fruitsStack.Push("Banana");
        fruitsStack.Push("Cherry");

        string json = JsonSerializer.Serialize(fruitsStack);
        Console.WriteLine(json); // Output: ["Cherry","Banana","Apple"]

        // Deserialization
        Stack<string> deserializedStack = JsonSerializer.Deserialize<Stack<string>>(json);
        foreach(var fruit in deserializedStack)
        {
            Console.WriteLine(fruit);
        }
    }
}

Sample Output:
["Cherry","Banana","Apple"]
Cherry
Banana
Apple

12. Real-World Example

Example: Expression Evaluation Using Stack<T>

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string expression = "3 4 + 2 * 7 /"; // ((3 + 4) * 2) / 7
        double result = EvaluateRPN(expression);
        Console.WriteLine($"Expression: {expression}");
        Console.WriteLine($"Result: {result}"); // Output: 2
    }

    static double EvaluateRPN(string expr)
    {
        Stack<double> stack = new Stack<double>();
        string[] tokens = expr.Split(' ');

        foreach(var token in tokens)
        {
            if(double.TryParse(token, out double number))
            {
                stack.Push(number);
            }
            else
            {
                if(stack.Count < 2)
                    throw new ArgumentException("Invalid expression.");

                double b = stack.Pop();
                double a = stack.Pop();
                double res = 0;

                switch(token)
                {
                    case "+":
                        res = a + b;
                        break;
                    case "-":
                        res = a - b;
                        break;
                    case "*":
                        res = a * b;
                        break;
                    case "/":
                        res = a / b;
                        break;
                    default:
                        throw new ArgumentException($"Invalid operator: {token}");
                }

                stack.Push(res);
            }
        }

        if(stack.Count != 1)
            throw new ArgumentException("Invalid expression.");

        return stack.Pop();
    }
}

Sample Output:
Expression: 3 4 + 2 * 7 /
Result: 2

13. Summary