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

Одной из важных концепций в программировании является концепция стека. Стеком называется упорядоченный набор элементов, в котором добавление новых элементов и удаление существующих выполняется только с одного его конца, который называется вершиной стека. Бытовой иллюстрацией стека может служить стопка книг. Добавить к ней очередную книгу можно, положив новую поверх остальных. Верхняя книга (элемент стека) и есть вершина стека. Просматривать книги можно только по одной, снимая их с вершины. Чтобы получить книгу из середины стека, надо задать критерий отбора и удалять элементы-книги из стека до тех пор, пока не будет найдена нужная книга. Элементы из стека могут удаляться, пока он не станет пустым. Таким образом, над стеком выполняются следующие операции:

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

2) определение пуст ли стек;

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

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

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

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

Другим специальным видом использования списка является очередь. Существуют различные разновидности очередей, здесь будет рассмотрена простая бесприоритетная очередь. При этом добавление элементов производится в конец очереди, а выборка и удаление элементов - из начала. Принцип доступа к очереди – «первым пришел - первым ушел» (first in - first out, FIFO). Принцип обработки как для стека, так и для очереди определяет набор соответствующих процедур. Для реализации очереди необходим список, для которого известны адрес первого и адрес последнего элементов. Таким образом, над очередью выполняются следующие операции:

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

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

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

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

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

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