Зачем использовать два стека для очереди?

Я вижу преимущество использования двух стеков, если используется реализация массива, поскольку стеки более легко реализуются с использованием массивов, чем очереди. Но если используются связанные списки, в чем преимущество? Активация стека в очередь увеличивает накладные расходы для реализации связанных списков и массивов.

Ответы

Ответ 1

Это обычный способ реализации очереди в языках функционального программирования с чисто функциональными (неизменяемыми, но разделяющими структурами) списками (например, Clojure, Haskell, Erlang...):

  • используйте пару списков для представления очереди, где элементы находятся в порядке FIFO в первом списке и в порядке LIFO во втором списке
  • enqueue в очередь путем добавления ко второму списку
  • dequeue из очереди, взяв первый элемент первого списка
  • если первый список пуст: отмените второй список и замените его первым, и замените второй список пустым списком

(все операции возвращают новый объект очереди в дополнение к любым возможным возвращаемым значениям)

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

Ответ 2

Этот подход может быть использован для создания очереди lock-free с использованием двух атомных односвязных списков, таких как предоставленные Win32: Блокированные одиночные списки. Алгоритм может быть описан в liwp answer, хотя шаг переупаковки (пуля 4) можно немного оптимизировать.

Блокированные структуры данных и алгоритмы - очень интересная (для некоторых из нас) область программирования, но их нужно использовать очень осторожно. В общей ситуации алгоритмы на основе блокировки более эффективны.

Ответ 3

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

Но, если вам просто нужна измененная очередь, использование двух стеков - отличный способ сделать ее медленнее и сложнее, чем просто связанный список.

Ответ 4

Это хороший опыт обучения, но не практический.