Stacks and their uses
Last in, first out: implement a stack on an array, check balanced brackets, build undo/redo, evaluate expressions and meet the monotonic stack pattern.
| Operation | Meaning | Cost |
|---|---|---|
Push(x) | O(1) amortised | |
Pop() | O(1) | |
Peek() | O(1) | |
Count | O(1) |
A stack is just an array with a top index
public class ArrayStack<T>{ private T[] _items = new T[4]; private int _count; // also the index of the next free slot public int Count => _count; public void Push(T item) { if (_count == _items.Length) Array.Resize(ref _items, _items.Length * 2); // double when full _items[_count++] = item; } public T Pop() { if (_count == 0) throw new InvalidOperationException("Stack is empty"); T item = _items[--_count]; _items[_count] = default!; // release the reference return item; } public T Peek() => _count > 0 ? _items[_count - 1] : throw new InvalidOperationException("Stack is empty");}Stack<T> works exactly like this.
Balanced brackets
(, [ and { is closed by the right partner in the right order. A stack makes this easy: push every opening bracket; on a closing bracket, the top of the stack must be its partner.
static bool IsBalanced(string code){ var stack = new Stack<char>(); foreach (char c in code) { switch (c) { case '(' or '[' or '{': stack.Push(c); break; case ')' or ']' or '}': char expected = c == ')' ? '(' : c == ']' ? '[' : '{'; if (!stack.TryPop(out char top) || top != expected) return false; // nothing open, or wrong partner break; } } return stack.Count == 0; // anything left was never closed} Console.WriteLine(IsBalanced("if (a[i] > 0) { f(x); }"));Console.WriteLine(IsBalanced("Math.Max(a[0], b[1)]"));True False
Undo and redo with two stacks
var undo = new Stack<string>();var redo = new Stack<string>(); void Do(string action) { undo.Push(action); redo.Clear(); Console.WriteLine($"do {action}"); }void Undo() { if (undo.TryPop(out var a)) { redo.Push(a); Console.WriteLine($"undo {a}"); } }void Redo() { if (redo.TryPop(out var a)) { undo.Push(a); Console.WriteLine($"redo {a}"); } } Do("move beam");Do("rotate column");Undo();Undo();Redo();do move beam do rotate column undo rotate column undo move beam redo move beam
Evaluating expressions
(3 + 4) * 2 into postfix form (3 4 + 2 *), where each operator comes after its two operands. Postfix needs no brackets and is evaluated with one stack: push numbers; for an operator, pop two numbers, apply it, push the result.
static double EvalPostfix(string expr){ var stack = new Stack<double>(); foreach (var token in expr.Split(' ', StringSplitOptions.RemoveEmptyEntries)) { if (double.TryParse(token, out double number)) { stack.Push(number); continue; } double right = stack.Pop(), left = stack.Pop(); // note the order! stack.Push(token switch { "+" => left + right, "-" => left - right, "*" => left * right, "/" => left / right, _ => throw new FormatException($"Unknown operator {token}") }); } return stack.Pop();} Console.WriteLine(EvalPostfix("3 4 + 2 *")); // (3 + 4) * 2Console.WriteLine(EvalPostfix("10 2 8 * + 3 -")); // 10 + 2 * 8 - 314 23
Pattern: the monotonic stack
static int[] NextGreater(int[] a){ var result = new int[a.Length]; Array.Fill(result, -1); var waiting = new Stack<int>(); // indexes, values decreasing from bottom to top for (int i = 0; i < a.Length; i++) { while (waiting.Count > 0 && a[waiting.Peek()] < a[i]) result[waiting.Pop()] = a[i]; // a[i] is the answer for everything smaller waiting.Push(i); } return result; // still waiting → no greater element (-1)} Console.WriteLine(string.Join(", ", NextGreater([2, 1, 5, 3, 6])));5, 5, 6, 6, -1
"abbaca" → remove bb → "aaca" → remove aa → "ca". Solve it in one O(n) pass with a stack.
Show a hint
Show the solution
static string RemoveDuplicates(string s){ var stack = new Stack<char>(); foreach (char c in s) { if (stack.Count > 0 && stack.Peek() == c) stack.Pop(); else stack.Push(c); } var chars = stack.ToArray(); // ToArray returns top first Array.Reverse(chars); return new string(chars);} Console.WriteLine(RemoveDuplicates("abbaca"));Console.WriteLine(RemoveDuplicates("azxxzy"));ca ay
Remember
A stack is LIFO: push and pop at the top, both O(1). It is just an array (or List) where you only use the end; .NET provides Stack<T>.Use a stack when the most recent unfinished thing must be handled first: brackets, undo, expressions, the call stack. A monotonic stack turns “next greater element” problems from O(n²) into O(n).