Stacks
Last in, first out. One end, three operations, and the structure behind undo, browser history and every function call your program makes.
- State the LIFO rule and why it constrains access to one end
- Perform push, pop and peek
- Recognise stacks in real systems, including the call stack
Finish first
Cost at a glance
- push
- O(1)
- pop
- O(1)
- peek
- O(1)
- search
- O(n)
Topic contents
Lesson 1 of 1
One end only
A stack is deliberately restrictive: you may only add to the top and only remove from the top. That is LIFO, last in, first out. The restriction is the feature, because it makes every operation O(1) and makes the structure impossible to misuse.
You have used one all day without noticing. Ctrl+Z undoes your most recent action first. The browser back button returns to the page you visited most recently. And when a function calls a function, the call stack remembers where to return, the deepest call finishes first.
Stack operations
Push, pop and peek on a vertical stack, with the top pointer always visible.
Stack: last in, first out
push / pop / peek all O(1)Start
Peek reads the top item without removing it.
Worked examples
Read the code, then change it
Copy any example into the playground and break it on purpose. That is the fastest way to learn what each line is holding up.
function isBalanced(text) {
const pairs = { ')': '(', ']': '[', '}': '{' };
const stack = [];
for (const char of text) {
if ('([{'.includes(char)) stack.push(char);
else if (char in pairs) {
if (stack.pop() !== pairs[char]) return false;
}
}
return stack.length === 0;
}
console.log(isBalanced('{[()]}'), isBalanced('{[(])}'));Practice
Work these out yourself
No answer key here on purpose: these are the questions worth thinking through before you move on. Open one and work it out.
0/3 attemptedAssessment
Check your understanding
Answer each question, then read the explanation. That is where the learning is.
Finished this topic?
0 of 1 lessons marked done. Marking the topic complete ticks the rest.