Stacks & Queues

Push, pop, enqueue, dequeue

A stack grows and shrinks from the top. A queue grows at the back and shrinks from the front.

Valid Parentheses

The classic stack problem. Scan left to right — push openers, pop when you find a matching closer. If the stack is empty at the end, the string is valid.

Templates

Stack — valid parentheses

function isValid( s: string) {
  const stack: string[] = []
  const map = { ")": "(", "]": "[", "}{": "{" }

  for (const c of s) {
    if (c in map) {
      if (stack.pop() !== map[c]) return false
    } else {
      stack.push(c)
    }
  }
  return stack.length === 0
}

Queue — BFS level order

function bfs(root: Node) {
  const queue = [root]

  while (queue.length) {
    const node = queue.shift()!
    // process node
    for (const child of node.children)
      queue.push(child)
  }
}