These are the notes for JavaScript episode 34, the first episode of the data structures and algorithms (DSA) part of the course. We start with an array of cinema seats and count steps, which gives us Big O. Priya's undo button fails with one variable, so we invent a stack. Counting brackets gives wrong answers, so we check them with a stack. A canteen token line becomes a queue, and we find out why the obvious JavaScript queue (push + shift) gets painfully slow, and fix it with a head pointer. Every output below is real Node.js output (Node 24). Timings like 190 ms change from run to run and machine to machine; the shape (how they grow) is what matters. File paths in stack traces are shortened, and long traces end with ....
Builds on: arrays and push/pop (episode 7), functions (9), JSON.stringify (19), classes (16), throw and errors (13), Array.from (7). Leads to: DSA in JavaScript 2: linked lists and hash maps (35).
What DSA is
A data structure is a way of arranging data so that the job you need is fast. An algorithm is the step-by-step recipe that works on it. The same data can be arranged in different ways, and the right arrangement depends on the job:
| Job | A good structure | Why |
|---|---|---|
| read item number 3 | array | jump straight to an index |
| undo the newest change | stack | newest goes on top, comes off first |
| serve people in arrival order | queue | oldest at the front, comes off first |
| find a phone number by name | hash map (episode 35) | turn the name into a position |
Arrays: the cinema row
Seats in a cinema row sit side by side, in order, and each has a number. That's an array: items in order, each with an index starting at 0.
| At the cinema | In JavaScript |
|---|---|
| numbered seats in a row | an array |
| ticket says "seat 3": walk straight there | seats[3]: one step |
| "where is Arjun?": check every face | a loop that checks each item |
const seats = ["Asha", "Ravi", "Neha", "Priya", "Arjun"];
console.log(seats[3]);
let steps = 0;
function findSeat(list, name) {
for (let i = 0; i < list.length; i++) {
steps++;
if (list[i] === name) return i;
}
return -1;
}
console.log(findSeat(seats, "Arjun"), "steps:", steps);
const big = Array.from({ length: 1000000 }, (_, i) => `P${i}`);
steps = 0;
console.log(big[999999]);
console.log(findSeat(big, "P999999"), "steps:", steps);
Output:
Priya
4 steps: 5
P999999
999999 steps: 1000000
By index: one step, whether there are 5 seats or a million. By name: one step per seat, a million steps for a million seats.
Big O: how the steps grow
Big O notation describes how the number of steps an algorithm takes grows when the input grows. It ignores seconds (computers differ) and small constant details. The input size is called n.
| Big O | Name | Example from today | n = 1,000 | n = 1,000,000 |
|---|---|---|---|---|
| O(1) | constant | seats[3], push, pop |
1 | 1 |
| O(n) | linear | findSeat, shift, unshift, includes |
1,000 | 1,000,000 |
| O(n²) | quadratic | shift() inside a loop over n items |
1,000,000 | 1,000,000,000,000 |
How to read it: double n, and an O(1) job stays the same, an O(n) job doubles, an O(n²) job becomes four times bigger.
The cost of common array methods
| Method | What it does | Big O | Why |
|---|---|---|---|
arr[i] |
read by index | O(1) | jump straight to the slot |
push(x) |
add at the end | O(1) (on average) | nothing else moves |
pop() |
remove from the end | O(1) | nothing else moves |
shift() |
remove from the front | O(n) | every other item moves one place left |
unshift(x) |
add at the front | O(n) | every other item moves one place right |
includes, indexOf, find |
search by value | O(n) | checks items one by one |
splice(i, 1) |
remove from the middle | O(n) | items after i move |
Inventing a stack: Priya's undo button
Priya is building a small notes app, and every app needs undo (Ctrl + Z). Her first idea: before each change, remember the previous text in one variable.
let text = "";
let previous = "";
function type(word) {
previous = text;
text += word;
}
function undo() {
text = previous;
}
type("Hello ");
type("dear ");
type("Ravi");
console.log(text);
undo();
console.log(text);
undo();
console.log(text);
Output:
Hello dear Ravi
Hello dear
Hello dear
The second undo did nothing. Why: one variable remembers one thing. Typing "Ravi" overwrote previous, so older versions were lost. We need to remember every version, and undo the newest one first.
The pile of plates
| In the kitchen | In code |
|---|---|
| put a washed plate on top | push: add to the top |
| take the top plate, never one from the middle | pop: remove from the top |
| look at the top plate without taking it | peek: read the top |
The last plate put on is the first one taken off: last in, first out, LIFO. A structure with this rule is a stack. A JavaScript array used only with push and pop is a stack, and both are O(1).
let text = "";
const history = [];
function type(word) {
history.push(text);
text += word;
}
function undo() {
text = history.pop();
}
type("Hello ");
type("dear ");
type("Ravi");
console.log(text);
for (let i = 1; i <= 4; i++) {
undo();
console.log(`undo ${i}:`, JSON.stringify(text));
}
type("Hi");
console.log(text);
Output:
Hello dear Ravi
undo 1: "Hello dear "
undo 2: "Hello "
undo 3: ""
undo 4: undefined
undefinedHi
Undo 1 to 3 bring back every version, newest first. Undo 4 is a silent bug: pop() on an empty array returns undefined (it does not throw), and undefined + "Hi" is the string "undefinedHi".
A Stack class that fails loudly
class Stack {
constructor() {
this.items = [];
}
push(x) {
this.items.push(x);
}
pop() {
if (this.isEmpty()) throw new Error("Stack is empty");
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
}
const plates = new Stack();
plates.push("plate 1");
plates.push("plate 2");
plates.push("plate 3");
console.log(plates.peek());
console.log(plates.pop(), plates.pop(), plates.pop());
plates.pop();
Output:
plate 3
plate 3 plate 2 plate 1
/home/user/main.js:9
if (this.isEmpty()) throw new Error("Stack is empty");
^
Error: Stack is empty
at Stack.pop (/home/user/main.js:9:31)
at Object.<anonymous> (/home/user/main.js:25:8)
...
| Operation | What it does | Big O |
|---|---|---|
push(x) |
put x on top |
O(1) |
pop() |
remove and return the top (throws if empty) | O(1) |
peek() |
return the top without removing it | O(1) |
isEmpty() |
is there anything on the stack? | O(1) |
Where stacks are used: undo/redo, the browser's back button, checking brackets, and JavaScript itself: every function call goes on the call stack, and returning pops it.
The bracket checker (a classic interview problem)
Problem: given a string, are its brackets balanced? Balanced means every opening bracket (, [, { is closed by the same type, in the right order.
| String | Balanced? | Why |
|---|---|---|
(a + b) * [c] |
yes | every bracket closes properly |
(] |
no | wrong type |
)( |
no | closed before it opened |
{[}] |
no | [ is closed by } |
(( |
no | never closed |
{[()]} |
yes | nested properly |
Attempt 1: counting (wrong)
function isBalanced(s) {
let open = 0;
for (const ch of s) {
if ("([{".includes(ch)) open++;
if (")]}".includes(ch)) open--;
}
return open === 0;
}
for (const s of ["(a + b) * [c]", "(]", ")(", "{[}]"]) {
console.log(s, "->", isBalanced(s));
}
Output:
(a + b) * [c] -> true
(] -> true
)( -> true
{[}] -> true
Three wrong answers. Why: a count only knows how many brackets are open, not their order or type. The bracket that opened last must close first: last in, first out. A stack.
Attempt 2: a stack (correct)
- Opening bracket: push it.
- Closing bracket: pop the top. It must be the matching opener; if not (or the stack was empty, so
pop()givesundefined), returnfalse. - At the end, the stack must be empty, otherwise something was never closed.
const pairs = { ")": "(", "]": "[", "}": "{" };
function isBalanced(s) {
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;
}
for (const s of ["(a + b) * [c]", "(]", ")(", "{[}]", "((", "{[()]}"]) {
console.log(s, "->", isBalanced(s));
}
Output:
(a + b) * [c] -> true
(] -> false
)( -> false
{[}] -> false
(( -> false
{[()]} -> true
Trace of {[}]:
| Character | Action | Stack after |
|---|---|---|
{ |
push | { |
[ |
push | { [ |
} |
pop gives [, but } needs { |
return false |
Complexity: each character is pushed or popped at most once: O(n) time, and up to O(n) extra space for the stack.
Inventing a queue: the canteen token line
| At the canteen | In code |
|---|---|
| new people join at the back | enqueue: add at the back |
| the counter serves from the front | dequeue: remove from the front |
First in, first out, FIFO: a queue. Used for printer jobs, chat messages, requests waiting for a server, and breadth-first search (episode 36).
The obvious queue: push + shift
const line = [];
line.push("Token 1");
line.push("Token 2");
line.push("Token 3");
console.log("Serving", line.shift());
console.log("Serving", line.shift());
console.log("Still waiting:", line);
Output:
Serving Token 1
Serving Token 2
Still waiting: [ 'Token 3' ]
It works. Now measure it:
function serveAll(n) {
const line = [];
for (let i = 1; i <= n; i++) line.push(i);
const start = performance.now();
while (line.length > 0) line.shift();
return Math.round(performance.now() - start) + " ms";
}
console.log("50,000 people:", serveAll(50000));
console.log("100,000 people:", serveAll(100000));
Output (one run; your numbers will differ):
50,000 people: 190 ms
100,000 people: 777 ms
Twice the people, about four times the time: the O(n²) shape. Why: every shift() moves everyone still waiting one place forward. Serving n people moves about n × n / 2 items.
performance.now() returns a high-resolution time in milliseconds; the difference between two calls is how long the code in between took.
The fix: move the counter, not the people
Keep a number head: the index of the person at the front. dequeue reads items[head] and adds one to head. Nobody moves.
class Queue {
constructor() {
this.items = [];
this.head = 0;
}
enqueue(x) {
this.items.push(x);
}
dequeue() {
if (this.isEmpty()) return undefined;
const x = this.items[this.head];
this.items[this.head] = undefined;
this.head++;
return x;
}
isEmpty() {
return this.head === this.items.length;
}
}
function serveAll(n) {
const line = new Queue();
for (let i = 1; i <= n; i++) line.enqueue(i);
const start = performance.now();
while (!line.isEmpty()) line.dequeue();
return Math.round(performance.now() - start) + " ms";
}
console.log("100,000 people:", serveAll(100000));
console.log("1,000,000 people:", serveAll(1000000));
Output (one run):
100,000 people: 8 ms
1,000,000 people: 3 ms
A million people in a few milliseconds (the second number can even be smaller, because the JavaScript engine has optimised the code by then). Setting the served slot to undefined lets the garbage collector free the item. A production queue would also compact the array now and then (for example, when head passes half the length, items = items.slice(head) and head = 0) so the array doesn't grow forever.
| Operation | push + shift queue | head-pointer Queue |
|---|---|---|
| enqueue | O(1) | O(1) |
| dequeue | O(n) | O(1) |
| serve n people | O(n²) | O(n) |
Stack vs queue
| Stack | Queue | |
|---|---|---|
| rule | last in, first out (LIFO) | first in, first out (FIFO) |
| add | push (top) |
enqueue (back) |
| remove | pop (top) |
dequeue (front) |
| real life | a pile of plates | a canteen token line |
| used for | undo, back button, brackets, the call stack, depth-first search | tokens, printers, messages, servers, breadth-first search |
Ask one question: should the newest or the oldest go first?
Common mistakes (and what really happens)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
one previous variable for undo |
the 2nd undo does nothing | one variable remembers one thing | a stack of versions |
history.pop() on an empty array |
undefined, then "undefinedHi" |
pop() on [] returns undefined, it doesn't throw |
check isEmpty(), or throw new Error("Stack is empty") |
| counting brackets | ")(" -> true, "{[}]" -> true |
a count forgets order and type | push openers, pop and compare |
while (q.length) q.shift(); on big data |
100,000 items take hundreds of ms | shift is O(n), the loop is O(n²) |
a head pointer |
const s = Stack(); |
TypeError: Class constructor Stack cannot be invoked without 'new' |
a class must be called with new |
new Stack() |
peek() with items[0] |
returns the oldest plate | the top of an array-stack is the end | items[items.length - 1] (or items.at(-1)) |
Mini project: Priya's editor with undo and redo
Add redo: undo pushes the current text onto a second stack, redo pops it back. Typing something new clears the redo stack (just like real editors).
let text = "";
const undoStack = [];
const redoStack = [];
function type(word) {
undoStack.push(text);
redoStack.length = 0;
text += word;
}
function undo() {
if (undoStack.length === 0) return;
redoStack.push(text);
text = undoStack.pop();
}
function redo() {
if (redoStack.length === 0) return;
undoStack.push(text);
text = redoStack.pop();
}
type("Hello ");
type("dear ");
type("Ravi");
undo();
undo();
console.log(JSON.stringify(text));
redo();
console.log(JSON.stringify(text));
type("Neha");
redo();
console.log(JSON.stringify(text));
Output:
"Hello "
"Hello dear "
"Hello dear Neha"
The last redo() does nothing, because typing "Neha" cleared the redo stack.
Practice
1. Reverse a string using a stack.
Solution
function reverse(s) {
const stack = [];
for (const ch of s) stack.push(ch);
let out = "";
while (stack.length > 0) out += stack.pop();
return out;
}
console.log(reverse("chai"));
console.log(reverse("SyntaxPilot"));
Output:
iahc
toliPxatnyS
Push every character, then pop them: the last one comes out first. O(n) time and space.
2. Give the Queue class a peek() method and a size getter.
Solution
class Queue {
constructor() {
this.items = [];
this.head = 0;
}
enqueue(x) {
this.items.push(x);
}
dequeue() {
if (this.isEmpty()) return undefined;
const x = this.items[this.head];
this.items[this.head] = undefined;
this.head++;
return x;
}
peek() {
return this.isEmpty() ? undefined : this.items[this.head];
}
isEmpty() {
return this.head === this.items.length;
}
get size() {
return this.items.length - this.head;
}
}
const q = new Queue();
q.enqueue("Token 1");
q.enqueue("Token 2");
q.enqueue("Token 3");
console.log(q.peek(), q.size);
q.dequeue();
console.log(q.peek(), q.size);
Output:
Token 1 3
Token 2 2
get size() is a getter: you read it like a property (q.size, no brackets), but it runs a function.
3. Bracket checker: report the position of the first error (-1 if balanced). For a bracket that is never closed, report where it opened.
Solution
const pairs = { ")": "(", "]": "[", "}": "{" };
function firstError(s) {
const stack = [];
for (let i = 0; i < s.length; i++) {
const ch = s[i];
if ("([{".includes(ch)) stack.push(i);
else if (ch in pairs) {
if (stack.length === 0 || s[stack.pop()] !== pairs[ch]) return i;
}
}
return stack.length === 0 ? -1 : stack[0];
}
for (const s of ["(a + b) * [c]", "(]", ")(", "{[}]", "((", "{[()]}"]) {
console.log(JSON.stringify(s), "->", firstError(s));
}
Output:
"(a + b) * [c]" -> -1
"(]" -> 1
")(" -> 0
"{[}]" -> 2
"((" -> 0
"{[()]}" -> -1
The trick: push the index instead of the character, so you can still look the character up (s[index]) and report where it was.
4. Which structure? For each, stack or queue: (a) the browser back button, (b) a printer with 20 jobs, (c) undo in Excel, (d) customers on a support helpline.
Solution
(a) stack: the newest page goes back first. (b) queue: the oldest job prints first. (c) stack. (d) queue: first caller, first served.
Quick quiz
const s = [];
s.push(1);
s.push(2);
s.push(3);
s.pop();
s.push(4);
console.log(s.pop(), s.pop());
A. 4 2 B. 3 4 C. 1 2 D. 4 3
Answer
A: 4 2. After the pushes the stack is [1, 2, 3]; pop() removes 3, giving [1, 2]; push(4) gives [1, 2, 4]. Then pop() gives 4 and the next pop() gives 2. Last in, first out.
Interview questions
- What is the difference between a stack and a queue? A stack is LIFO (add and remove at the same end, the top); a queue is FIFO (add at the back, remove from the front).
- Why is
shift()a bad way to dequeue in JavaScript? It is O(n): every remaining item moves one place. In a loop over n items that becomes O(n²). Use a head index (or a linked list, episode 35). - What is the time complexity of the balanced brackets check? O(n) time, O(n) space in the worst case (for example, a string of only opening brackets).
- What does
[].pop()return?undefined, it does not throw. That's why a careful stack checksisEmpty()first. - What does Big O measure? How the number of steps (or memory) grows as the input size n grows, ignoring constant factors. It does not measure seconds.
- Name places where JavaScript itself uses a stack and a queue. The call stack holds running function calls; the task queue (episode 24, the event loop) holds callbacks waiting to run.
- How would you implement a queue using two stacks? Push onto an "in" stack; to dequeue, if the "out" stack is empty, pop everything from "in" onto "out", then pop from "out". Each item moves at most twice, so it's O(1) on average.
Glossary
| Term | Meaning | Example |
|---|---|---|
| data structure | a way of arranging data so a job is fast | array, stack, queue |
| algorithm | a step-by-step recipe that solves a problem | the bracket checker |
| DSA | data structures and algorithms | this part of the course |
| array | items in order, each with an index starting at 0 | ["Asha", "Ravi"] |
| index | the position number of an item in an array | seats[3] |
| n | the size of the input | 1,000,000 seats |
| Big O | how the steps grow when n grows | O(1), O(n), O(n²) |
| O(1), constant time | the same steps for any n | arr[3], push, pop |
| O(n), linear time | steps grow in step with n | searching an array |
| O(n²), quadratic time | n steps, n times | shift() in a loop |
| stack | last in, first out (LIFO) | a pile of plates, undo |
| LIFO | last in, first out | the newest plate comes off first |
| push | add to the top of a stack (or end of an array) | history.push(text) |
| pop | remove and return the top of a stack | history.pop() |
| peek | read the top without removing it | items[items.length - 1] |
| queue | first in, first out (FIFO) | a canteen token line |
| FIFO | first in, first out | token 1 is served first |
| enqueue | add at the back of a queue | q.enqueue("Token 4") |
| dequeue | remove and return the front of a queue | q.dequeue() |
| head pointer | an index that marks the front of a queue | this.head |
| balanced brackets | every opener closed by the same type, in order | {[()]} |
| call stack | JavaScript's stack of running function calls | the stack in an error trace |
| getter | a method read like a property | get size() → q.size |
performance.now() |
a high-resolution time in milliseconds | timing serveAll |
| undo / redo | going back / forward through saved versions | two stacks |
Summary
- A data structure arranges data so the job you need is fast; Big O says how the steps grow with n.
- Arrays: index access O(1), search O(n), adding or removing at the front O(n), at the end O(1).
- One variable can't undo twice. A stack (LIFO:
push,pop,peek) keeps every version, newest first. Check for empty, orpop()quietly returnsundefined. - Balanced brackets: push openers, pop and compare on closers, end empty. O(n).
- A queue (FIFO:
enqueue,dequeue) serves the oldest first.push+shiftis O(n²) for n people; a head pointer makesdequeueO(1). - Next: linked lists and hash maps, for fast inserts at the front and finding things by name in one step.