java - 如何正确使用共享BlockingQueue？

Question

我有一个二叉树，其中每个节点代表一个电子门(AND、OR、...)。我的任务是计算树的总值(value)(就像图中的这个，一棵二叉树):

这是我到目前为止的代码(没有线程实现):

门节点:

public class gate_node {
    gate_node right_c, left_c;
    Oprtator op;
    int value;
    int right_v, left_v;

    public gate_node(gate_node right, gate_node left, Oprtator op) {
        this.left_c = left;
        this.right_c = right;
        this.op = op;
        right_v = left_v = 0;
    }

    void add_input(int right_v, int left_v){
        this.right_v=right_v;
        this.left_v=left_v;
    }

    int compute(int array_index, int arr_size) {
        /*
         * The following use of a static sInputCounter assumes that the
         * static/global input array is ordered from left to right, irrespective
         * of "depth".
         */

        final int left, right;
         System.out.print(this.op+"("); 

        if (null != this.left_c) {
            left = this.left_c.compute(array_index,arr_size/2);
            System.out.print(",");
        } else {
            left = main_class.arr[array_index];
            System.out.print(left + ",");
        }

        if (null != this.right_c) {
            right = this.right_c.compute(array_index + arr_size/2,arr_size/2);
            System.out.print(")");
        } else {
            right = main_class.arr[array_index + 1];

            System.out.print(right + ")");
        }

        return op.calc(left, right);
    }
}

运营商:

public abstract class Oprtator {
    abstract int calc(int x, int y);
}

和

public class and extends Oprtator {
    public int calc(int x, int y){
        return (x&y);
    }
}

或者

public class or extends Oprtator {
    public int calc(int x, int y){
        return (x|y);
    }
}

树:

public class tree implements Runnable {
    gate_node head;

    tree(gate_node head) {
        this.head = head;
    }

    void go_right() {
        head = head.right_c;
    }

    void go_left() {
        head = head.left_c;
    }

    @Override
    public void run() {
        // TODO Auto-generated method stub
    }
}

主类

public class main_class {
    public static int arr[] = { 1, 1, 0, 1, 0, 1, 0, 1 };

    public static void main(String[] args) {
        tree t = new tree(new gate_node(null, null, new and()));

        t.head.right_c = new gate_node(null, null, new or());

        t.head.right_c.right_c = new gate_node(null, null, new and());
        t.head.right_c.left_c = new gate_node(null, null, new and());

        t.head.left_c = new gate_node(null, null, new or());

        t.head.left_c.right_c = new gate_node(null, null, new and());
        t.head.left_c.left_c = new gate_node(null, null, new and());

        int res = t.head.compute(0, arr.length);

        System.out.println();
        System.out.println("The result is: " + res);
    }
}

我想使用线程池来计算它，就像这个算法:

准备工作:

1. 将每个门实现为类/对象。它必须有2个属性:输入A、输入B和计算结果的方法；

2. 实现一棵树。每个节点都是一对(gate，next_node)。 Root 是 next_node 为 null 的节点。叶子是没有其他节点指向它的节点。

3. 使用共享(线程安全)节点队列。它最初是空的。

4. 有固定数量(选择一个，不依赖于门的数量)的线程连续等待队列中的元素(除非达到结果，在这种情况下它们就会退出)。

循环:

1. 每当节点上发生输入时，都会将该节点放入队列中(开始时输入会转到叶子)。这可以通过在门上定义 add_input 方法来简单地实现。

2. 线程从队列中选取一个节点:

3. 1. 如果其中一个输入丢失，则丢弃它(当第二个输入出现时，它会再次出现)。另一个想法是仅当两个输入都存在时才将节点放入队列中。

   2. 如果两个输入都存在，则计算结果，如果不为空，则将其传递给next_node(并将next_node放入队列中)。如果 next_node 为 null，那么这就是您的结果 - 打破循环并完成。

唯一的问题是我不知道如何创建一个共享的BlockingQueue，树中的每个节点对象都可以将自己插入其中，以及如何创建一个固定大小的线程数组，不断等待新元素队列可用(然后执行它们)......直到头从列表中删除(意味着我们完成了计算)。

我在线搜索了 BlockingQueue 示例，但我只找到了生产者和消费者示例，并且我很难移动这些示例来适应我的问题。如果有人能尝试帮助我，我将非常感激。

Answer 1

我可以给你一些开始的指导，让你继续前进:)

要创建线程，只需生成那么多线程:

for (int i=0;i<MAX_THREADS;i++) {
    new Thread(myRunnable).start();
}

您可能很想存储对这些线程的引用，但这不是必需的。这些线程不需要特殊的设置，因为它们都是相同的，并且它们都只是坐在那里从队列中抓取项目。

要共享阻塞队列，最简单的方法就是使其静态且最终:

static final BlockingQueue blockingQueue();

现在所有线程都可以访问它。

顺便说一句，如果我这样做，我根本不会使用队列，我会使用 ThreadPoolExecutor 并将处理作为新的可运行对象发送给它。

http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ThreadPoolExecutor.html