Course contentsShow
← Java
Lesson 1216 of 2,87027. Queue and Deque ImplementationsFree lesson

Depth-First Search with Deque Stack

Apply stack operations using Deque to implement depth-first traversal algorithms for trees and graphs.

Depth-First Search with Deque Stack

What you'll learn: How to use Deque as a stack to implement depth-first traversal of trees and graphs.

Understanding Depth-First Search

Depth-first search (DFS) is an algorithm that explores as far down one branch as possible before backtracking. Think of it like exploring a maze by always taking the first unexplored path, going as deep as possible, then backing up when you hit a dead end.

The key to DFS is the stack: you push nodes/vertices to visit, then pop them off to explore them. Unlike breadth-first search (which uses a queue), DFS naturally uses a stack's LIFO (Last-In-First-Out) behavior.

Why Deque Instead of Stack Class?

As we've learned, Deque is the modern, preferred way to implement stack operations in Java. Using ArrayDeque gives you efficient O(1) push, pop, and peek operations—perfect for DFS.

DFS Implementation Pattern

Here's how DFS works with a Deque stack:

Deque<Node> stack = new ArrayDeque<>();
Set<Node> visited = new HashSet<>();

stack.push(startNode);

while (!stack.isEmpty()) {
    Node current = stack.pop();
    
    if (visited.contains(current)) {
        continue; // Skip already visited nodes
    }
    
    visited.add(current);
    // Process current node here
    
    // Push unvisited neighbors (reverse order for left-to-right traversal)
    for (Node neighbor : current.neighbors) {
        if (!visited.contains(neighbor)) {
            stack.push(neighbor);
        }
    }
}

The visited set prevents infinite loops in graphs with cycles. Each node is processed only once, and we explore all reachable nodes by going deep first.

Key Takeaway: Deque with push(), pop(), and peek() operations provides the perfect stack structure for implementing depth-first search algorithms, allowing you to explore trees and graphs by diving deep before exploring siblings.