Есть ли эффективный способ узнать, находится ли элемент очереди «перед» другим?

Question

Для моего Java-приложения мне нужен какой-то метод, который определяет, является ли item1 «до» item2 в моей очереди Q. Конечно, я могу просто использовать итератор и начать обход списка. Однако, может быть, есть другой способ выяснить это?

Для моего конкретного приложения я не могу использовать LinkedList (который предоставляет индексы и позволяет легко определить, находится ли один объект перед другим).

Answer 1

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

Answer 2

Если вам нужно только выяснить, находится ли item2 в очереди, Вы можете использовать java.util.LinkedHashMap, который поддерживает порядок вставки и может использоваться как очередь LIFO.

Answer 3

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

Я бы не рассматривал LinkedList 'index' как решение. Это реализовано как обход списка.

Answer 4

Я бы оставил отдельный HashMap от объектов очереди до целых чисел и подсчет общего количества объектов, которые вы когда-либо добавляли в очередь (поэтому при вставке объекта X счетчик означает, что объект X является Nобъект вставлен).Каждый раз, когда вы добавляете объект в очередь, добавляйте его в HashMap в качестве ключа;значение является текущим значением счетчика.

Когда вам нужно спросить, какой из двух объектов является первым, найдите их в HashMap и сравните порядковые числа.Какой из них имеет более низкое значение, тот пришел первым.

Answer 5

A Queue - это Collection, поэтому вы всегда можете скопировать его элементы в другой Collection, который позволяет получить заказ, например,

List<YourType> copy = new ArrayList<YourType>(yourQueue);
if(copy.indexOf(obj1)<copy.indexOf(obj2)){
    // some code here
}

Конечно, это ужасно неэффективно, но это работает.(Вам, вероятно, придется синхронизировать очередь при этом)

Другим способом было бы сделать это через iterator():

/**
 * Returns -1 if a occurs in the collection before b, 1 if b occurs before a
 * and 0 otherwise.
 */
public static <T> int comparePositionInCollection(final T a,
    final T b,
    final Collection<T> collection){

    // todo: check for a==null, b==null, a.equals(b)

    final Iterator<T> iterator = collection.iterator();
    boolean foundA = false;
    boolean foundB = false;
    int result = 0;
    while(iterator.hasNext()){
        final T t = iterator.next();
        if(a.equals(t)){
            if(foundB){
                result = 1;
                break;
            }
            foundA = true;
        } else if(b.equals(t)){
            if(foundA){
                result = -1;
                break;
            }
            foundB = true;
        }
    }
    return result;
}

Конечно, вам придется синхронизировать очередьдо доступа к итератору, так что это также ужасно неэффективно.

Answer 6

Я рекомендую приоритетную очередь, которая может ссылаться на таблицу поиска.Таким образом, вы получаете постоянную производительность для элемента, который хотите получить, и затраты на вставку полинома.Тем не менее, это может быть специализировано для вашего использования, если вы просто пытаетесь сделать сравнение, а не найти лучший или худший элемент приоритета.Тем не менее, постоянная производительность всегда приятно.и тогда вы не обязательно итерируете массив, а просто смотрите вверх.

Answer 7

Как правило, в очередях будет предложена операция «peek», которая позволит вам увидеть, что находится наверху очереди, не удаляя ее, но все остальное требует другой структуры данных. Или же вы вытаскиваете вещи из очереди в другую очередь, пока не выясните это, после чего вам нужно запросить значения, которые вы вытолкнули.

Answer 8

LinkedList - такой базовый класс, что трудно представить что-то, что я мог бы предложить в качестве альтернативы.кроме ArrayList, который поддерживает произвольный доступ и может быть намного быстрее для индексированного доступа.Однако ArrayList не так эффективен, как очередь.