Реализация стека

Откат

Стеки

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

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

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

Для реализации стека резервируют подряд расположенные ячейки памяти. Размер свободной области памяти, выделенной для размещения стека, ограничивает его размеры (количество элементов, умноженное на размер каждого элемента, если они однотипны).

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

Полная система стека предполагает наличие процедур для записи и удаления элементов стека, а также для проверки перед этими операциями, не пуст ли стек или не наполнен ли он до конца области памяти.

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

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

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

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

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