алгоритм - найти положение элемента в очереди

Question

У меня есть массив произвольных объектов

1. Каждый объект имеет уникальный идентификатор
2. Новые объекты добавляются в конец очереди (хвост)
3. Объекты снимаются сверху для обработки (FIFO)
4. Объекты, ожидающие обработки, могут быть удалены, если требуется.

Проблема заключается в том, чтобы найти текущую позицию Объекта в очереди из хвоста с учетом идентификатора.

Какой самый быстрый способ сделать это? Просто чтобы прояснить, я не хочу Object из идентификатора, поэтому просто хэш-карта не является решением. Что мне действительно нужно, так это позиция.

Мы думали о двух путях:

1. Грубая сила, найди в петле
2. добавить новое поле в объекте, в котором хранится глобальный индекс, который увеличивается на единицу для каждого объекта, добавляемого в очередь. Затем мы можем быстро получить позицию, проверив глобальный индекс, сохраненный в последнем элементе и в этом элементе. Однако единственная сложность заключается в том, что, если один из объектов удаляется, глобальный индекс всех элементов, представленных ниже, необходимо обновить.

Есть идеи получше? Пожалуйста, предложите.

Answer 1

Я считаю, что у меня есть log(n) временное решение. Создайте хеш-таблицу, которая сопоставляет каждый ID с его узлом в нашей другой структуре данных - самобалансирующемся бинарном дереве поиска (красно-чёрное, AVL, как вам угодно). В этом дереве узел должен быть упорядочен по его относительному приоритету / порядку в вашей очереди. Он также должен хранить указатель на своего родителя в дереве, а размер поддерева коренится сам по себе. Отсюда мы можем запросить количество элементов с более низким приоритетом / порядком в логарифмическом времени.

Answer 2

Самый простой способ сделать это - представить FIFO в виде двусвязного списка.Этот список может иметь либо Object s (то есть, если бы у вас был идентификатор, вам также потребовалось бы сопоставление, либо карта хеша, либо какой-либо другой подход, от идентификатора к объекту), либо отдельных узлов FIFO (в этом случае выбудет отображаться с ID на адрес узла).