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

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

Таким образом, по мере проталкивания и выталкивания записей вершина стека перемещается вперед и назад в пределах зарезервированного блока ячеек памяти. Для того чтобы отслеживать положение вершины, ее адрес хранится в дополнительной ячейке памяти, называемой указателем стека (stack pointer). To есть указатель стека — это указатель на вершину стека.

Система стека работает следующим образом (рис. 3): для того чтобы протолкнуть в стек новую запись, значение указателя стека переопределяется — теперь он указывает на свободное место за вершиной стека. Затем на это место записывается новый элемент. Чтобы вытолкнуть элемент из стека, мы считываем данные, на которые указывает указатель стека, а затем переопределяем этот указатель, чтобы он указывал на предыдущую запись в стеке.

Рисунок 3 – Стек в памяти компьютера

Как и для списков, программисту, очевидно, будет удобнее написать процедуры для выполнения операций проталкивания и выталкивания и использовать стек как абстрактный инструмент. Обратите внимание, что эти процедуры должны обрабатывать такие случаи, как попытки выталкивания записей из пустого стека и проталкивания элементов в полный стек. Таким образом, полная система стека предполагает наличие процедур для проталкивания и выталкивания записей, а также для проверки, пуст ли стек и есть ли в нем свободные места.

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

Контрольные вопросы

1. Что такое стек в концептуальном и физическом представлении?

2. Как операции осуществляются с элементами стека? Покажите на схеме.

3. Как называются функции помещения в стек и выборки из стека?

4. На какой элемент стека ссылается его указатель?

5. Что означает принцип LIFO?

Лекция № 25 Очереди и деревья