Stacks, queues and deques

A stack is last in, first out, like a pile of plates: you add and remove at the top only. It is how the call stack works, and how you match brackets, undo actions or work out expressions. A queue is first in, first out, like a line at a shop: add at the back, remove from the front.

That is exactly what breadth-first search needs later. A deque (double-ended queue) lets you add and remove at both ends. Every one of these operations should be O(1), and that is where language details catch people out.

Removing from the front of a plain array is O(n), so use a real deque type: deque from Python's collections module, ArrayDeque in Java or deque in C++. In JavaScript, keep an index that marks the front instead of removing items.