Алгоритм Dequeue

Question

Напишите четыре процедуры O (1)-времени, чтобы вставлять элементы в элементы и удалять их с обоих концов детекса, построенного из массива.

В моей реализации я сохранил 4 указателя передний1, задний1, передний2, задний2.

Есть ли у вас какой-либо другой алгоритм с меньшим количеством указателей и сложностью O (1)? Пожалуйста, объясни.

Answer 1

Есть два распространенных способов реализации Deque:

1. Doubly linked list: Вы реализуете дважды связанный список, и сохранить указатели на фронт и в конце списка. Легко как вставить, так и удалить начало/конец связанного списка в O(1) времени.
2. Круговой динамический массив: здесь вы имеете массив, который рассматривается как круговой массив (поэтому элементы в индексе = arr.length-1 и index = 0 считаются смежными).
   В этой реализации вы держите номер индекса «голова» и «хвост». Добавление элемента в «голову» выполняется с индексом head-1 (при перемещении головы назад), а добавление элемента к хвосту выполняется путем записи его в индекс tail+1.
   Этот метод амортизируется O(1) и имеет более высокие константы, чем реализация связанных списков. Однако это не «строгий худший случай» O(1), так как если количество элементов превышает размер массива, вам необходимо перераспределить новый массив и переместить элементы из старого в новый. Это занимает O(n) времени (но должно быть выполнено после не менее O(n) операций), и, таким образом, это O(1) амортизированный анализ, но время от времени он может упасть до O(n).