Очереди и стеки

Во многих алгоритмах имеется внутренняя фаза, в которой они должны обработать множество элементов: например, множество всех ребер, инцидентных узлу графа, множество проверенных узлов в алгоритмах BFS и DFS или множество всех свободных мужчин в алгоритме устойчивых паросочетаний.

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

Два простейших и самых естественных варианта организации множеств элементов — очередь и стек. Элементы очереди извлекаются в порядке «первым пришел, первым вышел» (FIFO, First-In, First-Out), то есть в том же порядке, в котором они добавлялись.

Элементы стека извлекаются в порядке «последним пришел, первым вышел» (LIFO, Last-In, First-Out): при каждом извлечении выбирается элемент, который был добавлен последним.

И очереди и стеки легко реализуются на базе двусвязного списка. В обоих случаях всегда выбирается первый элемент списка; отличается позиция вставки нового элемента. В очереди новый элемент добавляется в конец списка в последнюю позицию, а в стеке он размещается в первой позиции списка.

Помните, что в двусвязном списке хранятся указатели First и Last на начало и на конец списка соответственно, поэтому в обоих случаях вставка выполняется за постоянное время.

В следующем разделе будет показано, как реализовать алгоритмы поиска из предыдущего раздела за линейное время. Вы увидите, что алгоритм BFS может рассматриваться так, словно следующий узел выбирается из очереди, тогда как алгоритм DFS фактически предполагает стековую реализацию.