When solving a maze, finding the shortest route, or searching a network, a computer often has many possible paths to explore.

The big question becomes:

Which path should be checked next?

That decision is controlled by two important classes:

• StackFrontier
• QueueFrontier

These small structures determine how nodes are explored, and they power two famous search algorithms:

• DFS = Depth-First Search
• BFS = Breadth-First Search

---

What Is a Frontier?

A frontier is a collection of nodes waiting to be explored.

Think of it as a to-do list of possible next moves.

Already Explored  ✅
Currently Waiting  ⏳  ← Frontier
Not Yet Discovered ❓

So the frontier stores nodes that the algorithm has found, but not examined yet.

---

Why Frontier Matters

Suppose you are in a maze.

You can go:

• Left
• Right
• Forward

All three choices are added to frontier.

Now the system must choose:

Which one should I check first?

That choice changes everything.

---

1. StackFrontier

A stack follows:

Last In, First Out (LIFO)

The newest node added is explored first.

Like a stack of plates.

• Add new plate on top
• Remove top plate first

---

Visual Example

Top → [C]
      [B]
Bottom[A]

Remove next:

C

---

How It Powers DFS

Depth-First Search uses stack behavior.

It keeps going deep into one path before returning.

---

Maze Example

Start
 ├── Left
 ├── Right
 └── Forward

DFS may choose:

Start → Left → Left → Left → Dead End

Then backtrack.

---

Graphic

DFS Path

Start
  |
  v
 A
 |
 v
 B
 |
 v
 C

Explore deeply first.

---

Use Cases of DFS (StackFrontier)

• Maze exploration
• Puzzle solving
• Backtracking problems
• File system traversal
• Detecting cycles in graphs
• Sudoku solvers

---

Example Python Idea

frontier.add(A)
frontier.add(B)
frontier.add(C)

remove() → C

Newest item first.

---

2. QueueFrontier

A queue follows:

First In, First Out (FIFO)

The oldest node added is explored first.

Like people waiting in line.

First person enters first, leaves first.

---

Visual Example

Front → [A] [B] [C] ← Back

Remove next:

A

---

How It Powers BFS

Breadth-First Search uses queue behavior.

It explores all nearby nodes first, then deeper levels.

---

Tree Example

        Start
      /   |   \
     A    B    C
    / \
   D   E

BFS order:

Start → A → B → C → D → E

---

Graphic

Level 1: Start
Level 2: A B C
Level 3: D E

Explore by layers.

---

Use Cases of BFS (QueueFrontier)

• Shortest path in unweighted graphs
• Social connection search
• Nearest location search
• Web crawling
• Network broadcasting
• Minimum moves puzzles

---

Example Python Idea

frontier.add(A)
frontier.add(B)
frontier.add(C)

remove() → A

Oldest item first.

---

Side-by-Side Comparison

Feature	StackFrontier	QueueFrontier
Rule	Last In First Out	First In First Out
Search Type	DFS	BFS
Style	Go deep first	Explore wide first
Memory Use	Often lower	Often higher
Shortest Path Guaranteed?	No	Yes (unweighted graph)
Good For	Backtracking	Nearest / shortest route

---

Real World Example: Google Maps Style Thinking

Suppose you need to reach Delhi.

DFS Thinking

Pune → Mumbai → Goa → Kerala → ...

May go deep in wrong direction.

BFS Thinking

Pune → Nearby cities first

Finds shortest hops faster.

---

Real World Example: Social Media

Find connection between Tom Hanks and Emma Watson.

BFS is ideal because it checks shortest chain of mutual links first.

---

Why These Classes Matter

Without StackFrontier or QueueFrontier, search becomes random.

These classes give discipline and strategy.

They decide:

• what gets explored next
• how fast solution is found
• whether shortest path is guaranteed
• how much memory is used

---

Simplified CS50 Style Structure

class StackFrontier():
    def add(self, node):
        ...

    def remove(self):
        # remove newest

class QueueFrontier(StackFrontier):
    def remove(self):
        # remove oldest

Same container, different removal rule.

That small difference changes the algorithm.

---

Deep Insight

Search intelligence often comes not from smarter nodes…

…but from choosing which node to inspect next.

That is why frontier classes are powerful.

---

Beginner