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

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

Арифметические сопроцессоры, программируемые микрокалькуляторы и язык 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; Пример Литература Дополнительная литература