Любая подобная списку структура данных может быть представлена хеш-таблицей, где каждый элемент в списке сопоставлен со своей позицией.Таким образом, этот список: [a, b, c, d] может быть представлен такой хеш-таблицей, как эта:
0: a
1: b
2: c
3: d
Очередь - это структура данных FIFO: сначала во-первых, то, во-первых.Таким образом, элементы отображаются в том же порядке, в котором они были нажаты.Его можно смоделировать с помощью структуры данных, подобной списку, в которой мы помещаем новые элементы в список, добавляя их в хвост, и добавляем элементы, извлекая их из головы.
, реализация может выделять тольконебольшой (O (1) / O (log n)) объем памяти независимо
Единственными необходимыми данными, которые нужно обрабатывать независимо от самой хеш-таблицы, являются индексы head и tail.
Итак, используя пример [a, b, c, d], наша голова указывает на индекс 0 (что соответствует a), а наш хвост на индекс 3 (что соответствует d).
Чтобы вставить новый элемент в очередь (например, e), мы вставляем его в нашу хеш-таблицу с ключом tail + 1, то есть 4, и увеличиваем наш tail на 1.
Чтобы вытолкнуть элемент, мы получаем элемент в позиции head, удаляем его из хеш-таблицы и увеличиваем head на 1.
После этого наша хеш-таблица заканчивается следующим образом:
1: b
2: c
3: d
4: e
В этой реализации top и len тривиальны для implement.
Эта базовая идея может быть расширена для обработки более сложных хеш-таблиц.