Data structures and patterns · Question 37 of 50

Stack or queue? Where are they used?

What they're checking

The basics, and seeing them in real systems.

The answer

A stack is last in, first out: push and pop at the same end, both O(1). It is the call stack, undo, the browser's back button, matching brackets and depth-first search.

A queue is first in, first out: add at the back, take from the front. It is job queues, the event loop's task queue, printing, breadth-first search and paced sending. A deque allows both ends; a priority queue (a heap) serves the most urgent first instead of the oldest.

function balanced(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' }
  const stack = []
  for (const ch of s) {
    if ('([{'.includes(ch)) stack.push(ch)
    else if (pairs[ch] && stack.pop() !== pairs[ch]) return false
  }
  return stack.length === 0
}

The picture

stack (LIFO):  push 1, 2, 3 → [1 2 3] → pop → 3
queue (FIFO):  add 1, 2, 3  → [1 2 3] → take → 1
The follow-up they'll ask

How do you build a queue from two stacks?

Show the answer

Push onto stack A. To take one, if B is empty move everything from A to B, then pop B. Each item moves once, so it is O(1) on average.

Your progress stays on this device.