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

Представление стека в виде списка.

Организация данных

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

3.1. Организация данных – стек.

Стекпредставляет собой организацию данных, из которой первым извлекается тот элемент, который был добавлен в нее последним, т. е. последовательность элементов, включение и исключение элементов из которой производится только с одного конца, – таким образом, доступ к элементам происходит по принципу LIFO (last in first out).

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

Если стек пуст, то списка не существует, и указатель стека принимает значение nil.

Операция добавления нового элемента (запись в стек или включение элемента вершины стека) называется операцией проталкивания в стек и имеет общепринятое название Push.

Операция исключения элемента из вершины стека (удаление элемента) называется операцией выталкивания из стека и имеет общепринятое название Pop.

Операции Push и Pop являются безадресными в том смысле, что для их выполнения никакой дополнительной информации о месте размещения элементов не требуется (для этого достаточно указателя стека).

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

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

1. Создание элемента стека:

· выделение памяти под первый элемент стека и внесение в него информации;

· установка вершины стека Тор на созданный элемент.

2. Добавление элемента в стек:

· выделение памяти под новый элемент;

· внесение значения в информационное поле нового элемента и установка связи между ним и старой вершиной стека Тор;

· установка вершины стека Тор на новый элемент.

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

3. Удаление элемента из стека:

· извлечение информации из информационного поля вершины стека Тор в переменную и установка на вершину стека вспомогательного указателя Р;

· перемещение указателя вершины стека Тор на следующий элемент и освобождение памяти, занимаемой старой вершиной стека.

При удалении элемента из стека удаляется последний элемент из памяти, а указатель вершины перемещается к следующему (предпоследнему) элементу.