Где бы я обычно использовал Deque в производственном программном обеспечении?

Я довольно хорошо знаю, где использовать стеки, очереди и деревья в программных приложениях, но я никогда раньше не использовал Deque (Double Ended Queue). Где бы я обычно встречал их в дикой природе? Будет ли это в тех же местах, что и в очереди, но с дополнительными gribbilies?

data-structures Мировой инженер
источник

en.wikipedia.org/wiki/Double-ended_queue#Applications

Арсений Мурзенко,

кажется, есть некоторая путаница в этой теме. В Интернете «deque» - это двусторонняя очередь (в Википедии упоминается реализация связанного списка). Однако в C ++ STL std :: deque - это массивоподобная структура, реализованная как массив блоков данных. Он предлагает произвольный доступ, аналогичный std :: vector, но его возможность изменения размера ближе к возможности std :: list, поскольку при добавлении данных он добавляет блоки и не перераспределяет и не перемещает существующие данные.

ДХМ

@DXM: очередь STL по-прежнему является двусторонней очередью и обеспечивает более быстрые операции на концах (в зависимости от реализации). То, что он также предлагает доступ к середине, не делает его основную операцию менее похожей на очередь.

gbjbaanb

@gbjbaanb: Все, что я говорю, это если вы посмотрите на общедоступные интерфейсы 3 классов: std :: vector, std :: list (или std :: queue) и std :: deque, вы увидите, что std :: vector и std :: deque имеют идентичный открытый интерфейс и идентичные возможности (std :: deque немного более гибок за счет увеличения объема используемой памяти). Std :: list и std :: queue, с другой стороны, ведут себя больше как их CS-компоненты, связанный список и очередь соответственно. CS deque! = Std :: deque

DXM

Я считаю этот ответ более практичным shiv.mymail - stackoverflow.com/questions/3880254/…

roottraveller

Ответы:

Один из способов использования deque - это «старение» предметов. Обычно он используется как функция отмены или истории. Новое действие вставлено в деку. Самые старые предметы находятся на фронте. Ограничение на размер декы заставляет элементы в передней части быть удаленными в некоторый момент, когда новые элементы вставляются (старение самых старых элементов). Затем он обеспечивает быстрый способ доступа к обоим концам структуры, потому что вы мгновенно узнаете самые старые и самые новые элементы, чтобы либо удалить фронт, и совершить самое старое действие в O (1), либо отменить в O (1) время.

jmq
источник

Я не думаю, что deques используются / необходимы здесь. Достаточно простого (возможно, ограниченного по размеру) стека.

Конрад Рудольф

@Konrad Как вы состариваете вещи в простом стеке? (т.е. как вы удаляете команды, которые «слишком старые»?)

Андрес Ф.

@AndresF. Возраст не зависит от размера стека? Если так, то я никогда не слышал об этой структуре данных. В противном случае это просто стек с фиксированным размером, который можно реализовать в терминах deque, или просто постулируя более простую структуру данных, называемую стеком фиксированного размера.

Конрад Рудольф

Так двусторонние очереди являются полезными в конце концов;) Никогда не слышала о стеке фиксированного размера (в том смысле , вы имеете в виду, удаления старого элемента). Это имеет смысл, но это не то, что обычно подразумевается под «стеком», и то, действительно ли это проще, еще неизвестно :)

Andres F.

Это было размещено в комментариях к исходному вопросу: en.wikipedia.org/wiki/Double-ended_queue Это просто двусторонняя очередь. Я использовал это на практике так, как я обрисовал выше (вот почему я опубликовал это). В истинном стеке единственными операциями, которые вы должны иметь, являются push, pop, top и peek (мы могли бы поспорить с другими, но это обычно так). Вы не должны знать, что находится на дне стека или даже как получить доступ к дну. В «стеке фиксированного размера» вы просто генерировали бы переполнение стека вместо устаревания старых элементов при его заполнении.

JMQ

Отличный вопрос. Я не могу вспомнить наш курс по CS 102, в котором упоминалось одно приложение для двусторонней очереди.

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

Это работает по существу следующим образом:

В нормальной однопоточной процедурной модели каждый вызов функции помещает запись активации в так называемый стек вызовов . Запись активации содержит локальные переменные и параметры этого вызова. После завершения вызова метода («возврата») последняя запись активации извлекается из стека вызовов.

Это особенно важно, потому что именно так реализована рекурсия: структура рекурсии представлена в текущем состоянии стека вызовов.

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

Но как только поток завершил свою работу (= его очередь вызовов пуста), он крадет работу из другого потока, удаляя запись активации из очереди вызовов этого потока, удаляя ее с «неправильного» конца.

По сути, очередь вызовов действует как два стека вызовов, которые теперь обслуживают два потока.

Конрад Рудольф
источник

У вас есть источник для этого? Звучит интересно.

kyjelly90210

@ Richard1987 Статья в Википедии цитирует оригинальную статью. Существует несколько реализаций, например, в реализации кражи работы с параллельным расширением GNU c ++ stdlib (но код ужасно читается) или параллельная реализация обобщенного метода «разделяй и властвуй » (правда, последняя использует очень идиоматический стиль программирования). в частности, в библиотеке и, следовательно, трудно читать)

Конрад Рудольф