我正在尋找一種實現或方法來創建在迭代中重復的可變（具有頻繁更新）、排序、隊列或列表。一個例子是 [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），因為我完全被難住了。
1 回答
藍山帝景
TA貢獻1843條經驗 獲得超7個贊
好吧，我硬著頭皮寫了自己的實現
/**
* 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 以實現所需的功能?？梢圆迦牖騽h除元素，迭代器將相應地更新。循環中的直接迭代將導致無限循環，但這不是預期的目的。Javadocs 中有一個簡短的示例用例，大多數方法應該具有明顯的或繼承的功能，任何沒有的都被記錄下來。
希望這對其他人有幫助，如果他們有我非常具體的問題
添加回答
舉報
0/150
提交
取消