A stack is a linear data structure that follows the last-in, first-out (LIFO) principle: elements are added and removed only at one end, called the top, so the most recently added element is always the first to leave. Among data structures, the stack is one of the simplest abstract data types, yet it underpins function calls, expression evaluation, parsing, backtracking and undo features.
A stack is defined by its behavior rather than its storage. It can be implemented on top of an array or a linked list, and in both cases the core operations run in constant time, O(1).
How a stack works
A stack works by restricting access to a single position, the top. Push places a new element on the top, pop removes and returns the top element, and peek reads the top element without removing it. Because no operation reaches below the top, the order of removal is always the exact reverse of the order of insertion.
Two error conditions follow from this design. Popping an empty stack causes underflow, and pushing onto a full fixed-capacity stack causes overflow. Well-designed implementations either check with an isEmpty operation or signal these conditions explicitly instead of returning invalid data.
| Operation | Effect | Time complexity |
|---|---|---|
| Push | Adds an element on the top | O(1), amortized for dynamic arrays |
| Pop | Removes and returns the top element | O(1) |
| Peek or top | Returns the top element without removing it | O(1) |
| isEmpty | Reports whether the stack has no elements | O(1) |
| Size | Returns the number of elements | O(1) when a counter is kept |
Array-based and linked-list implementations
The two standard implementations differ in memory layout, growth behavior and cache efficiency. An array-based stack stores elements contiguously and keeps an index to the top, while a linked-list stack adds and removes nodes at the head of the list.
| Property | Dynamic array stack | Linked-list stack |
|---|---|---|
| Push cost | O(1) amortized, occasional O(n) resize | O(1) always, one allocation per node |
| Memory overhead | Unused spare capacity | One pointer per element |
| Cache locality | Excellent, contiguous memory | Poor, nodes scattered in memory |
| Capacity limit | Grows by reallocation, often doubling | Limited only by available memory |
| Typical choice | Default in most standard libraries | When resize pauses must be avoided |
In practice, dynamic arrays are usually faster because modern processors read contiguous memory efficiently. Growing the array by a constant factor, typically 1.5 or 2, keeps the average push cost constant even though an individual resize copies every element. Many standard libraries expose stacks directly, for example as a list with append and pop in Python or as an ArrayDeque in Java.
Stack compared with queue and other linear structures
A stack differs from its closest neighbor, the queue, only in which end elements leave from, but that single difference changes which problems each structure solves. A queue processes elements in first-in, first-out (FIFO) order, which preserves arrival order instead of reversing it.
| Structure | Access rule | Typical use |
|---|---|---|
| Stack | Last in, first out at one end | Call frames, undo, depth-first search |
| Queue | First in, first out | Task scheduling, breadth-first search |
| Deque | Insert and remove at both ends | Sliding windows, work stealing |
| Priority queue | Highest-priority element first | Scheduling, shortest-path algorithms |
| Array | Random access by index | General storage and lookup |
A deque can act as either a stack or a queue, which is why some libraries implement stacks on top of one. Depth-first traversal of a tree or graph naturally uses a stack, while breadth-first traversal uses a queue.
Where stacks are used
Stacks appear wherever a program must return to the most recent unfinished task before older ones. The most important case is the call stack, where each function call pushes a stack frame holding its parameters, local variables and return address, and each return pops it.
| Application | What is pushed | Why a stack fits |
|---|---|---|
| Function calls and recursion | Stack frames | The latest call must finish first |
| Bracket matching and parsing | Opening symbols | The latest opening must close first |
| Expression evaluation | Operands and operators | Postfix notation evaluates naturally |
| Undo history | Previous states or commands | The latest change is reversed first |
| Backtracking and depth-first search | Choices or nodes to revisit | Returns to the most recent branch |
Some languages, such as Forth and PostScript, and many virtual machines, such as the Java Virtual Machine, use a stack as their main evaluation model, pushing operands and applying operations to the values on top.
Limitations and common mistakes
The strength of a stack, its restricted access, is also its main limitation. Several practical mistakes recur when stacks are used.
- Searching a stack: finding an arbitrary element requires popping or scanning, which costs O(n); use another structure if lookups are frequent.
- Unchecked pop or peek: calling them on an empty stack raises errors or returns undefined values.
- Call stack overflow: deep or unbounded recursion exhausts the call stack, which is often limited to about 1 to 8 MB per thread depending on the platform; convert such recursion into a loop with an explicit stack.
- Confusing the data structure with stack memory: the region of memory called the stack is managed by the runtime and is distinct from a stack object created by a program.
- Holding references after pop: in managed languages, leaving popped objects referenced in the array prevents garbage collection.
In everyday language
A stack is like a pile of plates in a kitchen. You put a clean plate on top, and when you need one, you take the top plate. The plate you added last is the first one you use.
Computers use this simple rule all the time. When a program pauses one task to start another, it remembers its place on a stack. It then picks up exactly where it left off, newest task first.
Seen in the real world
A code editor checks whether every bracket in a file is correctly closed. As it reads the text from left to right, it pushes each opening bracket onto a stack. When it finds a closing bracket, it pops the top element and checks that the two brackets match.
In a line such as if (items[i] > 0) { total += items[i]; }, the stack never grows beyond two elements and is empty at the end, so the code is balanced. If a closing parenthesis appears while the top of the stack holds a square bracket, the editor immediately underlines that exact position as an error.
The result is instant, precise feedback on mismatched brackets in files of any length, achieved in a single pass with linear time and memory proportional to the nesting depth.