Объяснение проблемы ежедневного кодирования # 365

Кряк - это структура данных, сочетающая свойства как стеков, так и очередей. Его можно рассматривать как список элементов, записанных слева направо, так что возможны три операции:

  • push(x): добавить новый элемент x в левый конец списка
  • pop(): удалить и вернуть элемент в левом конце списка
  • pull(): удалить элемент в правом конце списка.

Реализуйте шарлатан, используя три стека и O(1) дополнительную память, чтобы амортизированное время для любой операции push, pop или pull было O(1).

Решение в JavaScript

Push и Pop уже поддерживаются в JavaScript как операция со списком, которая фактически удаляет элементы справа, и обе операции - O (1).

Вытягивание будет сложным, поскольку удаление первого элемента потребует от нас переместить все остальные элементы в списке, что будет операцией O (n).

Мы можем использовать deque (двусторонняя очередь), которая представляет собой тип очереди, которая позволяет удалять элементы как спереди, так и сзади. поэтому мы можем использовать deque как стек и как очередь. Подробнее про deque можно прочитать здесь. Deque обычно создается с использованием двух структур данных, то есть кругового массива, двусвязного списка.

Но для нашего решения нам нужно создать двухстороннюю очередь со стеками.

Один из способов - иметь три стопки.

  1. left (будет использоваться для push и pop)
  2. право (будет использоваться для тяги)
  3. буфер (будет использоваться для обращения стека)

Толкать

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

Поп

Если у нас есть элемент в левом массиве, мы можем просто выскочить вот так

но в нашем случае нам нужно проверить, есть ли у нас элемент в нашем правом списке, если да, то нам нужно сбалансировать наше шарлатанство.

Пример:

Для этого нам нужно переместить половину наших предметов из правой стопки в левую.

  1. Переместите половину предметов в буфер.
  2. Переместите оставшиеся элементы влево.
  3. Переместите все элементы в буфере вправо назад.

То же самое и для операции извлечения, если у нас нет элемента в правом массиве, нам нужно сбалансировать нашего шарлатана (переместить половину элементов слева направо)

Вот полный код