Стеки, деки, очереди.

Одной из важных концепций в программировании является концепция стека.

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

Бытовой иллюстрацией стека может служить стопка книг.

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

Просматривать книги можно только по одной, получая их из стека (снимая их с вершины). Чтобы получить книгу из середины стека, надо задать критерий поиска и удалять элементы-книги из стека до тех пор, пока не будет найдена нужная книга. Удаляемые элементы утрачиваются.

Иногда бывает полезно создать новый стек, куда помещаются элементы, удаляемые из исходного стека

Элементы из стека могут удаляться, пока он не станет пустым. Таким образом, над стеком выполняются следующие операции:

1. определение пуст ли стек;

2. добавление в стек нового элемента;

3. доступ к последнему включенному элементу, вершине стека;

4. исключение из стека последнего включенного элемента.

Принцип работы со стеком: «пришел последним - ушел первым» (last in - first out, LIFO).

Такая структура данных очень хорошо реализуется с помощью списка. Тип списка при этом может быть выбран в соответствии с потребностями алгоритма. Например, для стека может подойти линейный однонаправленный список без головного элемента со вставкой и исключением элементов в начале списка (это и будет вершиной стека).

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

Существуют различные разновидности очередей, здесь будет рассмотрена простая бесприоритетная очередь. При этом добавление элементов производится в конец очереди, а выборка и удаление элементов - из начала.

Принцип доступа к очереди – «первым пришел - первым ушел» (first in - first out, FIFO).

Принцип обработки, как для стека, так и для очереди определяет набор соответствующих процедур.

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

Над очередью выполняются следующие операции:

1. добавление в конец очереди нового элемента;

2. определение пуста ли очередь;

3. доступ к первому элементу очереди;

4. исключение из очереди первого элемента.

Эти операции могут быть взяты из стандартного набора действий со списком.

Кроме рассмотренных очереди и стека есть ещё и третий вариант структуры данных - дек, очередь с двойным доступом, или, как ещё его называют, - двухконечный стек. Для дека добавление элементов, доступ к «вершине» и удаление элемента возможны с обоих концов списка.

Использование рекурсии при работе со списками.

Рекурсия является одним из удобнейших средств при работе с линейными списками. Она позволяет сократить код программы и сделать алгоритмы обхода узлов деревьев и списков более понятными.

По определению понятия, рекурсивная процедура - это процедура, в теле которой есть обращение к самой себе. Для того, чтобы процесс рекурсии не стал бесконечным и не вызвал переполнение стека, в каждой рекурсивной процедуре должен быть определен ограничитель рекурсии, блокирующий дальнейшее «размножение» тела процедуры.

Хотя рекурсии в списках не являются настолько очевидным решением, как в деревьях, все же они позволяют оптимизировать обработку линейных списков. В списках возможны два варианта прохода: из начала в конец и из конца в начало. Эти методы реализуются очень легко в случае с двунаправленными списками.

Рекурсию в линейных списках демонстрирует следующий пример: подсчет числа элементов в линейном однонаправленном списке.

Procedure Count_El ( q : El; var count : integer);

Begin

if q < > nil { ограничитель рекурсии }

then begin

inc (count);

Count_El( q^.next , count);

end

End;

Графическая иллюстрация рекурсии для обработки списка

При входе в процедуру count = 0 ,а q=first (указатель на первый элемент списка).

Далее рекурсивная процедура работает так.

Анализируется значение указателя, переданного в процедуру. Если он не равен Nil (список не закончился), то счетчик числа элементов увеличивается на 1.

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

Вызванная процедура работает точно так же: считает, вызывает процедуру и переходит в состояние ожидания.

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

Этот процесс продолжается до тех пор, пока очередное значение адреса не станет равным Nil (признак окончания списка).

В последней вызванной рекурсивной процедуре уже не происходит очередного вызова, так как не соблюдается условие q<>nil, срабатывает «ограничитель рекурсии». В результате процедура завершается без выполнения каких-либо действий, а управление возвращается в «предпоследнюю», вызывающую процедуру. Точкой возврата будет оператор, стоящий за вызовом процедуры, в данном тексте - End, и «предпоследняя» процедура завершает свою работу, возвращая управление в вызвавшую её процедуру.

Начинается процесс «сворачивания» цепочки ожидающих завершения процедур. Счетчик count, вызывавшийся по ссылке, сохраняет накопленное значение после завершения всей цепочки вызванных рекурсивных процедур.

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

Мультисписки