Stacks

Data structures

At a glance

A stack is last in, first out (LIFO). The most recently added item is the first one removed.

Action	Meaning	Typical time
Push	Add an item	`O(1)` amortized
Pop	Remove the top item	`O(1)`
Peek	Inspect the next item without removing it	`O(1)`

Try the operations

Try it yourself

Value

Last in, first out (LIFO)

The top is the only removal point, so the newest value leaves first.

How the order works

Add items one after another.
Look at the next item. It is at the end of the stack.
Remove one item. The next item changes, but the remaining order is preserved.
Repeat until the collection is empty.

var items = new Stack<int>();
items.Push(10);
items.Push(20);
Console.WriteLine(items.Peek()); // 20
Console.WriteLine(items.Pop());  // 20

#include <stack>
#include <iostream>
std::stack<int> items;
items.push(10);
items.push(20);
std::cout << items.top() << '\n'; // 20
items.pop(); // pop returns void in C++

When does this help?

Stacks naturally fit undo history, depth-first traversal and parsing nested expressions. Recursive calls also use a call stack.

The invariant that matters

Only the top element can be removed by an ordinary stack pop. This is the LIFO rule: last in, first out. The stack does not promise anything about the values themselves being sorted. It preserves the order in which operations were performed.

Where stacks appear

Stacks are useful for undo histories, expression parsing, depth-first search and nested function calls. A browser’s Back behavior may resemble a stack, but real browser history has more rules than a basic stack model.

Resource costs

Push and pop are typically constant-time in standard stack implementations. A stack backed by a dynamic array may occasionally need a larger allocation; average append behavior can still be amortized constant-time. Plan for the empty-stack case before calling pop.