Stacks: Push on Top, Pop from the Top
The LIFO (last-in, first-out) discipline — where stacks shine (undo, function calls, bracket matching) and how to write one in C, Java, C#, and Python
What a stack is: a pile of plates
A stack is a restricted container that allows only two things: putting something on top (push) and taking something off the top (pop). Picture a pile of plates — a new plate goes on top, and you always take from the top. You cannot pull a plate out of the middle.
push(40) pop() -> 40 | ^ v | +------+ top -> | 40 | <- the last one in is the first one out +------+ | 30 | +------+ | 20 | +------+ | 10 | <- the first one in stays until the end +------+ LIFO: Last-In, First-Out
The last thing you put in is the first thing that comes out — a discipline called LIFO (Last-In, First-Out). Both push and pop only ever look at the top of the pile, so both are O(1).
"Can't touch the middle" sounds inconvenient, but it is the opposite. Precisely because the operations are restricted, the motion of "going back to what you did last" can be expressed in a way that cannot go wrong.
Where stacks are used
The most familiar example is function calls. Every time a function calls another, the "place to return to" is pushed onto a stack, and every return pops it off. A "stack overflow" from too-deep recursion is exactly this pile growing too tall.
An editor's undo and the browser's back button are also stacks — push the previous state, pop to go back. In algorithms, a stack drives depth-first search (DFS): go as deep as you can, and when you hit a dead end, step back once.
As a small worked example, consider bracket matching: push every opening bracket, and when a closing bracket arrives, pop and check that it matches.
Reading "( [ ] ( ) )" one character at a time: read operation stack contents ( push '(' ( [ push '[' ( [ ] pop, matches '[' ( ( push '(' ( ( ) pop, matches '(' ( ) pop, matches '(' (empty) Empty at the end -> every bracket is properly matched
Implementation: either an array or a linked list works
Either structure from the previous page can implement a stack. With a dynamic array, treat the end as the top: push and pop are amortized O(1). With a linked list, treat the head as the top: both are O(1).
So a stack is a promise about how the data may be used, not about how it is stored. The separation between the inner structure and the outward contract (the interface) shows up here again.
Across languages: C, Java, C#, and Python
In C
/* C: no standard stack — build one from an array and an index */ int stack[100]; int top = 0; /* the next free slot */ void push(int v) { stack[top++] = v; } int pop(void) { return stack[--top]; }
C has no standard stack. You build one from an array and an index pointing at the next free slot — which shows how small a promise a stack really is (overflow/empty-stack checks omitted).
In Java
// The idiom: the Deque interface + the ArrayDeque implementation Deque<String> stack = new ArrayDeque<>(); stack.push("a"); // push on top stack.push("b"); String top = stack.pop(); // "b" — the last one pushed comes out // java.util.Stack is a relic extending Vector (an old synchronized // dynamic array); the official docs recommend Deque instead.
One caution: Java does have a class literally named java.util.Stack, but it is a relic of early Java. It extends Vector (an old dynamic array with every method synchronized), and the official documentation itself recommends using the Deque interface instead.
The modern idiom is an ArrayDeque used via push / pop. Inside it is the ring buffer we will meet on the next page — fast, with no unnecessary synchronization cost.
In C#
// C#: a dedicated Stack<T> class (an array inside) var stack = new Stack<string>(); stack.Push("a"); // push on top stack.Push("b"); string top = stack.Pop(); // "b" — the last one pushed comes out
C# ships a dedicated Stack<T> class (an array inside). Even the method names — Push / Pop / Peek — mirror the concept directly.
In Python
# Python: use a plain list as the stack (a dynamic array inside) stack = [] stack.append("a") # push stack.append("b") top = stack.pop() # "b" — taken from the end (the top)
In Python, the idiom — recommended by the official docs — is to use a plain list as a stack. append / pop at the end are amortized O(1): the dynamic array with its end as the top — exactly the construction from the implementation section above.
Summary
A stack is a restricted container with only push / pop. The discipline is LIFO, and both operations are O(1).
The standard building block for "going back": function calls, undo, depth-first search, bracket matching.
It can be built on an array or a linked list — a stack is a usage contract, not a particular structure.
Most languages have an idiom: ArrayDeque in Java (java.util.Stack is a relic), Stack<T> in C#, a plain list in Python — and in C you build one from an array and an index.