创建排序队列的有效方法，其迭代器在 Java 中重复回到开头

Question

我正在寻找一种实现或方法来创建在迭代中重复的可变（具有频繁更新）、排序、队列或列表。一个例子是 [1, 3, 4, 9]，其中 next() 循环遍历元素，并在 9 之后返回 1。元素经常被删除和添加，需要正确排序。我最初的计划是使用 LinkedList 或 PriorityQueue，但问题越来越多。我需要对队列进行排序（最好是在更新时而不是在迭代时），因此使用 PriorityQueue，但我还需要队列在迭代时重复（手动完成，而不是循环）。我考虑制作一个包含比较器并包装迭代器的类，它看起来有点像这样public class SortedRepeatingQueue<T> extends LinkedList<T> {    private final Comparator<T> comparator;    private Iterator<T> iterator = iterator();    public SortedRepeatingQueue(Comparator<T> comparator) {        this.comparator = comparator;    }    public T next() {        Collections.sort(this, comparator);        if (!iterator.hasNext()) {            iterator = iterator();        }        return iterator.next();    }}但是，如果在迭代期间删除或添加条目，这会产生问题，因为缓存的 Iterator 不会更新，更新它需要大量工作以确保我们在同一索引处继续。例如，如果我们迭代 [1,2,3,5]，在 3 处然后插入 4，更新迭代器以确保 next() 返回 4 而不是 5 将很棘手。另一个选择是 List 的简单扩展，其中 next() 获取第一个元素，返回它，然后将它移到后面（例如 [1,3,4,5].next() 返回 1 并创建 [3,4, 5,1])。但是，这将被列表上的任何排序所覆盖。我还考虑过完全自定义的实现，但我不太相信自己可以创建一个安全、完全可用的实现，而且这会非常耗时。我正在寻找任何快速处理此问题的方法（尽管速度不是主要优先事项，因为 n 永远不应真正大于 20-30），因为我完全被难住了。

Answer 1

好吧，我硬着头皮写了自己的实现

/**

 * Implementation of {@link java.util.Queue} that represents a continuous queue of ordered data.

 * Elements are automatically sorted when added, by a given {@link Comparator}

 * This class is useful for something like a turn based game, in which a group of users take turns to perform

 * an action, and then repeat back to the first user.

 * Because of this, direct iteration or looping over <strong>WILL REPEAT INDEFINITELY</strong>, causing an

 * infinite loop.

 * A more suited example would be something like:

 * <p>

 * var currentPlayingUser;

 * while(game in progress){

 * //wait for the user to take their turn

 * currentPlayingUser = queue.poll();

 * }

 *

 * @param <T> The type of element in the queue

 * @author Alexander Wood http://bristermitten.me

 */

public class SortedRepeatingQueue<T> extends AbstractQueue<T> {

    /**

     * Internal list for this implementation.

     * This list is guaranteed to be sorted at all times

     */

    private final List<T> backingList = new ArrayList<>();

    private Comparator<T> comparator;

    private Itr iterator = iterator();

    public SortedRepeatingQueue(Comparator<T> comparator) {

        this.comparator = comparator;

    }

    /**

     * Return, but do not remove the head element.

     * Due to the cyclic nature, removing the head element would not match the intended functionality.

     * However, this will cycle through the elements. That is, given a SortedRepeatingQueue [1,2,3]

     * poll will return 1, then 2, then 3, then 1, etc

     * <p>

     * This is functionally equivalent to the head element being moved to the tail rather than removed, although

     * is not what happens.

     *

     * @return The "head" element of this SortedRepeatingQueue

     */

    @Override

    public T poll() {

        return iterator.next();

    }

    @Override

    public T peek() {

        return iterator.nextWithoutCycle();

    }

    @Override

    public boolean offer(T t) {

        return add(t);

    }

    public boolean add(T e) {

        backingList.add(e);

        backingList.sort(comparator);

        return true;

    }

    public boolean addAll(Collection<? extends T> c) {

        boolean b = backingList.addAll(c);

        backingList.sort(comparator);

        return b;

    }

    public boolean remove(Object o) {

        return backingList.remove(o);

    }

    public Itr iterator() {

        return new Itr();

    }

    public int size() {

        return backingList.size();

    }

    @Override

    public String toString() {

        return "SortedRepeatingQueue{" +

                "backingList=" + backingList +

                '}';

    }

    private class Itr implements Iterator<T> {

        private int cursor = 0;

        public boolean hasNext() {

            return true;

        }

        public T next() {

            if (cursor == backingList.size()) {

                cursor = 0;

            }

            return backingList.get(cursor++);

        }

        public T nextWithoutCycle() {

            if (cursor == backingList.size()) {

                cursor = 0;

            }

            return backingList.get(cursor);

        }

        public void remove() {

            if (cursor == backingList.size()) {

                cursor = 0;

            }

            backingList.remove(cursor);

        }

    }

}

它使用基于游标的迭代器并包装排序的 ArrayList 以实现所需的功能。可以插入或删除元素，迭代器将相应地更新。循环中的直接迭代将导致无限循环，但这不是预期的目的。Javadocs 中有一个简短的示例用例，大多数方法应该具有明显的或继承的功能，任何没有的都被记录下来。

希望这对其他人有帮助，如果他们有我非常具体的问题