What a stack is
A stack is a collection where the last item added is the first item taken out. This rule is called LIFO, for last in, first out. The picture to keep in mind is a pile of plates: you put a plate on top, and you take a plate from the top. Reaching for a plate in the middle is not part of the deal.
A stack supports a small set of operations, and each one works on the top:
- Push adds an item to the top.
- Pop removes the top item and gives it back.
- Peek gives back the top item without removing it.
- Count tells you how many items the stack holds, so you can tell whether it is empty.
This narrow interface is useful because many problems have a "most recent unfinished thing" in them. An opening bracket waits for its closing bracket, and the latest one is always the first to be closed. A number waits for a bigger number to its right. A nested expression is finished from the inside out. In each case, a stack remembers what is still waiting, with the newest item ready on top.
Using Stack<T> in C#
C# provides the generic class Stack<T>. It lives in the System.Collections.Generic namespace, and T is the type of the items. Use Stack<int> for integers, Stack<char> for characters, and so on.
Stack<int> stack = new Stack<int>();
stack.Push(1);
stack.Push(2);
stack.Push(3);
Console.WriteLine(stack.Peek()); // 3
Console.WriteLine(stack.Count); // 3
Console.WriteLine(stack.Pop()); // 3
Console.WriteLine(stack.Pop()); // 2
Console.WriteLine(stack.Count); // 1
The value pushed last, 3, is on top, so it is the first one that Peek reports and Pop returns. After two pops, only 1 remains.
Notice that Count is a property, so it has no parentheses, while Push, Pop and Peek are methods. A new stack starts empty, and it grows as needed. Unlike an array, you never declare its size.
Empty stacks
Calling Pop() or Peek() on an empty stack throws an InvalidOperationException whose message is "Stack empty." The usual fix is to check Count first:
if (stack.Count > 0) {
int top = stack.Pop();
}
In current C#, TryPop and TryPeek do the check and the operation together. They return true or false and hand the value back through an out parameter:
Stack<int> empty = new Stack<int>();
bool ok = empty.TryPop(out int value);
Console.WriteLine(ok); // False
Console.WriteLine(value); // 0
When the stack is empty, value holds the default for the type, here 0. Look at ok before you use it.
Other members
Contains(x)reports whether a value is present. It scans the stack, so it takes time proportional to the size.Clear()removes everything, so the same stack object can be reused.ToArray()copies the items into an array, top first. For a stack that received 1, 2, 3 in that order, it gives[3, 2, 1].foreachvisits the items from the top down without removing them. The same stack prints 3, 2, 1.- The constructor
new Stack<int>(new[] { 1, 2, 3 })pushes the items in order, so 3 ends up on top.
A first example: reversing a string
A stack hands items back in the opposite order from how they arrived, which makes reversal a natural fit. Push every character of a word, then pop them all:
Stack<char> letters = new Stack<char>();
foreach (char c in "stack") {
letters.Push(c);
}
string reversed = "";
while (letters.Count > 0) {
reversed += letters.Pop();
}
Console.WriteLine(reversed); // kcats
The loop condition letters.Count > 0 is the standard way to drain a stack. It is also the guard that keeps Pop() from being called on an empty stack.
How fast is a stack?
All of the basic operations, Push, Pop, Peek and Count, take constant time, O(1). Push is constant on average: the stack keeps its items in an array that is replaced by a bigger one now and then, and that rare copy is spread across many pushes. This matters in the next lessons, where a loop does a push and a pop for every element. As long as each element is pushed once and popped at most once, the whole loop is O(n), even when it contains an inner while loop that pops several items.
Common mistakes
- Popping an empty stack. Check
Countfirst, or useTryPop. This is the most common runtime error with stacks. - Using
Peekwhen you wantedPop.Peekleaves the item in place, so a loop that only peeks can run forever. - Expecting insertion order from
foreachorToArray. Both start at the top, so the newest item comes first. - Using
LengthorSize. A stack hasCount.Lengthbelongs to arrays and strings. - Forgetting the generic type. Write
Stack<int>, not a bareStack. A non-genericStackclass still exists in the olderSystem.Collectionsnamespace, but it stores plain objects, so new code should use the generic one.
How the chapter uses stacks
The lessons that follow use the same pattern in different forms. A stack of opening brackets checks that every bracket is closed in the right order. A stack of indices finds, for each number, the first greater number to its right. The same idea finds the nearest lower bar for each bar of a histogram. A list of strings used as a stack reverses the text inside nested parentheses. In each case you push what is waiting and pop it when the answer arrives.
Key takeaways
- A stack is last in, first out. Everything happens at the top.
- In C#, use
Stack<T>withPush,Pop,Peekand theCountproperty. PopandPeekthrow on an empty stack, so checkCountor useTryPopandTryPeek.- Every basic operation is
O(1), which makes stack-based loops linear when each item is pushed and popped once. - Reach for a stack when the most recent unfinished item is the one you need next.