Почему использование два стека для создания очереди?
Я вижу преимущество использования двух стеков, если реализация массива используется, так как стеки более легко реализованы с помощью массивов, чем очереди. Но если связанные списки используются, каково преимущество? Действие сования стека на очередь увеличивается наверху и для связанного списка и для реализаций массива.
4 ответа
Это общий способ реализации очереди в функциональных языках программирования с чисто функциональными (неизменными, но совместными сооружениями) списки (например, Clojure, Haskell, Erlang ...):
- Используйте пару списков для представления очереди Там, где элементы находятся в порядке в FIFO в первом списке и в порядок Lifo во втором списке
- enqueue в очередь, подготовив к второму списку
- . Укажите из очереди, взяв первый элемент первого списка
- Если первый список пуст: обратитесь за второй список и замените первый список, и замените второй список пустым списком
(все операции возвращают новый объект очередей в дополнение к любым возможным значениям возврата)
Дело в том, что добавление (удаление) элемента (из) передней части чисто функционального списка представляет собой O (1) и обратная работа, которая является o (n), амортизирована по всем режимам, поэтому он находится рядом с O (1 ), тем самым давая вам реализацию очереди ~ O (1) с неизменными структурами данных.
Этот подход может быть использован для построения очереди без блокировки , используя два стога на основе атомных однонакомых списков, таких как win32: Списки . Алгоритм может быть, как описано в Ответ Liwp , хотя шаг из экспакования (Bullet 4) может быть немного оптимизирован.
Бесплатные структуры данных и алгоритмы данных являются очень захватывающими (для некоторых из нас) область программирования, но они должны использоваться очень тщательно. В общей ситуации алгоритмы на основе блокировки более эффективны.
ExpressionEngine 2 - затраты, но явно лучшие.
PyroCMS - свободный и хотя выглядит безобразно, как грех, ветвь v0.9.8-dev очень перспективна. Делает гораздо больше, чем просто блог.
DBlog - просто блог, но делает это хорошо.
-121--1106229- Одной из областей deftype является производительность. Методы протоколов очень быстры на deftype. Также дефтип может иметь примитивные поля, поэтому больше не бокс, когда хрустящие числа...
Другой областью может быть взаимодействие Java, поскольку deftype может реализовывать интерфейсы (и если AOT скомпилирован) имеют именованный класс.
В общем, это основная идея определить абстракции с протоколами и реализовать их с deftype.
Богатые подробности его мотивации здесь: http://www.assembla.com/wiki/show/clojure/Datatypes
-121--2564041-Вы можете создать неизменяемую очередь с помощью двух неизменяемых стеков.
Но если вам нужна изменяемая очередь, использование двух стеков - отличный способ сделать ее более медленной и сложной, чем просто использование связанного списка.