C# Stacks

Introduction

A stack is a special type of collection that stores elements in a Last-In-First-Out (LIFO) manner. Think of it like a stack of plates: the last plate you put on top is the first one you take off. In C#, the Stack<T> class represents this data structure and is part of the System.Collections.Generic namespace.

Stacks are particularly useful when you need to:

• Process items in reverse order
• Remember a series of operations that might need to be undone
• Keep track of a path or sequence where you need to "backtrack"

Basic Stack Operations

There are three primary operations you can perform with a stack:

1. Push - Add an element to the top of the stack
2. Pop - Remove and return the element from the top of the stack
3. Peek - View the top element without removing it

Let's see how these operations work in C#:

csharp

using System;
using System.Collections.Generic;

// Creating a new stack
Stack<string> bookStack = new Stack<string>();

// Adding elements using Push
bookStack.Push("Book 1");
bookStack.Push("Book 2");
bookStack.Push("Book 3");

// Viewing the top element using Peek
Console.WriteLine("Top book: " + bookStack.Peek());
// Output: Top book: Book 3

// Removing elements using Pop
Console.WriteLine("Taking book: " + bookStack.Pop());
// Output: Taking book: Book 3

Console.WriteLine("Now the top book is: " + bookStack.Peek());
// Output: Now the top book is: Book 2

// Number of books in stack
Console.WriteLine("Number of books: " + bookStack.Count);
// Output: Number of books: 2

Creating and Initializing a Stack

You can create a stack in a few different ways:

csharp

// Empty stack
Stack<int> numbers = new Stack<int>();

// Stack with initial capacity
Stack<int> numbersWithCapacity = new Stack<int>(10);

// Stack initialized with elements from another collection
List<int> numberList = new List<int> { 1, 2, 3, 4, 5 };
Stack<int> numbersFromList = new Stack<int>(numberList);

// Note: When initializing from a collection, the elements are pushed
// in the order they are enumerated, so the top of the stack will be
// the last element in the source collection
Console.WriteLine(numbersFromList.Pop()); // Output: 5
Console.WriteLine(numbersFromList.Pop()); // Output: 4

Working with Stacks

Checking if an Element Exists in a Stack

csharp

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

// Check if the stack contains an element
bool hasApple = fruitStack.Contains("Apple");
Console.WriteLine("Stack contains Apple: " + hasApple); 
// Output: Stack contains Apple: True

Converting a Stack to Other Collections

csharp

Stack<int> myStack = new Stack<int>();
myStack.Push(10);
myStack.Push(20);
myStack.Push(30);

// Convert stack to array
int[] myArray = myStack.ToArray();
Console.WriteLine("First element in array: " + myArray[0]);
// Output: First element in array: 30

// Convert stack to list
List<int> myList = new List<int>(myStack);

Clearing a Stack

csharp

Stack<double> prices = new Stack<double>();
prices.Push(10.99);
prices.Push(5.49);
prices.Push(8.75);

Console.WriteLine("Number of prices: " + prices.Count);
// Output: Number of prices: 3

// Clear all elements
prices.Clear();
Console.WriteLine("Number of prices after clearing: " + prices.Count);
// Output: Number of prices after clearing: 0

Iterating Through a Stack

When you iterate through a stack, you go from the top (most recently added) to the bottom:

csharp

Stack<string> cards = new Stack<string>();
cards.Push("Ace of Spades");
cards.Push("King of Hearts");
cards.Push("Queen of Diamonds");

Console.WriteLine("Cards from top to bottom:");
foreach (var card in cards)
{
    Console.WriteLine(card);
}

// Output:
// Cards from top to bottom:
// Queen of Diamonds
// King of Hearts
// Ace of Spades

Practical Applications of Stacks

Example 1: Reversing a String

csharp

static string ReverseString(string input)
{
    Stack<char> charStack = new Stack<char>();
    
    // Push each character onto the stack
    foreach (char c in input)
    {
        charStack.Push(c);
    }
    
    // Build the reversed string
    string reversed = string.Empty;
    while (charStack.Count > 0)
    {
        reversed += charStack.Pop();
    }
    
    return reversed;
}

// Example usage
string original = "Hello World!";
string reversed = ReverseString(original);
Console.WriteLine($"Original: {original}");
Console.WriteLine($"Reversed: {reversed}");

// Output:
// Original: Hello World!
// Reversed: !dlroW olleH

Example 2: Checking Balanced Parentheses

csharp

static bool AreParenthesesBalanced(string expression)
{
    Stack<char> parenthesesStack = new Stack<char>();
    
    foreach (char c in expression)
    {
        if (c == '(' || c == '[' || c == '{')
        {
            parenthesesStack.Push(c);
        }
        else if (c == ')' || c == ']' || c == '}')
        {
            if (parenthesesStack.Count == 0)
            {
                return false;
            }
            
            char top = parenthesesStack.Pop();
            
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{'))
            {
                return false;
            }
        }
    }
    
    return parenthesesStack.Count == 0;
}

// Example usage
string expr1 = "{[()]}";
string expr2 = "{[(])}";
Console.WriteLine($"'{expr1}' is balanced: {AreParenthesesBalanced(expr1)}");
Console.WriteLine($"'{expr2}' is balanced: {AreParenthesesBalanced(expr2)}");

// Output:
// '{[()]}' is balanced: True
// '{[(])}' is balanced: False

Example 3: Implementing Undo Functionality

csharp

class TextEditor
{
    private string _currentText = "";
    private Stack<string> _undoStack = new Stack<string>();
    
    public void AddText(string text)
    {
        _undoStack.Push(_currentText);
        _currentText += text;
    }
    
    public bool Undo()
    {
        if (_undoStack.Count > 0)
        {
            _currentText = _undoStack.Pop();
            return true;
        }
        return false;
    }
    
    public string GetText()
    {
        return _currentText;
    }
}

// Example usage
TextEditor editor = new TextEditor();
editor.AddText("Hello ");
editor.AddText("World!");
Console.WriteLine("Current text: " + editor.GetText());

editor.Undo();
Console.WriteLine("After undo: " + editor.GetText());

editor.Undo();
Console.WriteLine("After another undo: " + editor.GetText());

// Output:
// Current text: Hello World!
// After undo: Hello 
// After another undo: 

Stack vs. Other Collections

Here's a quick comparison of stacks with other collection types:

Collection	Access Pattern	Use When
Stack	Last-In-First-Out (LIFO)	You need to process items in reverse order
Queue	First-In-First-Out (FIFO)	You need to process items in order they were added
List	Random access by index	You need arbitrary access to elements
Dictionary	Key-value lookup	You need to find values using unique keys

Performance Considerations

• Most stack operations (Push, Pop, Peek) are O(1) - constant time
• Searching with Contains is O(n) as it may need to check each element
• Stacks in C# are implemented as arrays internally, which might be resized when capacity is exceeded
• If you know the approximate size in advance, set the initial capacity for better performance

Summary

The Stack<T> collection in C# provides an efficient way to store and retrieve data in a Last-In-First-Out (LIFO) manner. We've learned:

• How to create and initialize stacks
• Basic operations like Push, Pop, and Peek
• How to check for elements and clear a stack
• Iterating through stack elements
• Practical applications like string reversing, parentheses checking, and undo functionality

Stacks are an essential data structure in programming and understanding them will help you solve many real-world problems more efficiently.

Exercises

1. Write a program that uses a stack to determine if a word is a palindrome
2. Implement a postfix calculator using a stack (e.g., evaluate "3 4 + 5 *")
3. Create a browser history functionality where you can navigate back using a stack
4. Write a function that sorts a stack without using any other data structure
5. Implement a stack that also keeps track of the minimum element

Additional Resources

• Microsoft Documentation on Stack<T>
• Stack Data Structure on Wikipedia
• Common Stack-based Algorithms