Understanding the remove() Method in StackFrontier (DFS)

[Rajeev Bagra]

When learning search algorithms like Depth First Search (DFS), one important concept is the frontier.

The frontier stores nodes waiting to be explored.

In a StackFrontier, nodes are removed using LIFO order:

Last In First Out

This means the most recently added node is explored first.

Let’s deeply understand this method:

def remove(self):
    if self.empty():
        raise Exception("empty frontier")
    else:
        node = self.frontier[-1]
        self.frontier = self.frontier[:-1]
        return node

---

First: What is self.frontier?

Usually it is a Python list.

Example:

self.frontier = ["A", "B", "C"]

Think of it like a stack:

Top
 C
 B
 A

The last item added is removed first.

---

Step 1 — Check if frontier is empty

if self.empty():

This usually calls:

def empty(self):
    return len(self.frontier) == 0

So if:

self.frontier = []

then:

raise Exception("empty frontier")

runs.

---

Why raise an exception?

Because removing from an empty list is invalid.

Without this check, Python would produce an error.

---

Step 2 — Access the last node

node = self.frontier[-1]

-1 means:

last element of the list

Example:

self.frontier = ["A", "B", "C"]

Then:

self.frontier[-1]

gives:

"C"

So:

node = "C"

---

Step 3 — Remove the last node

self.frontier = self.frontier[:-1]

This uses list slicing.

---

Understanding [:-1]

It means:

take everything except the last item

Example:

["A", "B", "C"][:-1]

becomes:

["A", "B"]

So the frontier changes from:

["A", "B", "C"]

to:

["A", "B"]

---

Step 4 — Return the removed node

return node

returns:

"C"

---

Full Example

Initial frontier:

self.frontier = ["A", "B", "C"]

Call:

remove()

---

Inside the method

Check empty:

False

continue.

Get last item:

node = "C"

Remove last item:

self.frontier = ["A", "B"]

Return node:

return "C"

---

Final Result

Returned value:

"C"

Remaining frontier:

["A", "B"]

---

Why is this called a Stack?

Because operations happen at the same end.

Items are:

• added to the end
• removed from the end

This creates:

LIFO → Last In First Out

which is the behavior of a stack.

---

DFS vs BFS

DFS (Depth First Search)

Uses a stack.

Removes from the end:

self.frontier[-1]

---

BFS (Breadth First Search)

Uses a queue.

Removes from the front:

self.frontier[0]

This creates:

FIFO → First In First Out

---

Simpler Alternative Using pop()

The same method could be written as:

def remove(self):
    if self.empty():
        raise Exception("empty frontier")

    return self.frontier.pop()

pop() automatically:

• removes the last item
• returns it

But the original version is often used for teaching because it clearly shows:

• indexing
• slicing
• stack mechanics

step by step.

[Author]

Posts