Программирование. Стеки Pascal-Паскаль

Стеки Pascal-Паскаль

Линейные списки, в которых операции вставки, удаления и доступа к значениям выполняются в первом или последнем узле, получили следующие названия:

  1. Стек - особый вид списка, обращение к которому идет только через указатель на первый элемент. Если в стек нужно добавить элемент, то он добавляется впереди первого элемента, при этом указатель на начало стека переключается на новый элемент. Алгоритм работы со стеком характеризуется правилом: «последним пришел - первым вышел» (LIFO, last in - first out).
  2. Очередь - это вид списка, имеющего два указателя на первый и последний элемент цепочки. Новые элементы записываются вслед за последним, а выборка элементов идет с первого. Этот алгоритм типа «первым пришел - первым вышел» (FIFO, first in - first out).
  3. Дек или двусторонняя очередь - это линейный список, в котором все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются на обоих концах списка.

Стеки

Интуитивными моделями стека могут служить колода карт на столе при игре в покер, стопка тарелок на полке буфета; во всех этих моделях взять можно только верхний предмет, а добавить новый объект можно, только положив его на верхний. Стеки также иногда называют «магазинами» по аналогии с магазином патронов, в этом случае патрон, помещенный в магазин первым, выстреливает последним.

Механизм работы стека можно представить, если воспользоваться аналогией с железнодорожным разъездом, которая предложена Э. Дейкстрой.

Схема стека

Со стеками обычно выполняются следующие действия:

  • Очистка стека;
  • Считывание элемента из вершины стека;
  • Удаление элемента из вершины стека;
  • Вставка элемента в вершину стека;
  • Проверка, является ли стек пустым.