Java 类sun.misc.Queue 实例源码

public static void printLevelOrder(Node root) throws InterruptedException {
    Queue<Node> qn = new Queue<Node>();
    Node temp;

    if(root == null){
        return;
    }

    qn.enqueue(root);

    while(!qn.isEmpty()){
        temp = qn.dequeue();

        System.out.println(temp.data);

        if(temp.left != null)
            qn.enqueue(temp.left);

        if(temp.right != null)
            qn.enqueue(temp.right);
    }

}

public static void printLevelOrder(Node root) throws InterruptedException {
    Node temp;
    Queue<Node> qn = new Queue<Node>();

    if(root == null){
        return;
    }

    qn.enqueue(root);

    while(!qn.isEmpty()) {
        temp = qn.dequeue();
        System.out.print(temp.data);

        if(temp.left != null)
            qn.enqueue(temp.left);

        if(temp.right != null)
            qn.enqueue(temp.right);
    }
}

public static void printLevelOrderDataInReverse(Node root) throws InterruptedException {
    Queue<Node> qn = new Queue<Node>();
    Stack<Node> sn = new Stack<Node>();
    Node temp;

    if(root == null) {
        return;
    }

    qn.enqueue(root);

    while(!qn.isEmpty()) {
        temp = qn.dequeue();

        if(temp.right != null){
            qn.enqueue(temp.right);
        }

        if(temp.left != null){
            qn.enqueue(temp.left);
        }

        sn.push(temp);
    }

    while(!sn.isEmpty()) {
        System.out.print(sn.pop().data);
    }
}

public static int numberOfHalfNodes(Node root) throws InterruptedException {
    Queue<Node> qn = new Queue<Node>();
    Node temp;
    int count = 0;

    if(root == null){
        return 0;
    }

    qn.enqueue(root);

    while(!qn.isEmpty()) {
        temp = qn.dequeue();

        if((temp.left==null && temp.right!=null) || (temp.left!=null && temp.right==null)) {
            count++;
        }

        if(temp.left != null){
            qn.enqueue(temp.left);
        }

        if(temp.right != null) {
            qn.enqueue(temp.right);
        }
    }
    return count;
}

/**
 * BFS for a vertex
 * 
 * @param g - graph to be searched
 * @param start - start vertex for the search operation in graph g
 * @param goal - goal vertex to be searched in graph g
 * @throws InterruptedException
 */
public void bfs(GraphAdjList g, Character start, Character goal) throws InterruptedException {
    Queue<Character> q = new Queue<Character>();
    // Set to keep track of visited nodes
    Set<Character> visited = new HashSet<Character>();
    // Map to hold parent-child relationship among nodes
    Map<Character, Character> parentChildMap = new HashMap<Character, Character>();

    Character curr;
    q.enqueue(start);
    visited.add(start);

    while(!q.isEmpty()) {
        curr = q.dequeue();
        if(curr==goal) {
            System.out.println("\nGoal found..."+curr);
            System.out.println("visited nodes: "+visited.toString());
            System.out.println("parent child map: "+parentChildMap.toString());
            return;
        }

        System.out.print(curr+"->");

        for(Character c : g.getEdgeList(curr)) {
            if(!visited.contains(c)) {
                visited.add(c);
                parentChildMap.put(curr, c);
                q.enqueue(c);
            }
        }

    }
}