Есть какие-нибудь интересные алгоритмы, использующие стек и очередь (deque) ADT?

Question

Мы часто используем стеки или очереди в наших алгоритмах, но есть ли случаи, когда мы используем двусвязный список для реализации и стека и очереди в алгоритме? Например, на одном этапе мы помещаем () 6 элементов в стек, pop () 2 элемента, а затем удаляем из очереди () остальные элементы (4) из хвоста двусвязного списка. Я ищу неясные, интересные алгоритмы, которые реализуют что-то в этом методе, или даже незнакомец. Псевдокод, ссылки и пояснения были бы хороши.

Answer 1

Алгоритм Мелькмана (для вычисления выпуклой оболочки простой многоугольной цепочки за линейное время) использует двустороннюю очередь (иначе deque ) для хранения добавочной оболочки для уже обработанных вершин.

Input: a simple polyline W with n vertices V[i]

    Put first 3 vertices onto deque D so that:
    a) 3rd vertex V[2] is at bottom and top of D
    b) on D they form a counterclockwise (ccw) triangle

    While there are more polyline vertices of W to process
    Get the next vertex V[i]
    {
        Note that:
        a) D is the convex hull of already processed vertices
        b) D[bot] = D[top] = the last vertex added to D

        // Test if V[i] is inside D (as a polygon)
        If V[i] is left of D[bot]D[bot+1] and D[top-1]D[top]
            Skip V[i] and Continue with the next vertex

        // Get the tangent to the bottom
        While V[i] is right of D[bot]D[bot+1]
            Remove D[bot] from the bottom of D
        Insert V[i] at the bottom of D

        // Get the tangent to the top
        While V[i] is right of D[top-1]D[top]
            Pop D[top] from the top of D
        Push V[i] onto the top of D
    }

    Output: D = the ccw convex hull of W.

Источник: http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm

Джо Митчелл: Алгоритм выпуклого корпуса Мелкмана (PDF)

Answer 2

Эта структура называется Deque, то есть очередью, в которую элементы могут быть добавлены или удалены из головы или хвоста.Подробнее на 1 .

Answer 3

Я не уверен, подходит ли это, но вы можете использовать двустороннюю очередь priority , чтобы применить быструю сортировку к файлу, слишком большому, чтобы уместиться в память.Идея состоит в том, что в обычной быстрой сортировке вы выбираете элемент в качестве оси, а затем разделяете элементы на три группы: элементы меньше, чем точка, элементы равны, а элементы больше, чем точка.Если вы не можете поместить все элементы в память одновременно, вы можете адаптировать это решение следующим образом.Вместо того, чтобы выбрать один элемент в качестве основного, вместо этого выберите какое-то огромное количество элементов (скажем, столько, сколько вы можете уместить в ОЗУ) и вставьте их в очередь с двусторонним приоритетом.Затем сканируйте остальные элементы по одному.Если элемент меньше, чем наименьший элемент очереди с двусторонним приоритетом, поместите его в группу элементов, меньшую, чем все сводные объекты.Если он больше, чем самый большой элемент очереди с приоритетами, поместите его в группу элементов, превышающую сводные.В противном случае вставьте элемент в очередь с двусторонним приоритетом, а затем вытолкните либо самый маленький, либо самый большой элемент из очереди и поместите его в соответствующую группу.Как только вы закончите делать это, вы разделите элементы на три части - группу небольших элементов, которые затем можно будет рекурсивно отсортировать, группу элементов в середине, которые теперь полностью отсортированы (так как если вы удалите их все из очереди)из очереди с двусторонним приоритетом они будут извлечены в отсортированном порядке), а также из группы элементов, превышающей средние элементы, которые также могут быть отсортированы.

Для получения дополнительной информации об этом алгоритме и двустороннемПриоритетные очереди в общем, рассмотрите эту ссылку к главе по теме.

Answer 4

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