Использование стека

При разработке алгоритмов трансляции арифметических выраже­ний широко используются наборы данных со стековой организацией. Стек - это упорядоченный набор элементов, в котором внесение новых элементов и выборка имеющихся осуществляются в соответствии с дисциплиной LIFO (Last In - First Out), когда пос­ледний внесенный элемент удаляется первым. Графически стек можно представить в виде бесконечной в одну сторону последовательности слов памяти, причем запись и чтение данных возможны только c од­ного конца, называемого вершиной стека, что показано на рис. 3.

В простейшем случае при работе со стеком определены две опе­рации:

1) занесение элемента в стек;

2) выборка (извлечение) элемента из стека.

При занесении в стек новый элемент размешается следующим за вершиной и сам становится вершиной cтека. При выборке элемента из стека удаляется только один верхний элемент, т.е. вершина. Иногда разрешается считывать элементы, находящиеся ниже вершины, но не допускается изменять их значения или добавлять новые элементы ни­же вершины. Пример работы со стеком приведен на рис. 4.

Рис. 3. Стек

Рис. 4. Пример работы со стеком

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

type Stack = record

top: integer; {вершина стека}

element: array [1..Max] of real {элементы стека}

end;

Операция записи элемента x в стек S выполняется процедурой Push.

procedure Push(x: real; var S: Stack);

Дата добавления: 2015-06-28