Javaでキュー、スタックを使った木構造のBFS,DFS

インタフェースとArrayList,LinkedListを使ってみたかったので、ちょうどい題材としてキューとスタックにインタフェースを組み合わせて木構造を幅優先探索と深さ優先探索しました。

/
  bin
    ar
    diff
    od
  usr
    home
      userA
      userB
      userC
  etc
  var

// スタックとキューを使った木構造の深さ優先、幅優先探索
// LinkedListの

import java.util.LinkedList;
import java.util.ArrayList;

public class Traverse {
    public static void main(String[] args) {
        // DFS
        System.out.println("-- DFS");
        traversal(new StackHandler());

        // BFS
        System.out.println("-- BFS");
        traversal(new QueueHandler());
    }
    static void traversal(ContainerHandler handler){ // インタフェース変数(interface variable)というらしい
        Node node = TreeBuilder.build();
        ContainerProxy proxy = new ContainerProxy(handler);
        proxy.put(node);
        while (!proxy.empty()){
            node = proxy.fetch();
            System.out.println(node.getValue());
            // add all children to proxy
            for (int i = 0; i < node.size(); i++){
                proxy.put(node.at(i));
            }
        }
    }
}


// スタック、キュー関連
// はじめてのインタフェース
interface ContainerHandler {
    public Node fetch(LinkedList<Node> lst);
}

class StackHandler implements ContainerHandler
{
    public Node fetch(LinkedList<Node> lst){
        return lst.removeFirst();
    }
}

class QueueHandler implements ContainerHandler
{
    public Node fetch(LinkedList<Node> lst){
        return lst.removeLast();
    }
}

class ContainerProxy {
    private ContainerHandler handler;
    private LinkedList<Node> cont;
    ContainerProxy(ContainerHandler h){
        handler = h;
        cont = new LinkedList<Node>();
    }
    void put(Node n){
        cont.addFirst(n);
    }
    Node fetch(){
        return handler.fetch(cont);
    }
    boolean empty(){
        return cont.size() == 0;
    }
}

//
// 木構造関連
//

class TreeBuilder {
    public static Node build(){
        // 木構造のビルド
        // root
        //     bin
        //         ar
        //         diff
        //         od
        //     usr
        //         home
        //             userA
        //             userB
        //             userC
        //     etc
        //     var
        Node root = new Node("/");

        Node bin = new Node("bin");
        bin.add(new Node("ar"));
        bin.add(new Node("diff"));
        bin.add(new Node("od"));

        Node home = new Node("home");
        home.add(new Node("userA"));
        home.add(new Node("userB"));
        home.add(new Node("userC"));
        Node usr = new Node("usr");
        usr.add(home);
        root.add(usr);

        root.add(bin);
        root.add(new Node("etc"));
        root.add(new Node("var"));

        return root;
    }
}

class Node {
    private ArrayList<Node> entries;
    private String value;
    Node(String v) {
        entries = new ArrayList<Node>();
        value = v;
    }
    public String getValue(){
        return value;
    }
    public void add(Node n){
        entries.add(n);
    }
    public int size(){
        return entries.size();
    }
    public Node at(int index){
        return entries.get(index);
    }
}

出力結果

-- DFS
/
var
etc
bin
od
diff
ar
usr
home
userC
userB
userA
-- BFS
/
usr
bin
etc
var
home
ar
diff
od
userA
userB
userC