Using a Stack to Solve Problems in C#
We got a stack of reasons for needing to know Stacks.
Hello, .NET Digest readers! The stack is a fundamental data structure that’s both simple and powerful, making it a go-to tool for solving a wide range of programming problems. Whether you’re prepping for a coding interview or building efficient .NET applications, understanding how to leverage a stack in C# is a necessity. In this post, I’ll explain what a stack is, implement one in C#, and show how to use it to solve two classic interview problems: reversing a string and validating parentheses.
What Is a Stack?
A stack is a Last-In, First-Out (LIFO) data structure, meaning the last item added (pushed) is the first one removed (popped). Think of it like a stack of papers on your desk: you add papers to the top and take them off the top. In .NET, the Stack<T> class provides a built-in implementation, but we’ll also create a custom stack to understand its mechanics better.
Stacks are perfect for problems involving reversal, backtracking, or nested structures, such as:
Reversing data (e.g., strings, lists).
Parsing expressions (e.g., validating parentheses).
Depth-first search or undo/redo functionality.
Our goals:
Implement a custom stack in C#.
Use Stack<T> to solve two real interview problems.
Keep the code clear and reusable.
Step 1: Implementing a Custom Stack
Let’s start by building a simple generic stack using a list as the underlying storage. This will help us understand how stacks work before we use .NET’s Stack<T>. If you want to take this code and test it yourself, go to my GitHub where it is available for free (along with other .NET Digest code samples).
public class CustomStack<T>
{
private readonly List<T> items = new List<T>();
public void Push(T item)
{
items.Add(item);
}
public T Pop()
{
if (IsEmpty())
throw new InvalidOperationException("Stack is empty.");
T item = items[items.Count - 1];
items.RemoveAt(items.Count - 1);
return item;
}
public T Peek()
{
if (IsEmpty())
throw new InvalidOperationException("Stack is empty.");
return items[items.Count - 1];
}
public bool IsEmpty() => items.Count == 0;
public int Count => items.Count;
}This CustomStack<T> supports:
Push: Adds an item to the top.
Pop: Removes and returns the top item.
Peek: Returns the top item without removing it.
IsEmpty and Count: Check if the stack is empty or get its size.
While this works, .NET’s Stack<T> is optimized and thread-safe, so we’ll use it for the real problem-solving examples. Thankfully, in an interview, you won’t have to actually implement your own stack to solve the problems.
Step 2: Solving Problems with Stack<T>
Let’s use .NET’s Stack<T> to solve two common problems that showcase the stack’s utility.
Problem 1: Reversing a String
A stack’s LIFO nature makes it ideal for reversing data. This is a way to solve LeetCode problem 344: Reverse String (found here). Let’s write a method to reverse a string by pushing each character onto a stack and then popping them off.
public static string ReverseString(string input)
{
if (string.IsNullOrEmpty(input))
return input;
Stack<char> stack = new Stack<char>();
foreach (char c in input)
{
stack.Push(c);
}
char[] result = new char[input.Length];
for (int i = 0; i < result.Length; i++)
{
result[i] = stack.Pop();
}
return new string(result);
}How It Works:
Push each character onto the stack (e.g., “hello” becomes a stack with ‘o’ on top).
Pop characters to build the reversed string (“olleh”).
Time complexity: O(n), where n is the string length.
Problem 2: Validating Parent Parentheses
Stacks are great for checking if parentheses in an expression are balanced (e.g., “{()}” is valid, but “{(}” is not). We’ll use a stack to track opening brackets and ensure they match closing brackets. Check out LeetCode problem 20: Valid Parentheses that asks this same question (found here).
public static bool IsValidParentheses(string input)
{
Stack<char> stack = new Stack<char>();
foreach (char c in input)
{
if (c == '(' || c == '{' || c == '[')
{
stack.Push(c);
}
else if (c == ')' || c == '}' || c == ']')
{
if (stack.Count == 0)
return false;
char top = stack.Pop();
if (!IsMatchingPair(top, c))
return false;
}
}
return stack.Count == 0;
}
private static bool IsMatchingPair(char open, char close)
{
return (open == '(' && close == ')') ||
(open == '{' && close == '}') ||
(open == '[' && close == ']');
}How It Works:
Push opening brackets onto the stack.
For each closing bracket, pop the top opening bracket and check if they match.
The expression is valid if the stack is empty at the end and all pairs match.
Time complexity: O(n), where n is the string length.
Step 3: Testing the Solutions
Let’s test both methods in a console app to see the stack in action.
using System;
class Program
{
static void Main()
{
// Test string reversal
string input = "Hello, .NET!";
string reversed = ReverseString(input);
Console.WriteLine($"Original: {input}");
Console.WriteLine($"Reversed: {reversed}");
// Test parentheses validation
string[] expressions = { "{()}", "{(})", "((()))", "({[]})" };
foreach (string expr in expressions)
{
bool isValid = IsValidParentheses(expr);
Console.WriteLine($"Expression '{expr}' is {(isValid ? "valid" : "invalid")}");
}
}
}Expected output:
Original: Hello, .NET!
Reversed: !TEN. ,olleH
Expression '{()}' is valid
Expression '{(})' is invalid
Expression '((()))' is valid
Expression '({[]})' is validThe first example reverses the string, and the second checks parentheses, demonstrating the stack’s versatility.
Tips for Using Stacks Effectively
Use .NET’s Stack<T>: It’s optimized and handles edge cases like empty stacks gracefully.
Watch for emptiness: Always check Count or try-catch to avoid the InvalidOperationException when popping or peeking.
Interview prep: Be ready to solve stack-based problems like evaluating postfix expressions or implementing a browser’s back/forward navigation.
Real-world use: Stacks are great for undo/redo features, parsing XML/JSON, or depth-first search in graphs.
Wrapping Up
Stacks are a simple yet powerful tool for solving problems in C#. Whether you’re reversing data or validating nested structures, the LIFO principle makes complex tasks manageable. The examples above, reversing a string and checking parentheses, are just the start. Try extending them to handle more complex inputs or explore other stack-based problems like the Min Stack.
For interview prep, practice explaining how a stack works and its time complexity. For .NET projects, consider using Stack<T> for features like command history or recursive algorithm simulation. I hope this post helps you see the stack’s potential! Happy coding guys!