Common Queue Patterns
Explore how to apply core queue patterns like breadth-first search for graph traversals and monotonic queues for sliding window problems in C++. Understand when and how to choose these patterns to solve interview problems effectively, improving your coding interview readiness.
Recognizing a queue as the right data structure is only the first step. The next step is knowing which pattern to apply. This lesson covers the two most important queue patterns in C++ coding interviews: breadth-first search and the monotonic queue. They represent two fundamentally different uses of a queue, and together they cover the majority of queue-based interview problems.
Interview lens: The signal for both patterns is usually recognizable within the first minute of reading a problem. A problem about layer-by-layer exploration or shortest path is almost always BFS. A problem about the maximum or minimum within a sliding window is almost always a monotonic queue. Building that reflex is what this lesson is about.
Breadth-first search
The BFS pattern uses a queue to explore nodes layer by layer. In C++, this usually means using std::queue. We push the starting node, then repeatedly take the front node, pop it, process it, and push its unvisited neighbors. Because we add and remove from opposite ends, we always process nodes in the order we discovered them, which guarantees that we visit every node at the current depth before moving to the next.
Trap (not marking nodes as visited before pushing them): Nodes must be marked as visited at the moment they are pushed into the queue, not when they are popped. Marking on pop allows the same node to be pushed multiple times before it is processed, which leads to incorrect results and, in graph problems, can cause infinite loops.
This ordering property is what makes BFS the right pattern for shortest-path problems in unweighted graphs and level-order traversal in trees. A stack-based DFS explores as deeply as possible before backtracking. BFS spreads outward uniformly, which is exactly what these problems need.
Time and space complexity
Time
...