Stacks

• Coding Interview Patterns
• /
• Stacks

Problems

No questions available

A stack is a data structure that follows the Last-In, First-Out (LIFO) principle. The last item you put in is the first item you take out.

Think of a stack of plates. You add plates on top and remove from the top. You can't pull a plate from the middle or bottom without removing everything above it first.

Stacks are everywhere in programming. Every time you call a function, it goes on the call stack. When you hit undo in a text editor, it pops the last action from a stack. Browser back button? Stack.

A stack supports only a few operations, and that's what makes it powerful. You don't need random access. You only care about the top.

• push(item): Add an item on top of the stack
• pop(): Remove and return the top item
• peek() / top(): Look at the top item without removing it
• isEmpty(): Check if the stack has no items
• size(): How many items are in the stack

Operation What it does Time Complexity push(item) Add item on top O(1) pop() Remove and return top item O(1) peek() / top() Look at top item O(1) isEmpty() Check if stack is empty O(1) size() Number of items O(1)

Notice that every operation is O(1). That's the beauty of a stack. You never search, you never iterate. You only touch the top.

Loading visualization...

In most languages, you don't need to build a stack from scratch. Arrays and built-in collections work perfectly.

Python: Use a regular list. append() is push, pop() is pop, [-1] is peek.

Java: Use Deque stack = new ArrayDeque(). Avoid the old Stack class.

JavaScript: Use an array. push() and pop() are built in.

C++: Use std::stack from the standard library.

Go: Use a slice. Append to push, slice to pop.

You can build a stack using an array or a linked list. In practice, arrays are almost always better.

• Array-based: Items are stored in contiguous memory. push/pop just move a pointer. Very cache-friendly and fast.
• Linked list-based: Each node points to the one below it. Push adds a new head, pop removes the head. Uses more memory because of the pointers.

Use an array-based stack unless you have a specific reason not to.

Array-based Linked list-based push() O(1) amortized O(1) pop() O(1) O(1) Memory Compact, cache-friendly Extra pointer per node Best for Almost everything When max size is unknown and memory is tight

Stacks Show Up More Than You Think

• Function call stack: Every function call pushes a frame. When it returns, the frame is popped. This is how recursion works under the hood.
• Undo/Redo: Text editors push each action onto a stack. Undo pops the last action. Redo uses a second stack.
• Browser history: Back button pops the current page and pushes it onto a forward stack.
• Expression evaluation: Calculators use stacks to handle operator precedence and parentheses.
• Syntax parsing: Compilers use stacks to match brackets, parse HTML tags, and validate nested structures.

Look For These Clues In a Problem

• Matching pairs: Anything that opens and closes (brackets, tags, quotes). Push the opener, pop when you see the closer.
• "Next greater" or "next smaller": A monotonic stack solves this in one pass. Keep the stack sorted, pop elements that violate the order.
• Undo operations: Anything where you need to reverse the most recent action.
• Nested structures: Parsing expressions, handling nested groups, function calls.
• Converting recursion to iteration: Any recursive algorithm can be rewritten with an explicit stack. This is exactly what DFS does.
• Popping from an empty stack. Always check isEmpty() before calling pop() or peek(). Forgetting this causes runtime errors.
• Using Java's Stack class. The java.util.Stack class is legacy and synchronized (slow). Use ArrayDeque instead.
• Forgetting items left in the stack. In monotonic stack problems, items remaining after the loop have no "next greater" element. Don't forget to handle them (usually set to -1).
• Confusing stack with queue. Stack is LIFO (last in, first out). Queue is FIFO (first in, first out). If you need level-order processing, you need a queue, not a stack.

Stack (LIFO) Queue (FIFO) Order Last in, first out First in, first out Add push (top) enqueue (back) Remove pop (top) dequeue (front) Use when Need to reverse, match pairs, backtrack Need ordering, level-by-level, BFS Real life Stack of plates, undo button Waiting in line, printer queue

Related concepts

• Introduction to Two Pointers Pattern

Stacks practice

• Valid Parentheses
• Remove All Adjacent Duplicates In String
• Min Stack
• Daily Temperatures

Back to Coding Interview Patterns