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

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


list abstract-data-type
person Tom    schedule 12.01.2010    source источник
comment
Кто использует две стопки для создания очереди? Я не очень понимаю ситуацию (извините :(   -  person helios    schedule 12.01.2010

Ответы (4)


arrow_upward
23
arrow_downward

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

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

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

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

person liwp    schedule 12.01.2010
comment
второй шаг, я считаю, что последнее слово должно быть list, а не queue, чтобы оно было похоже на enqueue to the queue by prepending to the second list. - person Lihang Li; 27.05.2014
comment
Спасибо @LihangLi, исправлено! - person liwp; 27.05.2014
comment
Здесь используется неправильный список? - person CyberMew; 10.07.2021

arrow_upward
7
arrow_downward

Этот подход можно использовать для создания очереди без блокировки с использованием двух атомарных односвязных стеки на основе списков, например, предоставленные Win32: Interlocked Singly Связанные списки. Алгоритм может быть таким, как описано в ответе liwp, хотя этап переупаковки (пункт 4) можно немного оптимизировать.

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

person atzz    schedule 12.01.2010
comment
В случае с несколькими записывающими устройствами и одним считывателем легко обрабатывать операции постановки в очередь эффективным безблокировочным способом, а также для удаления из очереди (без блокировки писателей и при условии наличия одного считывателя), если один запускает удаление из очереди с помощью pop all работа с почтовым ящиком (в основном Interlocked.Exchange). Если бы могло быть несколько читателей, вероятно, лучше было бы позволить им использовать блокировку для арбитража между собой (их блокировка не повлияет на писателей). - person supercat; 26.09.2012
comment
Это объяснение, которое я искал. Уважаемый, сэр. - person Aaron S; 01.05.2017

arrow_upward
3
arrow_downward

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

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

person Craig Gidney    schedule 12.01.2010

arrow_upward
-3
arrow_downward

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

person Dean J    schedule 12.01.2010