Stacks, queues and linked lists · Lesson 11 of 23
Stacks and monotonic stacks
Last in, first out: brackets, undo, and "the next greater number".
A stack is like a pile of plates: add on top (push), remove from the top (pop). The last thing in is the first out (LIFO). In JavaScript a plain array is a ready-made stack: push and pop are both O(1).
Stacks are everywhere: the browser's Back button, undo, and the call stack that runs your functions.
// Balanced brackets: every closer must match the most recent unclosed opener
function balanced(s) {
const pairs = { ")": "(", "]": "[", "}": "{" }
const stack = []
for (const ch of s) {
if ("([{".includes(ch)) stack.push(ch)
else if (ch in pairs) {
if (stack.pop() !== pairs[ch]) return false
}
}
return stack.length === 0
}
console.log(balanced("{[()]}"), balanced("([)]"), balanced("(("))- ▶const stack = []
- 2stack.push("{")
- 3stack.push("[")
- 4stack.pop()
- 5stack.push("(")
- 6console.log(stack.join(""))
Variables
| stack | [] |
Output
Monotonic stack: "the next bigger number"
A classic question: for each day, how many days until a warmer one? The simple solution is O(n²). The clever one: a stack of days still waiting for a warmer day, with temperatures decreasing from bottom to top. When a day warmer than the top arrives, it's that day's answer: pop it and repeat.
function warmerDays(temps) {
const wait = new Array(temps.length).fill(0)
const stack = [] // indexes, temperatures decreasing
for (let i = 0; i < temps.length; i++) {
while (stack.length && temps[i] > temps[stack[stack.length - 1]]) {
const day = stack.pop()
wait[day] = i - day
}
stack.push(i)
}
return wait
}
console.log(warmerDays([30, 32, 31, 29, 33, 30]))What's the output?
const stack = [1, 2, 3] stack.push(4) stack.pop() stack.pop() console.log(stack[stack.length - 1])
What will this code print?
Exercise
Write evalPostfix(tokens) to evaluate a postfix expression (["2","1","+","3","*"] = (2+1)×3). Operators are + - * only. It must print 9 4.
Expected output: 9 4
function evalPostfix(tokens) {
}
console.log(evalPostfix(["2", "1", "+", "3", "*"]), evalPostfix(["10", "2", "3", "*", "-"]))Practise on real problems
Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.
Learn more from
Played 0 of 2 games
Sign in to save your progress and earn XP.