Stack<T> is the generic last-in-first-out (LIFO) collection in the BCL. The _Queue<T>_ lesson covered Queue<T>, which works first-in-first-out. A stack flips that rule: the item you added most recently is the one that comes out first. It lives in System.Collections.Generic and is the data structure you reach for when "most recent" matters, like an undo history, a depth-first traversal, or evaluating a reverse-Polish expression.

The mental model for a stack is a pile of plates on a counter. You place a new plate on the top of the pile, and you take a plate off the top. You never reach into the middle. Whatever you put on last comes off first. That's the rule, and the entire API is shaped around it.

Stack<T> exposes exactly two mutating primitives that match this rule: Push to add to the top, and Pop to remove from the top. There's also Peek to look at the top without removing it. The collection still has the usual conveniences (Count, Contains, Clear, enumeration), but those don't change the LIFO shape, they just give you ways to inspect what's there.

Three actions go in. The most recent (Applied Coupon) sits on top. Peek reads it without changing anything, then Pop removes and returns it. After the pop, Added Headphones is the new top because it was the second most recent. The count drops from three to two.

This is the running example we'll use through the lesson: an undo stack for cart actions in an e-commerce app. Every time the shopper does something (add an item, change a quantity, apply a coupon), the action is pushed on the stack. Hitting "undo" pops the top action and reverses it. The stack remembers the recent history, and LIFO order matches what the user expects.

Here's the LIFO operation laid out visually. Three items get pushed, one at a time, and then one gets popped. Notice how the "top" pointer always points to the most recently pushed item, and a pop returns exactly that item.

Each push grows the stack from the top. The pop pulls from the same end. The bottom of the stack (the oldest item) never moves until everything above it has been popped first. That's the entire mental model. Every other API on Stack<T> is built around respecting it.

The contrast with Queue<T> is useful to keep in mind. A queue is FIFO: items leave in the order they arrived. A stack is LIFO: items leave in reverse arrival order. Same enqueue/push semantics on input, opposite ordering on output. Picking the right one is almost always a question of which order the consumer needs, not how items were produced.

Stack<T> has three constructors that cover most needs. The default constructor gives you an empty stack with a small starting capacity. The integer constructor lets you preallocate when you know roughly how many items you'll hold. And the IEnumerable<T> constructor copies an existing sequence into the new stack.

The first two are straightforward. The default constructor builds an empty stack. The capacity constructor also builds an empty stack but tells the underlying array to start at a specific size, so the first many pushes don't trigger a resize. The capacity is a hint for the array, not a limit on how many items you can store. The stack will grow past it if needed.

The third constructor is where the surprise lives. When you pass an IEnumerable<T>, Stack<T> walks the sequence and pushes each item one at a time. That means the last item in the source becomes the top of the stack, and iteration order on the new stack is the reverse of the source.

The source array is in the order the actions happened. After feeding it into the stack constructor, popping returns the actions in reverse. That's exactly what you want for undo: the most recent action comes out first. If you were tempted to think of the source as "the bottom of the stack going up," the output confirms it. The first source element ends up at the bottom; the last ends up on top.

The capacity constructor matters when you have a reasonable upper bound and want to skip resize work. The internal array doubles when it fills up, and each doubling copies every existing element to a new array. If you'll push around 100 items, starting at capacity 128 avoids three or four doublings on the way there.

A thousand pushes fit comfortably in the preallocated array with no resizes. The top is 999 because that was the last value pushed. Counting goes 0, 1, 2, ..., 999, and 999 lands on top by LIFO rule.

If you don't know the size in advance, don't bother. Default construction is fine. The doubling growth policy means even a hundred million pushes only triggers around twenty-seven resizes, and each is O(n) on the current size, so the amortized cost per push is still O(1). The preallocation trick is for hot paths and benchmarks, not everyday use.

Push adds an item to the top of the stack. Pop removes and returns the top item. Both work in O(1) amortized time, which is the main reason stacks are fast. There's no shifting, no search, no comparisons. The implementation maintains an internal array and a count, and these operations only touch the slot at index count - 1.

Three pushes leave the stack with Applied Coupon 10OFF on top, Added Headphones in the middle, and Added Book at the bottom. Each Pop peels off the current top. After two pops, the bottom item is now the only one left, and it's also the top by default (a one-item stack has its lone element at both ends).

The behavior people get wrong on the first try is Pop on an empty stack. It does not return default(T). It does not return null. It throws.

Pop on an empty stack throws InvalidOperationException with the message Stack empty.. The same is true for Peek. Both of them treat "there's nothing on top" as a programming bug rather than a state to fall through silently, because returning a sentinel like default(T) would force every caller to distinguish "the item was 0" from "the stack was empty." Throwing forces the caller to check Count first or to use TryPop / TryPeek (covered shortly).

When you push enough items to exceed the current capacity, the stack grows. The internal array doubles in size, every existing element is copied to the new array, and the new push lands in the next slot. The cost of a single push is therefore O(1) most of the time, with the occasional O(n) when a resize happens. Averaged over many pushes, that comes out to O(1) per push, which is what "amortized O(1)" means.

Even though the initial capacity was 4, the fifth push triggers an internal resize (the array doubles to 8) and the push succeeds. The Count goes up by one each time. From the caller's point of view there's no visible difference between a "fast" push and a "resize then push" push. The doubling is hidden behind the API.

You don't get to see the capacity directly from Stack<T>. Unlike List<T>.Capacity, there's no public property. You can call TrimExcess to shrink the internal array down to match the current Count, which is useful for long-lived stacks that grew large and then drained.

The trim doesn't change the count, only the internal capacity. After pushing 1000 and popping back down to 10, the internal array is still at least 1024 entries long (the next power of two past 1000) and most of it is wasted. TrimExcess reallocates to a tighter array, freeing the empty tail. Use it sparingly. It's a copy, not a free operation, and most short-lived stacks won't need it.

When "the stack might be empty" is a normal state (not a bug), the pair TryPop and TryPeek is the right tool. They return a bool to signal success and use an out parameter for the value. No exception is thrown either way.

The first call returns false. Because the method returned false, the action variable is set to default(string), which is null, but the code never reads it. That's the discipline: only touch the out value when the method returned true. The second call returns true because the stack now has one item, and action is set to "Added Book".

TryPop removes the top and gives it to you. TryPeek reads the top without removing it. Both follow the same pattern: bool return value, out T result.

TryPeek reads 20 and leaves the count at 2. The first TryPop returns 20 and drops the count to 1. The second TryPop returns 10 and the stack is now empty. The third call returns false, and the out variable gone is set to default(int), which is 0. The if (!stack.TryPop(...)) guard is what tells us we shouldn't trust gone as a real value.

The choice between Pop and TryPop is mostly a question of who's responsible for the empty case. If the contract of the surrounding code says "the stack is never empty when we get here," Pop is fine and an exception would correctly flag a violated assumption. If the contract says "maybe the stack is empty, that's normal," TryPop is cleaner because it doesn't use control flow as exception flow.

The draining-loop pattern is worth highlighting. It comes up everywhere a stack is the data structure for an algorithm.

The while loop calls TryPop once per iteration. As long as the stack has something, the call returns true, action is set to the top, and the loop body runs. When the stack is empty, TryPop returns false, the loop exits, and execution continues below. No Count check, no exception. Compare this to a hand-rolled version with Count > 0 and Pop, which works but has more moving parts.

TryPop and TryPeek were added in .NET Core 2.0 and are part of .NET 8. Earlier versions only had Pop and Peek with the throwing behavior. If you're maintaining old code that pre-dates them, you'll see the Count > 0 pattern. New code should prefer the Try variants when "empty is normal."

Peek is the read-only sibling of Pop. It returns the top item without removing it. Same throwing behavior on an empty stack, same O(1) cost.

Two peeks in a row return the same value and the count never changes. The top of the stack is observable but untouched. This matters when an algorithm needs to make a decision based on what's on top before deciding whether to pop or push something else. Parsing and expression evaluation lean on this constantly.

A common shape is "check the top, then decide what to do." For balanced-parentheses checking, for example, you peek at the top before popping, to see if the opener matches the closer you're processing. We'll write that algorithm out in the exercises.

When the stack is empty, Peek throws the same InvalidOperationException as Pop. Same fix: check Count > 0 first or use TryPeek.

The "look without removing" semantics of Peek are part of what makes a stack expressive. You can use it as a one-step lookahead, decide whether the current state matches what you expect, and only commit to a Pop if it does. Without Peek you'd have to pop and push the item back, which works but obscures the intent.

Iterating a Stack<T> with foreach walks the items from top to bottom without removing them. That is, the first item the enumerator yields is the one a Pop would return, and the last item yielded is the one at the bottom of the stack.

This trips up readers who expect iteration to follow insertion order. It doesn't. The order is reversed, because the stack is logically a LIFO collection and the "natural" walk is from the most recent to the oldest.

The pushes happened in the order Book, Headphones, Coupon. The iteration prints them in the order Coupon, Headphones, Book, which is the reverse of insertion and the same as the order Pop would produce. The count is still 3 after the loop, because foreach doesn't mutate the stack, it just reads it.

You can think of foreach over a stack as "what would I see if I popped everything, but I don't actually want to pop." Same order, no mutation. This is occasionally exactly what you want (for example, "print the undo history with the most recent action first") and occasionally not what you want (if you wanted insertion order, the stack is the wrong collection or you need a different traversal).

The same is true for ToArray. Calling stack.ToArray() returns an array whose index 0 is the top of the stack and whose last index is the bottom.

ToArray matches iteration order, which matches pop order, which is reverse insertion order. If you need insertion order, you have to reverse the array (Array.Reverse(arr)) or build the stack from a reversed source in the first place. There's no ToArrayInInsertionOrder method.

The next code example shows the subtlety side by side. The same items are pushed onto two stacks; one is iterated, the other is fed into a fresh stack via the IEnumerable<T> constructor. The results show how iteration order interacts with reconstruction.

Read this carefully. The original stack iterates top first, so it prints C, B, A. When you build copy from original, the constructor pushes each item from the source in iteration order: first C, then B, then A. After those three pushes, A is on top (it was pushed last). Iterating copy therefore prints A, B, C.

The takeaway is that round-tripping a stack through its IEnumerable<T> constructor reverses it. To produce a true clone with the same top, you need an extra step: build an intermediate collection, reverse it, and then push. Or use ToArray and then construct from Array.Reverse(arr). Or copy through Stack<T>(Stack<T>)... which doesn't exist as a direct constructor, you have to go through IEnumerable<T>.

Reversing the original before feeding it into the constructor puts the bottom of the original (A) first in the iteration. The constructor pushes A, then B, then C, so C ends up on top of the clone, matching the original. Now clone.Peek() returns the same value as original.Peek(). This is the idiomatic "clone a stack" pattern when the order has to match.

The three "everyday" operations on the rest of the stack: Count for size, Contains for membership, and Clear to wipe it out.

Count is a property and returns the current number of items in O(1). It works on an empty stack (returns 0) and never throws.

Use Count whenever you'd otherwise be tempted to write stack.ToArray().Length. The property is O(1) and doesn't allocate. The ToArray approach is O(n) and allocates a fresh array just to read its length.

Contains walks the internal array looking for an element equal to the argument. Equality is decided by EqualityComparer<T>.Default, which means Equals and GetHashCode for reference types and value equality for built-in value types. It returns as soon as it finds a match and is O(n) in the worst case.

The search walks the array in iteration order (top to bottom). For a small stack it doesn't matter, but if you're calling Contains frequently on a large stack, it's a sign that the stack isn't the right data structure. A HashSet<T> gives you O(1) membership tests. A stack is for ordered access, not for lookups.

Clear removes every item. The count goes to zero, the internal array is reset (slots are set to default(T) so the garbage collector can reclaim referenced objects), and the capacity is preserved. It's O(n) because it has to clear the array slots.

Clear leaves the stack ready for reuse. You don't have to throw away the object and allocate a new one to reset it. For long-lived stacks that go through cycles of fill and drain, calling Clear and continuing to push is cheaper than allocating a new stack each time.

If T is a reference type, Clear matters for memory. Without it, the internal array might still hold references to objects you've logically removed (with Pop, the slot is cleared, but if you stopped popping partway, the slots still hold references). Clear walks the live portion and nulls everything out so the GC can collect those objects.

Stack<T> is implemented as a dynamic array with a count. There's no linked list, no node allocation per push, no random pointers. The implementation looks roughly like this:

That's the shape. The real BCL implementation has more (a version counter for enumeration safety, optimized resize paths, an IEnumerator struct), but the storage model is exactly this: one array, one count. The top of the stack is always at index _size - 1 in the array. A push writes the new value at _array[_size] and increments the count. A pop reads _array[_size - 1], decrements the count, and (for reference types) clears the slot.

This matters for two reasons. First, it tells you why the operations are O(1). There's no list traversal, no node allocation, just an indexed write or read. Second, it tells you why iteration matches reverse insertion order. The enumerator walks the array from _size - 1 down to 0, so the first item you see is the most recently pushed.

Here's the array layout for a stack with three items.

Slots 0, 1, 2 hold the items A, B, C (in push order). The top of the stack is C, sitting at index _size - 1 = 2. Slots 3 through 7 are unused but allocated. A push writes into slot 3 and bumps _size to 4. A pop reads slot 2, clears it, and drops _size to 2, leaving B as the new top.

When _size reaches the array length, the next push triggers a resize. A new array twice the size is allocated, the existing items are copied over, and the old array becomes garbage. This is the only place where push isn't strictly O(1), and it's the source of the "amortized" qualifier.

The doubling policy is what makes amortized O(1) work. If the array doubled by only one each time, you'd copy n items per push and the amortized cost would be O(n). Doubling means that for every push that costs O(n), there are roughly n previous cheap pushes. Spread the expensive work over those cheap ones and the average comes out to O(1).

A common follow-up question in interviews is "why double instead of grow by 50% or 25%?" The short answer is that any constant multiplier produces amortized O(1). Doubling is the .NET BCL's choice (and the choice of most languages' default growable arrays); it tends to waste less memory than a 4x policy and trigger fewer resizes than a 25% policy. The specific multiplier varies by language and library, but the asymptotic answer is the same.

Stacks are everywhere in computing, but a few patterns dominate.

Undo and Redo. Every action the user takes is pushed onto an undo stack. Hitting undo pops the top action and reverses it. To support redo, you keep a second stack: when you pop from the undo stack, you push the reversed-or-not action onto the redo stack. Hitting redo pops from the redo stack and re-applies. This pairs perfectly with LIFO because the most recent action is always the most relevant to undo.

Two stacks, one for actions that can be undone, one for actions that can be redone. The Do method clears the redo stack because a fresh action invalidates any future history (this is how every text editor in the world behaves). The Undo and Redo methods pop from one stack and push onto the other, preserving the LIFO ordering on both sides.

Depth-first traversal. When you walk a tree or graph and want to go deep before going wide, a stack is the natural data structure. Push the starting node, then in a loop pop a node, visit it, and push its unvisited neighbors. The stack remembers which branches you haven't explored yet, in LIFO order so the most recently discovered branch is the next one explored. (BFS uses a Queue<T> instead, for the opposite reason.)

The DFS walks the category tree starting at the root. The traversal order depends on the order children are pushed. Here, Electronics is pushed before Books, so Books ends up on top of Electronics and gets popped first. Each category's children are pushed in their declared order, and again the last one pushed becomes the top, so they come out in reverse. (To visit children in declared order, push them in reverse using stack.Push(node.Subcategories[i]) for i from Count - 1 down to 0.)

The mental model: the stack holds "nodes I've discovered but haven't visited yet." Popping a node means "I'm visiting this one now." Pushing its children means "and now I have these new nodes to visit later." LIFO ensures depth-first; FIFO (a queue) would give breadth-first.

Expression evaluation (Reverse Polish Notation). RPN puts operators after their operands. The expression (3 + 4) * 5 becomes 3 4 + 5 * in RPN. A stack evaluates it cleanly: push numbers, and when you hit an operator, pop the right number of operands, compute, and push the result.

Each token is either a number (pushed) or an operator (which pops two values, applies the op, and pushes the result). The order of the pops matters: the right operand was pushed last, so it comes off the top first. After processing every token, the stack holds exactly one number, which is the final answer. If it didn't, the expression was malformed.

The RPN evaluator is short and direct because the stack handles all the "remembering" for us. Without a stack you'd need explicit recursion or a tree-walking interpreter, both of which are more code. The stack reduces a recursive structure (an expression tree) to a linear scan.

Parser backtracking. Recursive-descent parsers, regex engines, and AI planners all use stacks to remember "where I was so I can return to it if the current path fails." Pushing a save point and popping it on backtrack is the same shape as undo. The stack frames in a function call work this way at the language level (we'll see that in a moment).

Call stack simulation. Recursive algorithms can always be rewritten iteratively with an explicit stack, swapping language-managed recursion for a data structure you control. The benefit is that you avoid stack overflow for deep recursion, and you can pause and resume the traversal. The cost is that the code is less compact because you do explicitly what the language was doing implicitly.

This is a deliberately small example. Real call-stack-simulation use cases include tree walkers for very deep trees (where recursion would blow the .NET stack) and state-machine engines that need to checkpoint progress. The pattern is always the same: push work items, pop them in LIFO order, push new work discovered during the pop.

Stack<T> is not thread-safe. Multiple threads reading concurrently is fine, but a writer mixed with readers or other writers can corrupt the count, the array, or both. The behavior under contention is undefined: you might see torn writes, missed updates, or IndexOutOfRangeException from the iterator.

For concurrent access, System.Collections.Concurrent.ConcurrentStack<T> provides a thread-safe alternative with TryPush, TryPop, and TryPeek designed for multi-threaded use. The _Concurrent Collections_ lesson covers it in depth.

For an unchangeable stack (where every "modification" returns a new stack rather than mutating in place), System.Collections.Immutable.ImmutableStack<T> is the right tool. It uses persistent data-structure tricks so that adding or removing an item doesn't copy the whole stack. The _Immutable Collections_ lesson covers it.

For the rest of this lesson, assume single-threaded access with Stack<T>. That's the common case, and it's what 95% of "I need a stack" situations need.