На этом шаге мы рассмотрим стеки..
Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека.
Рис.1. Схематичное изображение стека
В организации стека используется доступ по принципу "последней пошел, первый вышел". Такой метод доступа называют методом LIFO (Last-In, First-Out). Представим себе стопку тарелок. Нижняя тарелка из этой стопки будет использована последней, а верхняя тарелка, которая была установлена в стопку последней, будет использована первой. Стеки широко используются в системном программном обеспечении, включая, компиляторы и интерпретаторы.
- начальное формирование стека (запись первой компоненты);
- добавление компоненты в стек;
- выборка компоненты (удаление).
- При описании алгоритмов, использующих структуру стек, принята специальная терминология; так говорят: "Поместим элемент
в верхушку стека" или "Снимем верхний элемент стека". Внизу стека находится наименее доступный элемент, и он не удаляется до тех пор,
пока не будут исключены все другие элементы. Часто говорят, что "элемент опускается в стек" ("push down") или что "стек
поднимается" ("pop up"), если исключается верхний элемент.
Термины "опустить" и "поднять" ошибочно предполагают движение всего списка в памяти компьютера, однако физически ничего не опускается; элементы просто добавляются сверху.
Итак, в стеке доступна единственная его позиция, называемая вершиной стека - это позиция, в которой находится последний по времени поступления в стек элемент.
Напомним, что описание компоненты стека будет следующим:
Type PtrRec = ^Rec; Rec = Record Element : TypeElement; {информационное поле компоненты стека} pNext : PtrRec; {ссылка на следующую компоненту стека} End;
Для формирования стека и работы с ним необходимо описать две переменные типа указатель: pTop определяет вершину стека, pAux - вспомогательная.
Var
pTop, pAux : PtrRec;
На следующем шаге мы рассмотрим формирование стека и добавление нового элемента.
