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 added most recently comes out first. It lives in System.Collections.Generic and is the data structure to use when "most recent" matters, like an undo history, a depth-first traversal, or evaluating a reverse-Polish expression.

A stack is like a pile of plates on a counter. A new plate goes on the top of the pile, and a plate comes off the top. Nothing reaches into the middle. Whatever goes on last comes off first. That's the rule, and the entire API is shaped around it.

Stack<T> exposes 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 has the usual conveniences (Count, Contains, Clear, enumeration), but those don't change the LIFO shape, they just allow inspecting 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 used 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.

A LIFO operation laid out visually. Three items get pushed, one at a time, and then one gets popped. 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. Every other API on Stack<T> is built around respecting this.

The contrast with Queue<T> is useful. 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 builds an empty stack with a small starting capacity. The integer constructor preallocates when the approximate item count is known. 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 the maximum item count. The stack grows past it if needed.

The third constructor has a noteworthy behavior. When passed 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 the right behavior for undo: the most recent action comes out first. The first source element ends up at the bottom; the last ends up on top.

The IEnumerable<T> constructor is O(n). It also allocates an internal array sized for the source (or larger). For a hot path that builds many short-lived stacks, prefer pushing only what's needed rather than rebuilding from a temporary collection.

The capacity constructor matters with a known upper bound, skipping resize work. The internal array doubles when it fills up, and each doubling copies every existing element to a new array. To 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 the size isn't known in advance, 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 pattern 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 (a one-item stack has its lone element at both ends).

One behavior to know: 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 ignore, 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).

Throwing an exception is expensive (the runtime captures a stack trace, walks frames, and unwinds). For code that pops in a loop and needs to handle "no more items," prefer checking Count > 0 or using TryPop. Driving a loop with try-catch around Pop works but burns cycles on the exception path.

When pushes 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.

The capacity isn't visible from Stack<T>. Unlike List<T>.Capacity, there's no public property. TrimExcess shrinks the internal array down to match the current Count, 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 fits. 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. 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 returns it. 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 signals that gone isn't 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 correctly flags 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.

TryPop and TryPeek have the same O(1) cost as their throwing counterparts on the success path, and they're cheaper on the empty path because there's no exception machinery. For loops that drain a stack down to zero, while (stack.TryPop(out var item)) is the idiomatic shape.

The draining-loop pattern 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. Compared to a hand-rolled version with Count > 0 and Pop, this has fewer 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. Old code pre-dating them uses 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, peek at the top before popping to see if the opener matches the closer being processed. The exercises develop that algorithm.

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. Use it as a one-step lookahead, decide whether the current state matches the expected one, and only commit to a Pop if it does. Without Peek the alternative is 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.

A common surprise: iteration doesn't follow insertion order. 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 reads it.

Think of foreach over a stack as "what would I see if I popped everything, without actually popping." Same order, no mutation. This fits "print the undo history with the most recent action first." For insertion order, the stack is the wrong collection or a different traversal is needed.

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. For insertion order, 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. Building copy from original makes the constructor push 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: round-tripping a stack through its IEnumerable<T> constructor reverses it. To produce a true clone with the same top, an extra step is needed: build an intermediate collection, reverse it, and then push. Or use ToArray and then construct from Array.Reverse(arr). There's no direct Stack<T>(Stack<T>) constructor; everything goes 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.

Both ToArray() and the IEnumerable<T> constructor are O(n) in time and space. They don't share memory with the stack's internal array, so mutating the array doesn't affect the stack and vice versa.

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 instead of stack.ToArray().Length. The property is O(1) and doesn't allocate. The ToArray approach is O(n) and allocates a fresh array 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 frequent Contains calls on a large stack signal a mismatch between data structure and access pattern. A HashSet<T> provides O(1) membership tests. A stack is for ordered access, not for lookups.

Contains is O(n). If membership tests are common, the data structure is probably wrong. Use a HashSet<T> for lookups, or maintain both a stack and a set when ordered LIFO with fast membership is genuinely needed.

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. There's no need 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 logically removed objects (with Pop, the slot is cleared, but stopping mid-pop leaves the remaining slots holding 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 explains why the operations are O(1). There's no list traversal, no node allocation, just an indexed write or read. Second, it explains why iteration matches reverse insertion order. The enumerator walks the array from _size - 1 down to 0, so the first item is the most recently pushed.

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. Growing the array by one each time would 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, keep a second stack: popping from the undo stack pushes the action onto the redo stack. Hitting redo pops from the redo stack and re-applies. This pairs 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 walking a tree or graph and going 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 haven't been 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 model: the stack holds "discovered but unvisited nodes." Popping a node visits it. Pushing its children adds new nodes to visit later. LIFO ensures depth-first; FIFO (a queue) gives 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 on 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, the final answer. Otherwise, the expression was malformed.

The RPN evaluator is short and direct because the stack handles all the "remembering" for the algorithm. Without a stack, the alternative is 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 (the next section shows it).

Call stack simulation. Recursive algorithms can always be rewritten iteratively with an explicit stack, swapping language-managed recursion for a data structure under direct control. The benefit is avoiding stack overflow for deep recursion, plus the ability to pause and resume the traversal. The cost is that the code is less compact because the recursion that was implicit becomes explicit.

This is a deliberately small example. Real call-stack-simulation use cases include tree walkers for very deep trees (where recursion would overflow the .NET stack) and state-machine engines that 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: torn writes, missed updates, or IndexOutOfRangeException from the iterator are all possible.

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> fits. It uses persistent data-structure techniques 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 for most "I need a stack" situations.