Part 10 · Lesson 38 · read
Stacks
Last in, first out. Examples: valid brackets, a stack that knows its minimum, and working out expressions.
On this page
Last in, first out
A stack is like a pile of plates. You can only add a plate on top, and you can only take a plate from the top. So the plate you put on last is the first one to come off. This rule is called LIFO: last in, first out. In code, a stack is a collection of values where you may only add or remove at one end, called the top. A stack has just three operations. Each one is O(1), which means it takes the same short time however big the stack is:
- push — put a value on top.
- pop — remove and return the top value.
- peek — look at the top value without removing it. Most stacks also have isEmpty, which tells you if the stack has nothing in it.
You have already used a stack, even if you did not know its name. The call stack is a stack. It is the list of function calls that have started but not finished. Recursion (a function that calls itself) relies on it. The most recent function call is the first to finish.
A stack is an array with two rules
JavaScript has no separate stack type, and it does not need one. If you use an array only with push and pop, it is a stack. The end of the array is the top. Both operations are O(1).
const stack = [];stack.push(1); // [1] put on topstack.push(2); // [1, 2]stack.push(3); // [1, 2, 3]console.log(stack[stack.length - 1]); // 3 peek: look at the top without removing itconsole.log(stack.pop()); // 3 remove and return the topconsole.log(stack.pop()); // 2console.log(stack.length); // 1console.log(stack.length === 0); // false (isEmpty)console.log([].pop()); // undefined (popping an empty stack does not throw)unshift adds an item at the front of an array and shift removes the first item. In general they have to move every other item, so they can take O(n) time. Always treat the end as the top. If you write shift on a stack, something is wrong.Matching brackets
Is "([{}])" correctly nested? Think about how you would check it by hand. Every opening bracket waits for its closing bracket. A closing bracket must close the most recent opening bracket that is still open. "The most recent one still waiting" is the top of a stack.
function isValid(s) { const pairs = { ")": "(", "]": "[", "}": "{" }; // closer -> its opener const stack = []; for (const ch of s) { if (ch === "(" || ch === "[" || ch === "{") { stack.push(ch); // an opener waits for its closer } else { if (stack.pop() !== pairs[ch]) return false; // the most recent opener must match } } return stack.length === 0; // anything left over was never closed}console.log(isValid("()[]{}")); // trueconsole.log(isValid("([{}])")); // trueconsole.log(isValid("(]")); // falseconsole.log(isValid("((")); // falseconsole.log(isValid(")")); // falseThere are three ways to fail. The same lines of code handle all three:
(]— the closing bracket does not match the top of the stack.))— a closing bracket arrives when the stack is empty. Thenpop()returnsundefined, which never equals an opening bracket.((— the string ends while opening brackets are still on the stack, so the last check fails.
Traced: ( [ { } ] ]
The stack holds the opening brackets that are still waiting for a closing bracket. The top is the most recent one.
▶const stack = [];2for (const ch of s) {3 if (ch === "(" || ch === "[" || ch === "{") {4 stack.push(ch);5 } else {6 if (stack.pop() !== pairs[ch]) return false;7 }8}9return stack.length === 0;| s | "([{}]]" |
| stack | [] |
How to recognise a stack problem
| If the problem says… | Think… |
|---|---|
| match / nested / balanced | stack of opening brackets |
| undo, backspace, most recent first | stack of actions or characters |
| the inner part must finish before the outer part | stack of unfinished outer parts (decode string) |
| evaluate an expression | stack of operands |
| next greater / smaller element | monotonic stack (a stack whose values are always kept in increasing or decreasing order, Lesson 40) |
| a DFS (depth-first search: follow one path as deep as it goes, then go back) that you want to write without recursion | a stack that you make yourself |
What they have in common: the item you need next is always the most recent one that you have not finished with.
A stack that knows its minimum
Build a stack where getMin() (get the smallest value) is also O(1). Looking through everything for the smallest takes O(n). One stored min variable does not work either, because it becomes wrong when you pop that smallest value. The fix is to store, next to every item, the smallest value among that item and everything below it. When you pop an item, you pop its stored minimum too. So the right answer is always on top.
class MinStack { constructor() { this.items = []; this.mins = []; } // mins[i] = the smallest value among items[0..i] push(x) { this.items.push(x); const prevMin = this.mins.length ? this.mins[this.mins.length - 1] : Infinity; this.mins.push(Math.min(x, prevMin)); } pop() { this.mins.pop(); return this.items.pop(); } top() { return this.items[this.items.length - 1]; } getMin() { return this.mins[this.mins.length - 1]; } // O(1): the answer is always already stored}const m = new MinStack();m.push(5); m.push(3); m.push(7);console.log(m.getMin()); // 3m.pop(); // removes 7console.log(m.getMin()); // 3m.pop(); // removes 3console.log(m.getMin()); // 5The price is O(n) extra space, because you keep a second array of the same length. Every operation stays O(1).
Evaluating postfix expressions
An operator is a symbol such as + or *, and its operands are the numbers it works on. In postfix (also called Reverse Polish) notation, the operator comes after its operands. So you need no brackets and no rules about which operator goes first. For example, 2 1 + 3 * means (2 + 1) * 3. Read from left to right. If you see a number, push it on the stack. If you see an operator, pop two numbers, apply the operator to them, and push the result.
// Postfix (Reverse Polish): the operator comes after its two operands.// "2 1 + 3 *" means (2 + 1) * 3.function evalRPN(tokens) { const stack = []; for (const tok of tokens) { if (tok === "+" || tok === "-" || tok === "*" || tok === "/") { const b = stack.pop(); // the right operand was pushed LAST, so it pops first const a = stack.pop(); if (tok === "+") stack.push(a + b); else if (tok === "-") stack.push(a - b); else if (tok === "*") stack.push(a * b); else stack.push(Math.trunc(a / b)); // division truncates toward zero } else { stack.push(Number(tok)); } } return stack[0];}console.log(evalRPN(["2", "1", "+", "3", "*"])); // 9console.log(evalRPN(["4", "13", "5", "/", "+"])); // 6console.log(evalRPN(["7", "-2", "/"])); // -3 (trunc, not floor)a first and write a − b, you get the wrong sign. Division in this problem cuts off the decimal part (Math.trunc), so it rounds towards zero. Math.floor is different for negative numbers: it rounds down.Nested structure: decode a string
A string like k[text] means "write text k times". For example, "3[a2[c]]" means "repeat three times: a, then c repeated twice". The innermost bracket must finish first. That is LIFO again. When you see [, save the outer part (the text so far and the repeat count) on stacks, and start fresh inside the bracket. When you see ], take the saved outer part back and add the repeated inside text to it.
// "3[a2[c]]" -> "accaccacc"function decodeString(s) { const counts = []; const texts = []; let cur = ""; // the text being built at the current depth let num = 0; // a repeat count being read for (const ch of s) { if (ch >= "0" && ch <= "9") { num = num * 10 + Number(ch); // counts can have several digits } else if (ch === "[") { counts.push(num); // remember the count and the text so far, then start fresh inside the bracket texts.push(cur); num = 0; cur = ""; } else if (ch === "]") { const times = counts.pop(); cur = texts.pop() + cur.repeat(times); // glue the repeated inside onto what came before } else { cur += ch; } } return cur;}console.log(decodeString("3[a]2[bc]")); // aaabcbcconsole.log(decodeString("3[a2[c]]")); // accaccaccconsole.log(decodeString("2[ab]c")); // ababc| Char | cur | num | counts stack | texts stack |
|---|---|---|---|---|
| 3 | "" | 3 | [] | [] |
| [ | "" | 0 | [3] | [""] |
| a | "a" | 0 | [3] | [""] |
| 2 | "a" | 2 | [3] | [""] |
| [ | "" | 0 | [3, 2] | ["", "a"] |
| c | "c" | 0 | [3, 2] | ["", "a"] |
| ] | "acc" | 0 | [3] | [""] |
| ] | "accaccacc" | 0 | [] | [] |
Practice questions
Before you code, say what the stack holds at each moment. That one sentence is the whole idea of the algorithm.
You get a string of ()[]{} characters. Decide whether every bracket is closed by the right type of bracket, in the right order.
Hint 1
Hint 2
Show all 2 solutions with explanations
Remove (), [] and {} (replace them with nothing) again and again, until the string stops changing. If the string ends up empty, it was valid.
function isValid(s) { let prev; do { prev = s; s = s.replace("()", "").replace("[]", "").replace("{}", ""); } while (s !== prev); return s === "";}console.log(isValid("([{}])")); // trueconsole.log(isValid("(]")); // falseIt gives the right answer, but each pass takes O(n) time and there can be O(n) passes. So the worst case is O(n²), which is slow for long strings.
Push each opening bracket. When a closing bracket comes, pop and compare. At the end, the stack must be empty.
function isValid(s) { const pairs = { ")": "(", "]": "[", "}": "{" }; const stack = []; for (const ch of s) { if (ch in pairs) { if (stack.pop() !== pairs[ch]) return false; } else { stack.push(ch); } } return stack.length === 0;}console.log(isValid("()[]{}")); // trueconsole.log(isValid("(]")); // falseconsole.log(isValid("((")); // falseconsole.log(isValid(")")); // falseO(n) time, O(n) space. As a small speed-up, you can reject a string with an odd length straight away.
Use the stack. (LeetCode 20.)
Build a stack with push, pop, top and getMin. All four must take O(1) time.
Hint 1
min variable is not enough. What do you lose when you pop the smallest value?Hint 2
Show all 2 solutions with explanations
Keep a plain stack. getMin looks at every item to find the smallest.
class SlowMinStack { constructor() { this.items = []; } push(x) { this.items.push(x); } pop() { return this.items.pop(); } top() { return this.items[this.items.length - 1]; } getMin() { return Math.min(...this.items); }}const s = new SlowMinStack();s.push(-2); s.push(0); s.push(-3);console.log(s.getMin()); // -3getMin takes O(n) time. Also, passing a very large array into Math.min with ... can even throw a RangeError (JavaScript's error for "too many arguments"). The question asks for O(1).
On each push, also push min(x, current min) (the smaller of the two) onto a second stack. Pop from both stacks together.
class MinStack { constructor() { this.items = []; this.mins = []; } push(x) { this.items.push(x); this.mins.push(this.mins.length ? Math.min(x, this.mins[this.mins.length - 1]) : x); } pop() { this.mins.pop(); return this.items.pop(); } top() { return this.items[this.items.length - 1]; } getMin() { return this.mins[this.mins.length - 1]; }}const s = new MinStack();s.push(-2); s.push(0); s.push(-3);console.log(s.getMin()); // -3s.pop();console.log(s.top()); // 0console.log(s.getMin()); // -2All operations are O(1) and the extra space is O(n). You could also store pairs [value, minSoFar] in one array. It works the same way.
Use the second stack. (LeetCode 155.)
Work out the value of a maths expression written in Reverse Polish Notation. Division cuts off the decimal part (it rounds towards zero).
Hint 1
Hint 2
Show the solution with explanations
Push the numbers. When you see an operator, pop b and then a. Work out a op b and push the result. The answer is the last item left.
function evalRPN(tokens) { const stack = []; for (const t of tokens) { if (t === "+" || t === "-" || t === "*" || t === "/") { const b = stack.pop(), a = stack.pop(); stack.push(t === "+" ? a + b : t === "-" ? a - b : t === "*" ? a * b : Math.trunc(a / b)); } else { stack.push(Number(t)); } } return stack[0];}console.log(evalRPN(["2", "1", "+", "3", "*"])); // 9console.log(evalRPN(["4", "13", "5", "/", "+"])); // 6console.log(evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])); // 22O(n) time, O(n) space. You need Math.trunc for negative numbers. Math.floor(-7 / 2) gives −4, but the question wants −3.
There is only one good approach here. The difficulty is in the details: the order of the two numbers, and cutting off the decimal part. (LeetCode 150.)
Decode a string where k[text] means text repeated k times. Brackets can be inside other brackets.
Hint 1
Hint 2
[, you must save the text built so far and the repeat count.Hint 3
12[a].Show all 2 solutions with explanations
- Read digits into
num. Read letters intocur. - On
[, pushnumandcuron their stacks, then reset both. - On
], pop both values and setcur = oldText + cur.repeat(count).
function decodeString(s) { const counts = [], texts = []; let cur = "", num = 0; for (const ch of s) { if (ch >= "0" && ch <= "9") num = num * 10 + Number(ch); else if (ch === "[") { counts.push(num); texts.push(cur); num = 0; cur = ""; } else if (ch === "]") { cur = texts.pop() + cur.repeat(counts.pop()); } else cur += ch; } return cur;}console.log(decodeString("3[a]2[bc]")); // aaabcbcconsole.log(decodeString("3[a2[c]]")); // accaccaccconsole.log(decodeString("12[x]")); // xxxxxxxxxxxxThe time grows with the length of the output. The space is the nesting depth (how many brackets are inside each other) plus the output.
Write a function that reads until it finds a ] or the end, and then returns the text. Each [ makes the function call itself (a recursive call). The call stack (the list of unfinished calls) does the job of the two stacks.
function decodeString(s) { let i = 0; function read() { let out = "", num = 0; while (i < s.length && s[i] !== "]") { const ch = s[i]; if (ch >= "0" && ch <= "9") { num = num * 10 + Number(ch); i++; } else if (ch === "[") { i++; out += read().repeat(num); num = 0; i++; } // skip "[", read inside, skip "]" else { out += ch; i++; } } return out; } return read();}console.log(decodeString("3[a2[c]]")); // accaccaccSame result and same cost. Pick the one you can write without bugs. The stack version has fewer parts that can go wrong.
Use the two-stack version. (LeetCode 394.)
Two typed strings contain #, which means backspace. Return whether the two final texts are equal.
Hint 1
# removes the most recent character that is still in the text.Show all 2 solutions with explanations
Push each letter. Pop when you see # (popping an empty stack does nothing). Then compare the two results.
function build(s) { const stack = []; for (const ch of s) { if (ch === "#") stack.pop(); else stack.push(ch); } return stack.join("");}function backspaceCompare(s, t) { return build(s) === build(t); }console.log(backspaceCompare("ab#c", "ad#c")); // trueconsole.log(backspaceCompare("a#c", "b")); // falseconsole.log(backspaceCompare("a##c", "#a#c")); // trueO(n + m) time and space.
Walk both strings from the end. Count the backspaces so you know which characters to skip. Compare the characters that remain, one at a time.
function backspaceCompare(s, t) { const next = (str, i) => { let skip = 0; while (i >= 0) { if (str[i] === "#") { skip++; i--; } else if (skip > 0) { skip--; i--; } else break; } return i; // index of the next surviving character, or -1 }; let i = s.length - 1, j = t.length - 1; while (true) { i = next(s, i); j = next(t, j); if (i < 0 || j < 0) return i < 0 && j < 0; // both must run out together if (s[i] !== t[j]) return false; i--; j--; }}console.log(backspaceCompare("ab#c", "ad#c")); // trueconsole.log(backspaceCompare("a##c", "#a#c")); // trueconsole.log(backspaceCompare("a#c", "b")); // falseO(n + m) time, O(1) space. Walking backwards is what makes this work, because a # only affects the characters to its left.
Start with the stack. The two-pointer version is the usual follow-up when the interviewer asks for O(1) space. (LeetCode 844.)
Change an absolute Unix path (a path that starts at the root /) into its shortest standard form (the canonical form).
Hint 1
/. Each piece is a folder name, ., .. or empty.Hint 2
.. undoes the most recent folder. That is a pop.Show the solution with explanations
Ignore empty pieces and .. Pop on .. (if the stack is not empty). Push anything else. Join the stack with /.
function simplifyPath(path) { const stack = []; for (const part of path.split("/")) { if (part === "" || part === ".") continue; if (part === "..") stack.pop(); else stack.push(part); } return "/" + stack.join("/");}console.log(simplifyPath("/home//foo/")); // /home/fooconsole.log(simplifyPath("/a/./b/../../c/")); // /cconsole.log(simplifyPath("/../")); // /O(n) time and space. Popping an empty stack does no harm, so going above the root is handled without extra code.
This is the standard answer. It is a good example of "undo the most recent step". (LeetCode 71.)
Again and again, delete two equal letters that sit next to each other, until there are none left. Return the result.
Hint 1
Show all 2 solutions with explanations
For each letter, check the top of the stack. If it is the same letter, pop it (the pair cancels out). If not, push the letter.
function removeDuplicates(s) { const stack = []; for (const ch of s) { if (stack.length && stack[stack.length - 1] === ch) stack.pop(); else stack.push(ch); } return stack.join("");}console.log(removeDuplicates("abbaca")); // caconsole.log(removeDuplicates("azxxzy")); // ayO(n) time and space. The stack always holds the string so far with no equal letters side by side. That is exactly what the next letter needs to compare with.
Remove one pair at a time with a regex (a pattern for searching text), until nothing matches. The pattern (.)\1 means "any character followed by the same character again".
function removeDuplicates(s) { const re = /(.)\1/; while (re.test(s)) s = s.replace(re, ""); return s;}console.log(removeDuplicates("abbaca")); // caconsole.log(removeDuplicates("azxxzy")); // ayIt works, but it scans the string again after each removal. The worst case is O(n²).
Use the stack. (LeetCode 1047.)
Make it stick
- Say what LIFO means. Give two examples: one from code and one from daily life.
- Explain what the stack holds in the brackets problem. Name the three ways it can fail.
- Explain how MinStack gets an O(1)
getMin, and what this costs. - Explain why the first value that an operator pops is the right number.
Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.
What's next
Lesson 39 turns the rule around. The queue is first in, first out, like people waiting in a line. It also explains why shift() is slow, and it introduces the double-ended queue (a queue you can add to and remove from at both ends).
Practise on LeetCode
Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.
Published by Jainik · Last updated · How these lessons are made
Keep learning
Part of the study guide
Related series