Core Patterns
Stacks & queues
Lesson 4 of 5
What you'll learn
- Distinguish last-in-first-out from first-in-first-out and when each fits
- Use a stack to match, parse, and undo
- Reach for a queue when fairness and order of arrival matter
Stacks and queues are not about storage; they are about the order in which work comes back out. A stack is last-in-first-out: the most recent item is the next one handled. A queue is first-in-first-out: items leave in the order they arrived. Choosing the right discipline often makes a hard problem trivial, because the structure enforces the order you need for free.
// stack: push and pop from the end of an array
const stack = [];
stack.push("a"); stack.push("b");
stack.pop(); // "b" — last in, first out
// queue: push to the end, take from the front
const queue = [];
queue.push("a"); queue.push("b");
queue.shift(); // "a" — first in, first out
When to reach for a stack
Stacks shine whenever the most recent unfinished thing must be resolved first. That covers matching brackets, parsing expressions, evaluating undo history, and the call stack itself. The pattern is: push when you open something, pop when you close it, and check that what you pop matches what you expected. If the stack is not empty at the end, something was left open.
When to reach for a queue
Queues model fairness and breadth. Anything processed in arrival order is a queue: task schedulers, request buffers, and breadth-first traversal, which you will meet in the next lesson. The mental cue is "first come, first served." Note that array shift is order n in JavaScript because it reindexes; for hot paths use a real ring buffer or a head pointer, but for interview-sized inputs an array is fine.
Match, do not just count
A balanced-bracket check that only counts opens and closes will wrongly accept a string like a closing bracket following an open square bracket. You must verify each closer matches the most recent opener, which is exactly what popping the stack gives you.
The challenge implements a balanced-parentheses checker that supports three bracket types using a stack to ensure every closer matches the most recent opener.
Run it. Push each opening bracket, and on each closing bracket pop and confirm it matches the most recent opener.
Why does a stack correctly validate nested brackets when simple counting does not?
Next: trees and graphs, where breadth-first traversal puts the queue to work.
Saved on this device. Sign in to sync your progress everywhere.