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

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

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

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Очереди и стеки:

  1. Наряды вне очереди
  2. 2. Наследники иных (последующих) очередей
  3. 1. Наследники первой очереди
  4. Статья 1263. Третья очередь наследников по закону
  5. Статья 1264. Четвертая очередь наследников по закону
  6. Статья 1265. Пятая очередь наследников по закону
  7. Статья 1262. Вторая очередь наследников по закону
  8. Статья 1261. Первая очередь наследников по закону
  9. Мудрец, в первую очередь, – гармоничный человек
  10. Если мы спешим, то в универсаме становимся в очередь, которая движется медленнее всех остальных.
  11. Статья 534. Очередность погашения требований по денежным обязательствам
  12. 1. Понятие и принципы наследования по закону
  13. Статья 1258. Очередность наследования по закону
  14. Статья 1072. Очередность списания денежных средств со счета
  15. 8. Наследование по закону
  16. Статья 112. Удовлетворение требований кредиторов
  17. Получение энергии от людей (пожирание),
  18. 22. Очередность удовлетворения требований кредиторов
  19. Аспекты Луны
  20. Управители домов