Data Structures
Stack (LIFO)
Difficulty: Beginner
Every time a function calls another function, the language runtime pushes a frame onto an internal stack; every return pops one off. That same Last In, First Out discipline shows up in undo buttons, expression evaluators, browser back...
Stack (LIFO)
Every time a function calls another function, the language runtime pushes a frame onto an internal stack; every return pops one off. That same Last In, First Out discipline shows up in undo buttons, expression evaluators, browser back navigation, and the call patterns of recursion, which is why Stack (LIFO) is one of the first abstract data types every engineer learns.
This lesson introduces the four core operations of a stack (push, pop, peek, isEmpty), the underflow case you must handle on every pop, and two implementations: a dynamic array stack with amortized O(1) push, and a linked list stack with strict O(1) push at the head. You will trace stack state through bracket matching, postfix evaluation, and string reversal so the LIFO mental model becomes a tool you reach for instinctively when a problem asks you to remember the most recent thing.
In Arrays & Strings, you saw that appending to the end of a dynamic array is O(1) amortized, which is exactly the cost model for an array-backed stack. Linked Lists (Singly) showed that head insertion is unconditionally O(1), which is what makes a linked list the cleanest backing store for a stack with a strict worst-case guarantee.
Next, Queue & Deque flips the discipline: instead of pulling from the same end you pushed to, you pull from the opposite end, and the implementation gets just a little more interesting.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain LIFO with a concrete real-world example and contrast it with FIFO.
Implement push/pop/peek safely (handle underflow) using both array-based and linked-list-based approaches.
Trace stack state after a sequence of operations and predict the output.
Identify common stack use cases: call stack, bracket matching, expression evaluation, undo/redo, and browser navigation.
State time/space complexity for typical implementations and explain amortized O(1) for dynamic arrays.
Why This Matters
01
Stacks model nested behavior (like function calls and recursion) — every programming language uses a call stack internally.
02
They power undo/redo flows, bracket parsing, expression evaluation, and backtracking patterns found in real software.
03
Many interview patterns reduce to 'use a stack to remember the most recent thing' — recognizing this pattern is a core skill.
Key Terms
5 terms you'll encounter in this lesson
LIFO
Last In, First Out — the most recently added item is removed first.
Underflow
Trying to remove (pop) from an empty stack — an error condition that must be handled explicitly.
Peek
Reading the top element without removing it — a non-destructive observation of the stack's state.
Amortized O(1)
Average per-operation constant time over many operations. Although occasional resizes cost O(n), the average cost per push stays O(1) when amortized across all pushes.
Call Stack
The internal stack maintained by the runtime to track function calls. Each function call pushes a frame; each return pops it.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Pop removes the oldest item"
That's FIFO (queue behavior). A stack is LIFO: the newest (most recently pushed) item is removed first. Think of it like a stack of plates — you take from the top, not the bottom.
"Peek removes the element"
Peek reads the top element without removing it. The stack remains unchanged after peek. Only pop actually removes an element.
"Pop on an empty stack should return null or undefined"
This is a design choice, not a universal rule. Some implementations throw an error (fail-fast for debugging), others return null/undefined (graceful handling). Always define and document the behavior explicitly.
"A linked-list stack is always better than an array stack"
Array-backed stacks have better cache locality (contiguous memory) and lower per-element overhead (no pointer storage). Linked-list stacks avoid resizing but use more memory per node. For most use cases, array-backed is preferred.