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

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

Арифметические сопроцессоры, программируемые микрокалькуляторы и язык Forth используют стековую модель вычислений.

В ЦВК стек называется магазином - по аналогии с магазином в огнестрельном оружии (стрельба начнётся с патрона, заряженного последним)

Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.

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

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

• добавление элемента в стек;

• удаление элемента из стека;

• проверка, пуст ли стек;

• просмотр элемента в вершине стека без удаления;

• очистка стека.

Как и у всего хорошего в этом мире, у стека есть предел или размер. То есть вы не можете бесконечно помещать в него данные. Как только он достигнет своего лимита, система сгенерирует исключение EXCEPTION_STACK_OVERFLOW (исключение переполнения стека). Чуть позже мы рассмотрим все подробности этой операции. По умолчанию, размер стека равен одному мегабайту. Это значение можно изменить с помощью опции линкера «/STACK». Для каждого потока система организует свой стек.

Последняя переданная страница стека всегда имеет установленный флаг PAGE_GUARD (охрана страницы).

ПРИМЕЧАНИЕ

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

Когда происходит обращение к этой странице, система генерирует исключение EXCEPTION_GUARD_PAGE (исключение охраны страницы).

Если оно возникло при обращении к страницам стека, то система обрабатывает его сама. Во всех остальных случаях исключение передается приложению. Я не знаю, на каком уровне система определяет, что это исключение стека, но знаю, на основе каких данных она это делает. Об этом чуть позже.

ПРИМЕЧАНИЕ

Обработчик исключения EXCEPTION_GUARD_PAGE снимает атрибут PAGE_GUARD со страницы, на которой произошла ошибка, и пытается передать следующую страницу. Если следующая страница является последней, то она не передается и обработчик генерирует EXCEPTION_STACK_OVERFLOW. Если же она не последняя – страница передается с флагами PAGE_GUARD и PAGE_READWRITE, и становится очередной сторожевой страницей стека потока.

Таким образом, система должна знать, как минимум три вещи о стеке как о структуре:

• Адрес начала стека или базу стека.
• Адрес последней зарезервированной страницы стека.
• Адрес последней переданной не сторожевой страницы. Этот адрес называется лимитом стека.

ПРИМЕЧАНИЕ

На самом деле система использует следующую структуру для управления стеком: —- Можно предположить,что первые два поля являются устаревшими и игнорируются. По крайней мере, в [2] и в kernel32.dll при создании потока они обнуляются. Адрес базы и стека можно найти в TIB – Thread Information Block (Информационный блок потока). Для работы со стеком необходим указатель вершины стека. Основные операции над стеком следующие: «запомнить в стеке» и «извлечь из стека» (причем извлекается последний из занесенных в стек элементов - то есть элемент с вершины стека). Поэтому говорят, что стек – это структура типа LIFO - »Last In - First Out» - «последним зашел - первым вышел». Для представления стека в программе обычно используется одномерный массив (назовем его B), нумерация элементов которого начинается с нуля. В этом нулевом элементе массива хранится индекс первого свободного места в массиве (т.е. увеличенный на 1 индекс вершины стека). Если массив пуст, то указатель равен 1 (B[0]=1). Добавление элемента X в стек реализуется очень просто - на первое свободное место (индекс которого хранится в B[0]) помещается X, после чего индекс первого свободного места увеличивается на 1: B[B[0]]:=x; { Занести в стек } B[0]:=B[0]+1; { Увеличить указатель } Если необходимо извлечь элемент X из стека, то берется последний из занесенных элементов (естественно, только в том случае, если стек непуст), и указатель на первое свободное место уменьшается на 1: if B[0]<>1 { Если стек не пуст } then begin x:=B[B[0]]; { Взять элемент } B[0]:=B[0]-1; { Уменьшить указатель } end; Пример Литература Дополнительная литература