java - 同时迭代和修改java队列

Question

我有一个列表和一个指向列表元素的指针。有时我需要:

• 在队列末尾附加一个值
• 从队列头部删除一个值
• 使指针前进到列表中的下一个值

即:

• 从 WRITE 的角度来看，它是一个队列。
• 从 READ 的角度来看，它是一个列表。

如果我使用普通的迭代器，我会在修改队列时得到ConcurrentModificationException；如果我使用 ListIterator，我只能在迭代器位置删除/添加值。

我可以使用任何标准数据结构来实现此目的吗？

Answer 1

您可以使用ConcurrentLinkedQueue。它允许同时修改和迭代，因为它包含必要的同步机制。

以下代码片段显示了一个工作示例，其中有 3 个线程访问同一队列，没有出现问题: 1. 迭代并输出元素 2. 偶尔添加新元素 3. 偶尔删除输出的元素

package test;

import java.util.Iterator;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.atomic.AtomicInteger;

public class QueueListTest
{
    // private static final Queue<Integer> numbers = new ConcurrentLinkedQueue<>();

    public static void main(String[] args)
    {
        final Queue<Integer> numbers = new ConcurrentLinkedQueue<>();

        final AtomicInteger insert = new AtomicInteger(0);
        final AtomicInteger output = new AtomicInteger();

        for(int j = 0; j < 100; j++)
        {
            numbers.add(insert.getAndIncrement());
        }

        // print 1 number every 100ms
        Thread t1 = new Thread() {
            public void run()
            {
                Iterator<Integer> iter = numbers.iterator();
                while(iter.hasNext())
                {

                        int first = numbers.peek();
                        int size = numbers.size();
                        int last = first + size - 1;
                        int current = iter.next();

                        System.out.println("list from " + first + " to " + last + " @ " + current);
                        output.set(current);

                    try
                    {
                        Thread.sleep(100);
                    }
                    catch(InterruptedException e)
                    {
                        e.printStackTrace();
                    }
                }
            }
        };

        // add 5 number every 500ms
        Thread t2 = new Thread() {
            public void run()
            {
                while(true)
                {
                    for(int j = 0; j < 5; j++)
                    {
                        numbers.add(insert.getAndIncrement());
                    }
                    try
                    {
                        Thread.sleep(500);
                    }
                    catch(InterruptedException e)
                    {
                        e.printStackTrace();
                    }
                }
            }
        };

        // remove all printed numbers every 1000ms
        Thread t3 = new Thread() {
            public void run()
            {
                while(true)
                {
                    try
                    {
                        Thread.sleep(1000);
                    }
                    catch(InterruptedException e)
                    {
                        e.printStackTrace();
                    }

                        int current = output.intValue();

                        while(numbers.peek() < current)
                            numbers.poll();
                }
            }
        };

        t1.start();
        t2.start();
        t3.start();

        try
        {
            t1.join();
            t2.join();
            t3.join();
        }
        catch(InterruptedException e)
        {
            e.printStackTrace();
        }
    }
}

因为队列是“链接的”，所以它应该在恒定时间内处理迭代、添加和删除，因此是您可以使用的最有效的实现。