Итерация и изменение очереди Java одновременно - PullRequest
Новая
       25

Итерация и изменение очереди Java одновременно

0 голосов
/ 27 апреля 2018

У меня есть список и указатель на элемент списка. Время от времени мне нужно:

  • добавить значение в конец очереди
  • удалить значение из заголовка очереди
  • сделать указатель для перехода к следующему значению в списке

То есть:

  • с точки зрения НАПИСАТЬ, это очередь.
  • с точки зрения ЧИТАТЬ, это список.

Если я использую обычный итератор, я получаю исключение ConcurrentModificationException при изменении очереди; если я использую ListIterator, я могу только удалить / добавить значение в позиции итератора.

Существует ли какая-либо стандартная структура данных, которую я могу использовать для достижения этой цели?

Ответы [ 3 ]

0 голосов
/ 27 апреля 2018

Не совсем. Проблема в том, что нет структуры, которая делает то, что вы хотите, эффективным образом.

  • Вы можете использовать ArrayList, перебирать индексы и сохранять обновленный текущий индекс после вставки в начале (с шагом 1), но вставка в начале не будет эффективной
  • Вы не можете использовать LinkedList, потому что он не выставляет текущий Node

Лучшая ставка, вероятно, будет CursorableLinkedList из коллекций Apache Commons (https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/list/CursorableLinkedList.html)

).
0 голосов
/ 27 апреля 2018

Вы можете использовать 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();
        }
    }
}

Поскольку очередь «связана», она должна обрабатывать итерации, добавления и удаления в постоянное время и, следовательно, быть наиболее эффективной реализацией, которую вы можете использовать.

0 голосов
/ 27 апреля 2018

Создайте копию своего списка перед итерацией по элементам.

Или у вас есть другие ограничения?

...