cf.completefrontend
STACKS & QUEUES · FOUNDATION

Stack

A list where you only add and remove at the top, so the last item in is the first one out.

Time O(n)Space O(n)19 practice problemsStep-through picture

The idea

A stack is a list with one open end, called the top. You can push an item onto the top, pop the top item off, or peek at it. You never reach into the middle. Because of this, the item you get back is always the most recent one you added: last in, first out.

That rule matches any task where the newest unfinished thing must be finished first. When you read ( [ ] ), the ] must close the [ that opened most recently, not the (. A stack remembers the open brackets, and its top is always the one that must close next.

In JavaScript a plain array is a good stack: push adds to the end, pop removes from the end, and stack[stack.length - 1] peeks. All three are O(1).

An everyday example

A pile of plates

In a kitchen, clean plates go on top of the pile, and whoever needs a plate takes the top one. Nobody pulls a plate from the middle. The plate you take is always the one that was put down last.

How the example maps to the code
In the exampleIn the code
The pile of platesstack, an array
Putting a plate on topstack.push(item)
Taking the top platestack.pop()
Looking at the top plate without taking itstack[stack.length - 1]
No plates leftstack.length === 0

From the slow way to stack

  1. Start with the obvious check for balanced brackets: count them. Add one for every ( and subtract one for every ), and the text is fine if the count never drops below zero and ends at zero. That works for one kind of bracket. With three kinds it fails: ([)] has matching counts for every kind, yet the brackets cross each other.
  2. Another obvious way is to delete pairs: find any (), [], or {} that sit right next to each other, remove them, and repeat until nothing changes. If the text becomes empty, it was balanced. That is correct, but each pass scans the whole text, so it can take O(n^2) time.
  3. Look at what deleting pairs really does. A closer always pairs with the newest opener that is still open, because pairs nest: the inner pair must close before the outer one. So you never need the older openers until the newer ones are closed. You only ever need the most recent open bracket, and when it closes, the one before it becomes the most recent again.
  4. A list where you only add and remove at one end gives exactly that: the last item in is the first item out. Push each opener, and on each closer pop the top and check that it matches. At the end, the text is balanced only if nothing is left open. That loop is the stack-based bracket check.

How it works

  1. Create an empty array stack.
  2. Read the input one item at a time, here each char of text.
  3. When something opens, push it: stack.push(char).
  4. When something closes, the matching opener must be on top. If the stack is empty, or stack.pop() isn't the matching opener, the text is broken.
  5. Ignore characters that neither open nor close.
  6. At the end, the text is balanced only if nothing is left open: stack.length === 0.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function isBalanced(text) {
  2. const pairs = { ")": "(", "]": "[", "}": "{" };
  3. const stack = [];
  4. for (const char of text) {
  5. if (char === "(" || char === "[" || char === "{") {
  6. stack.push(char);
  7. } else if (char in pairs) {
  8. if (stack.length === 0) return false;
  9. if (stack.pop() !== pairs[char]) return false;
  10. }
  11. }
  12. return stack.length === 0;
  13. }

How fast it is

TimeO(n)
Extra memoryO(n)

Each character is pushed and popped at most once, each in O(1). The stack can hold up to n openers.

  • Best caseO(1)

    The first character is a closer, like ]abc: the stack is empty, so the function returns false after one character.

  • Average caseO(n)

    Ordinary text, balanced or with an error near the end. Each character is pushed and popped at most once.

  • Worst caseO(n)

    A balanced text, which must be read to the last character before the answer is known, or a text of only openers like ((((.

Common mistakes

  • Using shift and unshift, which work on the front of the array and move every other item. Use push and pop on the end.
  • Popping or peeking an empty stack. [].pop() returns undefined instead of throwing, which hides the bug. Check stack.length first.
  • Forgetting the final check that the stack is empty, so (( counts as balanced.
  • Counting brackets instead of using a stack. Counts can't tell ([)] (broken) from ([]) (fine).

When to use it

Look for these clues in a problem:

  • Things open and close in nested pairs: brackets, HTML tags, function calls, folders in a path.
  • The most recent unfinished item must be handled first, like undo.
  • The task processes a sequence left to right and sometimes cancels or combines the newest items, such as backspaces or collisions.
  • A recursive solution exists and you want a loop instead: the call stack becomes your own stack.

Check yourself

Answer each one in your head first, then open it.

Why can't three counters, one per bracket kind, replace the stack?

Counters lose the order. ([)] and ([]) have the same counts, but only the second is balanced. The stack remembers which opener is newest.

What would go wrong without the final stack.length === 0 check?

Text with unclosed openers, like "((", would return true, because no closer ever failed.

How many pushes and pops does a balanced text of length n cause?

Exactly n / 2 pushes and n / 2 pops if every character is a bracket: one push per opener and one pop per closer.

Why is popping before checking the match safe?

If the popped item doesn't match, the function returns false right away, so it doesn't matter that the item was removed.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 19 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The loop keeps one rule: as long as it hasn't returned, stack holds exactly the openers read so far that have not been closed yet, oldest at the bottom and newest on top. It starts empty, which is right for an empty prefix. Pushing an opener adds the newest open bracket on top, so the rule holds.

When a closer arrives, nesting means it must close the newest open bracket, the top. If the stack is empty, there is nothing for it to close, and no text added later can fix that, so false is right. If the top is the wrong kind, the pairs would cross, which also can never be fixed. If the top matches, popping it removes the one opener that just got closed, so the rule holds again.

The loop ends after the last character. By the rule, the stack then holds every opener that was never closed. The text is balanced only if that set is empty, which is exactly the final stack.length === 0 check.

Going deeper

3 more ideas

Why the top is always the right opener

In well-nested text, every pair closes before the pair around it does. So when a closer arrives, the opener it must match is the newest one still open. The stack keeps the openers in the order they arrived, and its top is the newest, which is exactly the one to check.

Cost

Each character is pushed at most once and popped at most once, and both are O(1), so a text of length n takes O(n) time. In the worst case, such as ((((((, every character is pushed, so the stack uses O(n) space.

Stacks and recursion

When a function calls itself, the engine pushes the call's local variables onto the call stack and pops them when it returns. Any recursive walk, such as a depth-first walk of the DOM, can be written as a loop with your own array as the stack. That avoids "Maximum call stack size exceeded" errors on very deep inputs.

Work it by hand

Every step in a table, with why

Check a short text that holds letters, two bracket pairs inside braces, and then one extra closer.

text = "{[a](b)}]"

StepcharKindstack after (bottom to top)What happensWhy
1{opener{pushAn opener can't be checked yet, so it waits on the stack.
2[opener{ [pushThe newest opener is now [, on top.
3aother{ [ignorea is neither an opener nor a key of pairs, so the loop skips it.
4]closer{pop [: matchpairs["]"] is [, and the popped top is [, so this pair is fine.
5(opener{ (pushA new opener sits on {, which is still waiting.
6bother{ (ignoreLetters never touch the stack.
7)closer{pop (: matchThe newest open bracket is (, which is what ) needs.
8}closeremptypop {: matchThe outer pair closes last, as nesting requires. The stack is empty.
9]closeremptyempty: return falseA closer arrives with nothing open, so stack.length === 0 and the function stops at once.

It returns false at the ninth character, the extra ]. Without that last ], the loop would end with an empty stack and return true.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
StackO(n)O(n)Several kinds of brackets, tags, or any nested pairs where the newest open item must close first.
One counterO(n)O(1)Only one kind of bracket. The counter is the stack's height, since every item on the stack would be the same.
Repeatedly delete adjacent pairsO(n²)O(n)Almost never. It is easy to explain, but each pass rescans the text.

Extra memory: O(n) in the worst case: text made only of openers pushes every character. Text with no brackets at all uses O(1).

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Stack and the other approaches, on a scale where each line up is 10 times more steps.
  • Stack, One counter O(n)
  • Repeatedly delete adjacent pairs O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Stack101,0001 million
One counter101,0001 million
Repeatedly delete adjacent pairs1001 million1 trillion

Inputs that need care

5 tricky inputs
An empty string: text = ""
The loop never runs, the stack is empty, and the function returns true. Nothing opened means nothing is left open.
Only openers: "((("
Every character is pushed and nothing is popped. The final check sees three items and returns false.
A closer with nothing open: ")("
The first ) finds stack.length === 0 and returns false before the ( is read.
Wrong kind: "(]"
] pops (, but pairs["]"] is [, so it returns false. A counter per kind would miss this.
Very deep nesting: 100,000 ( then 100,000 )
The array grows to 100,000 items and shrinks back, which is fine. A recursive checker could overflow the call stack here; a plain array stack doesn't.

Variations and follow-ups

Twists interviewers add

Report where the error is

Push the index along with the opener, as [char, i]. A closer with nothing open is an error at its own index. Anything left on the stack at the end points to the opener that was never closed, which is what an editor needs to underline.

Fewest insertions to balance one kind of bracket

With only ( and ), the stack holds nothing but (, so a counter can replace it. Count unmatched ) as you go, and add whatever ( remain at the end. With several kinds you need the real stack again.

Tag matching

Push tag names instead of characters. A closing tag </ul> must match the name on top. HTML parsers do this with their stack of open elements, and also use it to recover from missing closing tags.

Recursion as a loop

Any depth-first walk can push the things still to visit instead of calling itself. The array plays the role of the call stack, and the code no longer depends on the engine's stack size limit.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "valid", "balanced", "matching", "nested", "undo", or "the most recent". Any time the newest unfinished thing must be finished first, think of a stack.
  • Say the rule out loud: "the stack holds the openers that are still open, newest on top, so a closer must match the top." That one sentence explains both the push and the pop.
  • Test by hand on an empty string, ")", "((", and a crossed pair like "([)]". They hit the empty-stack check, the final check, and the mismatch check.
  • Expect the follow-up "can you do it in O(1) space?". For one kind of bracket, yes, with a counter. For several kinds, no: you must remember the order of the open kinds, which can take O(n) memory.

Where frontend code uses it

The same idea in real UI code
  • The JavaScript engine's call stack is a stack: each function call pushes a frame, and an error's stack trace lists the frames from the top down.
  • The HTML parser keeps a "stack of open elements" while it reads tags, and uses it to decide which element a closing tag closes.
  • Editors use a stack to match brackets for highlighting and for bracket pair colorization, and undo history is a stack of past states.
  • A depth-first walk of the DOM or a nested menu can use an explicit stack instead of recursion.

Related algorithms