创建排序队列的有效方法，其迭代器在 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

好吧，我硬着头皮写了自己的实现/**&nbsp;* Implementation of {@link java.util.Queue} that represents a continuous queue of ordered data.&nbsp;* Elements are automatically sorted when added, by a given {@link Comparator}&nbsp;* This class is useful for something like a turn based game, in which a group of users take turns to perform&nbsp;* an action, and then repeat back to the first user.&nbsp;* Because of this, direct iteration or looping over <strong>WILL REPEAT INDEFINITELY</strong>, causing an&nbsp;* infinite loop.&nbsp;* A more suited example would be something like:&nbsp;* <p>&nbsp;* var currentPlayingUser;&nbsp;* while(game in progress){&nbsp;* //wait for the user to take their turn&nbsp;* currentPlayingUser = queue.poll();&nbsp;* }&nbsp;*&nbsp;* @param <T> The type of element in the queue&nbsp;* @author Alexander Wood http://bristermitten.me&nbsp;*/public class SortedRepeatingQueue<T> extends AbstractQueue<T> {&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Internal list for this implementation.&nbsp; &nbsp; &nbsp;* This list is guaranteed to be sorted at all times&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; private final List<T> backingList = new ArrayList<>();&nbsp; &nbsp; private Comparator<T> comparator;&nbsp; &nbsp; private Itr iterator = iterator();&nbsp; &nbsp; public SortedRepeatingQueue(Comparator<T> comparator) {&nbsp; &nbsp; &nbsp; &nbsp; this.comparator = comparator;&nbsp; &nbsp; }&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* Return, but do not remove the head element.&nbsp; &nbsp; &nbsp;* Due to the cyclic nature, removing the head element would not match the intended functionality.&nbsp; &nbsp; &nbsp;* However, this will cycle through the elements. That is, given a SortedRepeatingQueue [1,2,3]&nbsp; &nbsp; &nbsp;* poll will return 1, then 2, then 3, then 1, etc&nbsp; &nbsp; &nbsp;* <p>&nbsp; &nbsp; &nbsp;* This is functionally equivalent to the head element being moved to the tail rather than removed, although&nbsp; &nbsp; &nbsp;* is not what happens.&nbsp; &nbsp; &nbsp;*&nbsp; &nbsp; &nbsp;* @return The "head" element of this SortedRepeatingQueue&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; @Override&nbsp; &nbsp; public T poll() {&nbsp; &nbsp; &nbsp; &nbsp; return iterator.next();&nbsp; &nbsp; }&nbsp; &nbsp; @Override&nbsp; &nbsp; public T peek() {&nbsp; &nbsp; &nbsp; &nbsp; return iterator.nextWithoutCycle();&nbsp; &nbsp; }&nbsp; &nbsp; @Override&nbsp; &nbsp; public boolean offer(T t) {&nbsp; &nbsp; &nbsp; &nbsp; return add(t);&nbsp; &nbsp; }&nbsp; &nbsp; public boolean add(T e) {&nbsp; &nbsp; &nbsp; &nbsp; backingList.add(e);&nbsp; &nbsp; &nbsp; &nbsp; backingList.sort(comparator);&nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; }&nbsp; &nbsp; public boolean addAll(Collection<? extends T> c) {&nbsp; &nbsp; &nbsp; &nbsp; boolean b = backingList.addAll(c);&nbsp; &nbsp; &nbsp; &nbsp; backingList.sort(comparator);&nbsp; &nbsp; &nbsp; &nbsp; return b;&nbsp; &nbsp; }&nbsp; &nbsp; public boolean remove(Object o) {&nbsp; &nbsp; &nbsp; &nbsp; return backingList.remove(o);&nbsp; &nbsp; }&nbsp; &nbsp; public Itr iterator() {&nbsp; &nbsp; &nbsp; &nbsp; return new Itr();&nbsp; &nbsp; }&nbsp; &nbsp; public int size() {&nbsp; &nbsp; &nbsp; &nbsp; return backingList.size();&nbsp; &nbsp; }&nbsp; &nbsp; @Override&nbsp; &nbsp; public String toString() {&nbsp; &nbsp; &nbsp; &nbsp; return "SortedRepeatingQueue{" +&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; "backingList=" + backingList +&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; '}';&nbsp; &nbsp; }&nbsp; &nbsp; private class Itr implements Iterator<T> {&nbsp; &nbsp; &nbsp; &nbsp; private int cursor = 0;&nbsp; &nbsp; &nbsp; &nbsp; public boolean hasNext() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public T next() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (cursor == backingList.size()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cursor = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return backingList.get(cursor++);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public T nextWithoutCycle() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (cursor == backingList.size()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cursor = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return backingList.get(cursor);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; public void remove() {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (cursor == backingList.size()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; cursor = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; backingList.remove(cursor);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}它使用基于游标的迭代器并包装排序的 ArrayList 以实现所需的功能。可以插入或删除元素，迭代器将相应地更新。循环中的直接迭代将导致无限循环，但这不是预期的目的。Javadocs 中有一个简短的示例用例，大多数方法应该具有明显的或继承的功能，任何没有的都被记录下来。希望这对其他人有帮助，如果他们有我非常具体的问题