Объяснение проблемы ежедневного кодирования # 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 обычно создается с использованием двух структур данных, то есть кругового массива, двусвязного списка.
Но для нашего решения нам нужно создать двухстороннюю очередь со стеками.
Один из способов - иметь три стопки.
- left (будет использоваться для push и pop)
- право (будет использоваться для тяги)
- буфер (будет использоваться для обращения стека)
Толкать
мы можем добавлять элементы слева направо, и поскольку мы используем массивы JavaScript, которые являются динамическими, нам не нужно беспокоиться о верхнем пределе шарлатана или о нашем левом стеке.
Поп
Если у нас есть элемент в левом массиве, мы можем просто выскочить вот так
но в нашем случае нам нужно проверить, есть ли у нас элемент в нашем правом списке, если да, то нам нужно сбалансировать наше шарлатанство.
Пример:
Для этого нам нужно переместить половину наших предметов из правой стопки в левую.
- Переместите половину предметов в буфер.
- Переместите оставшиеся элементы влево.
- Переместите все элементы в буфере вправо назад.
То же самое и для операции извлечения, если у нас нет элемента в правом массиве, нам нужно сбалансировать нашего шарлатана (переместить половину элементов слева направо)
Вот полный код