Algorithms Lesson 4: Stacks & Queues

Stacks (LIFO) and queues (FIFO) are essential data structures used in parsing, undo operations, BFS/DFS, and many more algorithms.

Stack (LIFO — Last In First Out)

class Stack {
  constructor() { this.items = []; }
  push(item) { this.items.push(item); }         // O(1)
  pop() { return this.items.pop(); }             // O(1)
  peek() { return this.items[this.items.length - 1]; } // O(1)
  isEmpty() { return this.items.length === 0; } // O(1)
  size() { return this.items.length; }           // O(1)
}

// Classic stack problem: valid parentheses
function isValid(s) {
  const stack = [];
  const map = { ")": "(", "}": "{", "]": "[" };
  for (const c of s) {
    if (["(", "{", "["].includes(c)) stack.push(c);
    else if (stack.pop() !== map[c]) return false;
  }
  return stack.length === 0;
}
isValid("({[]})"); // true
isValid("({)}");   // false

Queue (FIFO — First In First Out)

class Queue {
  constructor() { this.items = []; }
  enqueue(item) { this.items.push(item); }    // O(1)
  dequeue() { return this.items.shift(); }    // O(n) — use linked list for O(1)
  front() { return this.items[0]; }           // O(1)
  isEmpty() { return this.items.length === 0; }
}

// BFS uses a queue!
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const result = [];
  
  while (queue.length) {
    const node = queue.shift();
    result.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}