I always mix up whether I use a stack or a queue for DFS or BFS. Can someone please provide some intuition about how to remember which algorithm uses which data structure?
16 Answers
Don't remember anything.
Assuming the data structure used for the search is X:
Breadth First = Nodes entered X earlier, have to be generated on the tree first: X is a queue.
Depth First = Nodes entered X later, must be generated on the tree first: X is a stack.
In brief: Stack is Last-In-First-Out, which is DFS. Queue is First-In-First-Out, which is BFS.
An easier way to remember, especially for young students, is to use similar acronym:
BFS => Boy FriendS in queue (for popular ladies apparently).
DFS is otherwise (stack).
You can remember by making an acronym
BQDS
Beautiful Queen has Done Sins.
In Hindi, बहुरानी क्यु दर्द सहा
Here is a simple analogy to remember. In a BFS, you are going one level at a time but in DFS you are going as deep as possible to the left before visiting others. Basically stacking up a big pile of stuff, then analyze them one by one, so if this is STACK, then the other one is queue.
Remember as "piling up", "stacking up", big as possible. (DFS).
if you visually rotate 'q' symbol (as in queue) 180 degrees you will get a 'b' (as in bfs).
Otherwise this is stack and dfs.
Related