How a Stack Actually Works
A stack is defined entirely by one restriction: you may only touch the most recently added item. That sounds like a limitation and it is actually the point — the restriction is what makes stacks fast, simple, and the right model for anything with nesting, from bracket matching to the call frames your own program runs on.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int main() {
vector<int> st;
st.push_back(10);
st.push_back(20);
st.push_back(30);
cout << st.back() << endl;
st.pop_back();
cout << st.back() << endl;
while (!st.empty()) {
cout << st.back() << ' ';
st.pop_back();
}
cout << endl << st.size() << endl;
return 0;
}Implements the stack as a vector so every push and pop is a visible array operation rather than a black box.
How it works, step by step
Only the top is reachable
push_back adds at the end, back reads the end, pop_back removes the end. There is no operation that reaches into the middle, and that is deliberate: the guarantee that access is restricted is what lets the structure be this simple.
Everything is O(1) because nothing shifts
Adding and removing at the end of a vector touches one slot. Compare that to inserting at the front, which has to move every existing element. Stacks are fast because they only ever operate where no shifting is needed.
LIFO models nesting
Anything that opens and closes in nested order — brackets, HTML tags, function calls, undo steps — matches the last-in-first-out discipline exactly. When you find yourself needing the most recent unfinished thing, you have found a stack.
Growth is amortised, not free
A vector doubles its capacity when it fills, so an occasional push copies every element. Averaged over many pushes the cost is still O(1) per operation, but individual pushes can be slow — this matters if you are measuring latency rather than throughput.
Your program already runs on one
Every function call pushes a frame holding parameters and locals; every return pops it. That is why a runaway recursion produces a stack overflow, and why local variables vanish when a function ends — the same LIFO rules, applied to memory.
Complexity
All operations touch a single position at the end of the underlying storage, so none of them depend on the number of elements; the only non-constant moment is a reallocation when a vector-backed stack outgrows its capacity.
Common bugs
Calling back() or pop_back() on an empty stack
Neither throws. back() on an empty vector is undefined behaviour and typically returns whatever bytes are sitting there, so your code proceeds with a plausible-looking garbage value. Always guard with !st.empty(), and be aware that std::stack behaves the same way.
Expecting pop to return the value
In C++, pop_back and stack::pop return void. Writing int x = st.pop_back(); does not compile, and the fix is to read back() first and then pop. This split exists for exception-safety reasons, and it trips up everyone arriving from Python or Java.
Holding a reference across a push
int& top = st.back(); followed by st.push_back(...) can invalidate top, because the push may reallocate the vector and move every element to new memory. The reference then points at freed storage. Copy the value instead of binding a reference if a push might follow.
Using a stack when you needed a queue
Draining a stack reverses the insertion order. If your breadth-first search visits nodes in the wrong sequence, or your task list processes the newest item first, you have picked the wrong structure — and the output is often subtly wrong rather than obviously broken.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
What does LIFO mean?
Last In, First Out — the most recently added element is the first one removed. It describes a stack of plates: you take from the top, and the plate you put down last is the one you pick up first. The opposite discipline, FIFO, describes a queue.
Why are stack operations O(1)?
Because every operation acts on one end of the storage, so no other elements need to move. Push writes one slot, pop discards one slot, and top reads one slot — none of these depend on how many elements the stack holds. Inserting or removing anywhere else would require shifting.
What is a stack used for in programming?
Anywhere the most recent unfinished item is the one you need next: matching brackets, evaluating expressions, undo history, depth-first search, backtracking, and the function call stack itself. The common thread is nested structure — things that open and close in order.
What is the difference between a stack and a queue?
A stack removes the newest element (LIFO); a queue removes the oldest (FIFO). That single difference changes traversal order entirely — a graph search with a stack goes deep along one path, while the same search with a queue explores level by level.