SyntaxPilot
Courses/JavaScript/Lesson 34
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript · Lesson 34 of 40

DSA in JS 1: arrays, stacks, queues

queued

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)

  1. Opening bracket: push it.
  2. Closing bracket: pop the top. It must be the matching opener; if not (or the stack was empty, so pop() gives undefined), return false.
  3. 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

  1. 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).
  2. 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).
  3. 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).
  4. What does [].pop() return? undefined, it does not throw. That's why a careful stack checks isEmpty() first.
  5. 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.
  6. 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.
  7. 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, or pop() quietly returns undefined.
  • Balanced brackets: push openers, pop and compare on closers, end empty. O(n).
  • A queue (FIFO: enqueue, dequeue) serves the oldest first. push + shift is O(n²) for n people; a head pointer makes dequeue O(1).
  • Next: linked lists and hash maps, for fast inserts at the front and finding things by name in one step.