CHAPTER 04 · Stack

The Stack

A pile of plates: adding and removing both happen at one end, the top. So the element you remove is always the one you added most recently. That single rule, last in first out, is what makes a stack fit nesting, undo, and function calls.

§01

Intuition: a pile of plates, and only the top moves

First a group of problems, then the structure built for them.

Arrays and linked lists give you a general way to store a sequence of items. Now look at three features you use every day. In an editor, Ctrl+Z undoes the most recent change. In a browser, Back returns to the previous page. When one function calls another, the function called last is the first one to finish. The three look different, but they share one shape: what happened most recently is handled first.

For this kind of problem you give up free access to any position and take a restricted structure instead: the stack. Think of a pile of plates. A clean plate goes on top, and the plate you take is the one on top, so the plate placed last is taken first. The mechanism is exactly that: additions and removals happen at the same end, so the element removed is always the most recent one added. The name for the rule is LIFO, last in, first out. A stack sets only three rules:

RULE 01

Only the top

push (add), pop (remove), and peek (look) all act on the top. There is no operation for reaching an element in the middle. To get to one, you first remove everything above it.

RULE 02

Last in, first out

The element added last is removed first. This is not a side effect of the restriction, it is the purpose. Nesting, undo, and going back are all “most recent first” orders.

RULE 03

One end is closed

Nothing enters or leaves at the bottom or in the middle. With so few operations, each one can be made cheap: pop, peek, isEmpty, and size are O(1), and push is O(1) amortized when an array backs the stack.

What the restriction buys you

A data structure is defined as much by what it forbids as by what it allows. A stack forbids access to the middle, and in return every operation is cheap, the order can never come out wrong, and the implementation is short. When you read “the most recent one first”, “matching nested pairs”, or “undo and go back”, the first structure to consider is a stack.

Stacks are everywhere

The undo stack in an editor, the history stack in a browser, the tag stack in a JSON or HTML parser, expression evaluation, and the function call stack of every language runtime (§03). Every line of code you write runs on top of a call stack.

§02

In memory: an array or a linked list with a rule attached

A stack is not a new way to store data. It is a contract that only one end may be touched.

Look at memory and a stack has no layout of its own: it lives either in an array or in a linked list. The word “stack” describes the interface and the rule (you may only add and remove at one end), not the storage. A structure defined by its operations rather than by its storage is called an abstract data type (ADT). Here is the same contract, kept in two ways:

IMPLEMENTATION 1 · ARRAY

Array: the top is the last slot

top

·4

·5

✓ push and pop both happen at the end, so no other element moves: O(1).
✗ If the top were at index 0, every push and pop would shift the whole array by one: O(n). That is the lesson from the array chapter.

IMPLEMENTATION 2 · LINKED LIST

Linked list: the top is the head node

top

null

✓ The top is the head node: inserting and deleting there changes one pointer, O(1) even in the worst case, and there is never a resize.
△ The cost: every push allocates a node, every node carries an extra next pointer, and the nodes are scattered on the heap, so access is less cache-friendly than an array (see the linked list chapter).

Why is the top at the end of the array but at the head of the linked list? The same reason in both cases: pick the end where nothing has to move and nothing has to be searched for. In an array, appending and deleting at the end is O(1), while at the front every element would shift. In a linked list, inserting and deleting at the head is O(1), while removing the last node means walking the list to find the node before it. The structure changes, the principle does not.

Which implementation should you choose?

Most standard libraries use the array version. Contiguous memory suits the CPU cache, and the cost of growing is acceptable: one resize copies n elements, but the capacity grows in proportion to the size, so the cost spread over all the pushes is constant. That is why an array-backed push is O(1) amortized and not O(1) in the worst case. The linked-list version is the opposite: push is O(1) even in the worst case, with no resize pause, but every push allocates a node, every node carries an extra next pointer, and the nodes are scattered on the heap, so access is less cache-friendly. The steady per-operation cost matters in real-time code, such as some embedded or audio systems. Java ArrayDeque, Python list, and JavaScript Array all take the array route.

§03

Core operations: four actions, and what each one costs

Every cost answers one question: do other elements have to move?

Operation	Meaning	Complexity	Why
push(x)	Put x on the top	O(1) amortized	Writes at the end of the array or at the head of the list, moving nothing. An array-backed stack occasionally resizes and copies n elements, so the cost is amortized.
pop()	Remove and return the top	O(1)	Touches one element. Deleting at the end of an array or at the head of a list moves nothing.
peek()	Look at the top without removing it	O(1)	Reads the last slot or the head node. Nothing is even removed.
isEmpty() / size()	Empty test, element count	O(1)	Reads a counter.
Read or search an element in the middle	——	O(n)	A stack does not offer this. You would have to pop everything above it. If you need random access, use an array.

Push a few plates yourself. Watch two things: how the top moves, and what happens when you pop an empty stack.

StackLab — push a pile of plates yourself

7top

bottom · closed, no access here

Two plates are in place. push adds one on top, pop takes the top one off. Watch top: it always points at the highest plate.

size 2 · pushes 0 · pops 0

Edge case: popping an empty stack

Calling pop or peek on an empty stack behaves differently in each language. Java ArrayDeque throws NoSuchElementException. Python raises IndexError. JavaScript [].pop() does not fail; it returns undefined. The silent one is the most dangerous, because the error surfaces far from where it started. So the template is always: check for empty, then touch the top. LC 20 is a direct example: if a closing bracket arrives while the stack is empty, you can return false immediately.

Now look at the most important job a stack does inside a computer: the call stack. Every function call pushes one stack frame. A frame holds the parameters, the local variables, and the return address, which is the point in the caller where execution continues. Every return pops one frame. Step through it:

CallStackDemo — the call stack, frame by frame

main()local a · resumes at line 2

call stack · grows upward · the top frame is running

When the program starts, the stack frame for main is pushed first. A frame holds this function’s parameters, its local variables, and the address to return to.

1 / 7

The stack region, threads, and recursion depth

As the introduction chapter described, a process reserves a region of memory for the call stack, one per thread, usually 1 to 8 MB by default (Java: -Xss, Linux: ulimit -s). One frame takes tens to a few hundred bytes, so the depth limit is roughly tens of thousands of calls. Python sets its own limit and stops at 1000 recursive calls by default. This is why code that walks very deep trees or graphs often rewrites the recursion as a loop with an explicit stack (pattern three in §06). Any recursion can be rewritten that way, although the result is not always as easy to read.

§04

Build one: a dynamic array plus a top index

One sentence holds it together: size is both the number of elements and the index of the next free slot, so the top sits at size − 1.

Build a stack on top of the dynamic array from the array chapter. You will see that implementing a stack mostly means taking abilities away from the array: expose the operations at the end, hide everything else. The Java version resizes by itself; Python list and JavaScript Array already resize, so those versions are shorter. What happens in memory is the same.

array_stack.py

1class ArrayStack:

2 """A stack backed by a list: the top is the last item."""

4 def __init__(self):

5 self._data = [] # a list resizes itself, so there is no grow()

7 def push(self, x):

8 self._data.append(x) # append at the end = push, O(1) amortized

10 def pop(self):

11 if self.is_empty():

12 raise IndexError("pop from empty stack")

13 return self._data.pop() # remove the last item = pop, O(1)

15 def peek(self):

16 if self.is_empty():

17 raise IndexError("peek from empty stack")

18 return self._data[-1] # read without removing

20 def is_empty(self):

21 return len(self._data) == 0

23 def size(self):

24 return len(self._data)

Why wrap a list at all? A list already has append and pop, but whoever holds an ArrayStack can only use it in LIFO order. Narrowing the interface removes a whole class of mistakes.

§05

Three languages: what to use as a stack

Java has one class you should not use. Here is the reason.

The abstraction is the same in all three languages, but the defaults are not. In Java you have to pick the right container, and one classic mistake lives here. In Python and JavaScript the built-in dynamic array is already the right answer.

stack_basics.py

1stack = [] # a list is already a stack

3stack.append(1) # push: append at the end

4stack.append(2)

5top = stack[-1] # look at the top -> 2

6x = stack.pop() # pop: with no argument it removes the last item -> 2

7empty = not stack # the usual way to test for empty

9# collections.deque is the choice when you need both ends

10# (appendleft / popleft are O(1); list.pop(0) is O(n))

Common mistake: pop(0) removes the first item, which shifts every remaining element and costs O(n) (see the array chapter). Stack code always calls pop() with no argument.

Operation	Java (ArrayDeque)	Python (list)	JavaScript (Array)	Complexity
Push	`stack.push(x)`	`stack.append(x)`	`stack.push(x)`	O(1) amortized
Pop	`stack.pop()`	`stack.pop()`	`stack.pop()`	O(1)
Look at the top	`stack.peek()`	`stack[-1]`	`stack.at(-1)`	O(1)
Empty test	`stack.isEmpty()`	`not stack`	`stack.length === 0`	O(1)
Pop on an empty stack	throws NoSuchElementException	raises IndexError	returns undefined, no error	——

§06

Three patterns, and monotonic stacks

★ Interview core

Almost every stack problem on LeetCode is one of these three, and the monotonic stack is the one interviews test.

PATTERN 01

Matching and nesting

Bracket matching, removing adjacent pairs, decoding nested strings. Whenever a closing item has to find the most recent opening item, push the opening items and let them wait. LC 20, 1047, 394, 150.

PATTERN 02

Next greater or next smaller

For each element, which is the first element to its right that is larger (or smaller)? A monotonic stack answers all of them in one pass and turns O(n²) into O(n). LC 739, 496, 503, 84, 42. Covered in detail below.

PATTERN 03

Replace recursion with a stack

Recursion already runs on the call stack. Replace the runtime’s stack with one you create yourself and any recursion becomes a loop, with no depth limit from the call stack. Iterative binary tree traversal, chapter 07.

A monotonic stack is a stack whose contents stay in sorted order; the order is kept by popping before each push. Take “next greater element” as the goal. The stack holds the indices of the elements whose answer is still unknown, and their values never increase from bottom to top. When a new element is larger than the value on top, that new element is the first larger element to the right of the top, so the top is popped and its answer is recorded. Why can a popped index be forgotten? Any later element that looks left for a larger value meets the element that did the popping first, because it is both larger and closer. So a popped index can never be anyone’s answer again. Three questions cover the whole technique:

QUESTION 01

Which order is kept?

Next greater: values never increase from bottom to top. Equal values may sit next to each other, because an equal value is not greater. Next smaller: the order is reversed. Mixing the two up breaks everything.

QUESTION 02

When do you pop?

When the new element breaks the order. In a non-increasing stack, a new element larger than the top pops it, and the while loop keeps popping until the top is at least as large as the new element, or the stack is empty. Then the new element is pushed.

QUESTION 03

What is settled at the pop?

The answer for the popped element is the element that popped it. LC 739 settles the number of days waited (the difference of the indices), LC 84 the rectangle whose height is the popped bar, LC 42 one horizontal layer of water. Store indices: an index gives you the position and the value, a value does not give you the position.

Why is it O(n)?

A while loop inside a for loop looks like O(n²). Count the total work instead: each index is pushed exactly once and popped at most once, and a popped index never comes back, so the whole scan performs at most 2n stack operations. This is the same amortized argument as array resizing: do not measure the most expensive single step, measure the total.

Walkthrough A

LC 20 · Valid Parentheses

EASY

The problem: a string containing only the six bracket characters. Decide whether it is valid, meaning every closing bracket matches the most recent unmatched opening bracket of the same type. Brute force: repeatedly delete adjacent pairs such as (), [], and {} until nothing can be deleted. Each pass is O(n) and there can be n/2 passes, so O(n²). The stack solution: the most recent unmatched opening bracket is the top of the stack, so one pass is enough. That is the reason a stack fits here, not a trick.

LC 20 · Bracket matching, stack drawn sideways (right end = top)

Input s = "([{}])". The rule: a closing bracket must match the most recent opening bracket that is still unmatched. “ Most recent” is exactly what a stack gives you, so the stack holds the opening brackets that are still waiting for a partner. It is drawn lying on its side below, with the top at the right end.

1 / 8

lc20_valid_parentheses.py

1class Solution:

2 def isValid(self, s: str) -> bool:

3 pairs = {')': '(', ']': '[', '}': '{'}

4 stack = []

5 for c in s:

6 if c not in pairs: # opening bracket: push and wait

7 stack.append(c)

8 elif not stack or stack.pop() != pairs[c]:

9 return False # stack empty, or the top does not match

10 return not stack # the stack must end up empty

Complexity and follow-up questions

Time O(n): each character is handled once. Space O(n): in the worst case every character is an opening bracket. Follow-up one: what if there is only one kind of bracket? A counter is enough: add one for (, subtract one for ), never let it go below zero, and it must end at zero. Follow-up two: why does a counter fail with several kinds? In ([)] each kind is balanced, but the pairs cross. Only the stack remembers the order in which the brackets were opened.

Walkthrough B

LC 155 · Min Stack

MEDIUM

The problem: design a stack that supports push, pop, and top, and also returns the current minimum with getMin in O(1). Brute force: scan the stack inside getMin, which is O(n) and is exactly what the problem rules out. A single min variable? Updating it on push is easy, but as soon as the minimum is popped you do not know the second smallest and you have to scan again. The fix: the problem is that the history was thrown away, so keep it. An auxiliary stack stores the minimum as of every push, and the two stacks move together:

LC 155 · Auxiliary stack (lower half of each cell = the minimum stored at that level)

Goal: push, pop, top, and getMin must all be O(1). One way: keep a second stack beside the main one. Each of its levels stores the smallest value in the stack as of that push. Both are drawn in a single cell here: the value on top, the stored minimum below. The price is O(n) extra space.

1 / 7

lc155_min_stack.py

1class MinStack:

2 def __init__(self):

3 self.stack = [] # main stack

4 self.mins = [] # auxiliary stack: the minimum as of each push

6 def push(self, val: int) -> None:

7 self.stack.append(val)

8 # this level = min(new value, previous minimum), fixed at push time

9 self.mins.append(val if not self.mins else min(val, self.mins[-1]))

11 def pop(self) -> None:

12 self.stack.pop()

13 self.mins.pop() # always together, so the minimum rolls back by itself

15 def top(self) -> int:

16 return self.stack[-1]

18 def getMin(self) -> int:

19 return self.mins[-1] # O(1)

Why can the auxiliary stack stay in step?

The reason is the LIFO rule itself. When the top is popped, what is exposed is exactly the stack as it was before that element was pushed, and the minimum frozen at that level is the minimum of that earlier state. In a structure that allows removal from the middle, such as an array, these snapshots stop being valid. LIFO is what lets the history roll back correctly. Follow-up: can it use less space? Two options. First, push onto the auxiliary stack only when the new value is smaller than or equal to the current minimum, and pop it only when the popped value equals the current minimum; that helps on average, but the worst case is still O(n). Second, keep a single stack and push the encoded difference 2 * val - min whenever a new minimum arrives, restoring the previous minimum on pop. That version uses O(1) extra space, but the encoded value can be roughly twice the range of the input, so it overflows 32-bit arithmetic and has to be done in 64-bit.

Complexity

All four operations are O(1). The auxiliary stack costs O(n) extra space. The general technique is worth keeping: when a quantity changes with the history of the stack, record that quantity at every level in a second stack. Many “design a stack that supports X” problems are variants of this one.

Walkthrough C

LC 739 · Daily Temperatures

MEDIUMMonotonic stack

The problem: given the temperature of each day, find how many days you have to wait for a warmer one, or 0 if it never gets warmer. Brute force: scan forward from every day, O(n²); with n = 10⁵ that is about 10¹⁰ steps, which is too slow. Why it can be improved: the brute force rescans the same stretch again and again. 74, 71, and 69 are all waiting for 75, so when 75 arrives all of them should be settled at once. Keep the days that are still waiting in a stack. Each new waiting day is colder than the one before it, which makes it a monotonic stack:

LC 739 · Monotonic stack (highlighted = waiting in the stack, green = answer settled)

730

741

712

693

754

735

T = [73,74,71,69,75,73]. For each day, how many days until a warmer one? Brute force scans forward from every day: O(n²). The monotonic stack holds the indices of the days whose answer is still unknown, and their temperatures never increase from bottom to top. A highlighted cell is waiting in the stack; green means its answer is settled.

1 / 10

lc739_daily_temperatures.py

1class Solution:

2 def dailyTemperatures(self, temperatures: list[int]) -> list[int]:

3 n = len(temperatures)

4 ans = [0] * n # default 0: no warmer day ahead

5 stack = [] # indices, temperatures non-increasing

6 for i, t in enumerate(temperatures):

7 # while today is warmer than the top, today is the answer the top waited for

8 while stack and t > temperatures[stack[-1]]:

9 j = stack.pop()

10 ans[j] = i - j # settled at the moment of the pop

11 stack.append(i) # today waits for its own answer

12 return ans

Complexity and follow-up questions

Time O(n): each index is pushed once and popped at most once, so at most 2n stack operations. A nested loop does not make this O(n²). Space O(n). Follow-up one: why store indices instead of temperatures? Settling an answer needs the difference of two indices, and an index also gives you the temperature, while a temperature does not give you the index. Follow-up two: how do you find the previous greater element? In the same pass: just before index i is pushed, the index on top of the stack is the nearest day to its left whose temperature is at least T[i]. Follow-up three: what if the array is circular? Run the index from 0 to 2n − 1 and use i % n, and on the second pass only pop, never push (LC 503, in the problem set).

§07

Problem set: 10 stack problems

Hot 100 selection

Pair cancellation, then expressions, then monotonic stacks, easy to hard. Think for 30 seconds before you open the hint.

LC 1047Remove All Adjacent Duplicates In StringStackPair cancellationEASY

LC 232Implement Queue using StacksTwo stacksAmortized analysisEASY

LC 225Implement Stack using QueuesQueueRotationEASY

LC 682Baseball GameStackSimulationEASY

LC 150Evaluate Reverse Polish NotationStackExpression evaluationMEDIUM

LC 394Decode StringStackNested structureMEDIUM

LC 496Next Greater Element IMonotonic stackHash tableEASY

LC 503Next Greater Element IIMonotonic stackCircular arrayMEDIUM

LC 84Largest Rectangle in HistogramMonotonic stackSentinelHARD

LC 42Trapping Rain WaterMonotonic stackTwo solutionsHARD

§08

Quiz

✎ Quiz

All 7 correct turns this chapter green.

QUESTION 01 / 7

What does LIFO (Last In, First Out) mean for a stack?

QUESTION 02 / 7

If you back a stack with a dynamic array, which end of the array should be the top, and why?

QUESTION 03 / 7

Which of these are true about calling pop on an empty stack? (Select all that apply.)

QUESTION 04 / 7

In the monotonic stack solution to LC 739 (daily temperatures), what order does the stack hold from bottom to top?

QUESTION 05 / 7

Why is java.util.Stack not recommended, in interviews or in production code?

QUESTION 06 / 7

A recursive function has no base case, or recurses 100,000 levels deep. What is the most likely result?

QUESTION 07 / 7

While a monotonic stack scans an array of length n, each index is pushed at most ___ time(s) (type a number). This is why the total cost is O(n) and not O(n²).

What to take away from this chapter

A stack is a container with one opening. pop, peek, isEmpty, and size are O(1); push is O(1) amortized on an array and O(1) in the worst case on a linked list, at the cost of one allocation per node. Array-backed: the top is the last slot. Linked-list-backed: the top is the head node. Both pick the end where nothing has to move.
“The most recent one first” is the signal for a stack: undo, going back, bracket matching, nested decoding, function calls. A nested structure is a LIFO order.
The call stack: one frame per call, holding the parameters, the local variables, and the return address; one pop per return. Recursion pushes frames for the same function, and too many of them means a stack overflow. An explicit stack plus a loop is the way out, and it works for any recursion.
Monotonic stack: for next greater, keep the values non-increasing from bottom to top; pop when a new element breaks the order and settle the popped element’s answer at that moment; each index is pushed once and popped at most once, so the whole pass is O(n).
What to use: ArrayDeque in Java (not java.util.Stack, which extends Vector and synchronizes every method), list in Python (collections.deque when you need both ends), and Array in JavaScript. Remember that popping an empty array in JavaScript returns undefined instead of failing.