====== Структура данных стек ====== **Стек** — (англ. stack — стопка) динамическая [[wpru>структура данных]], представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. Стеки широко используются в вычислительной технике — так для отслеживания точек возврата из подпрограмм [[wpru>стек вызовов]], который является неотъемлемой частью архитектуры большинства современных процессоров. [[wpru>Языки программирования высокого уровня]] используют стек вызовов для передачи параметров при вызове процедур. [[Арифметические сопроцессоры]], программируемые микрокалькуляторы и [[wpru>язык Forth]] используют стековую модель вычислений. В [[wpru>ЦВК]] стек называется магазином - по аналогии с магазином в огнестрельном оружии (стрельба начнётся с патрона, заряженного последним) Наиболее наглядным примером организации стека служит [[детская пирамидка]], где добавление и снятие колец осуществляется как раз согласно определению стека. Добавление элемента, называемое также проталкиванием (push), возможно только в вершину стека (добавленный элемент становится первым сверху), выталкивание (pop) — также только из вершины стека, при этом второй сверху элемент становится верхним. {{:tema:333px-data_stack_svg.png|}} //Стек можно организовать// на базе любой структуры данных, где возможно хранение нескольких однотипных элементов и где можно реализовать определение стека: [[http://xgu.ru/wiki/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B0%D1%81%D1%81%D0%B8%D0%B2_%D0%B2_SolidWorks|линейный массив]], [[http://www.pascaler.ru/pascal/filetype/tipizir/1/|типизированный файл]], [[wpru>однонаправленный]] или двунаправленный список. В нашем случае наиболее подходящим для реализации [[wpru>стека]] является однонаправленный список, причём в качестве вершины [[wpru>стека]] выберем начало этого списка. ====== Типовые операции над стеком и его элементами: ====== * добавление элемента в [[wpru>стек]]; * удаление элемента из [[wpru>стека]]; * проверка, пуст ли [[wpru>стек]]; * просмотр элемента в вершине [[wpru>стека]] без удаления; * очистка [[wpru>стека]]. ====== Размер стека ====== Как и у всего хорошего в этом мире, у стека есть предел или размер. То есть вы не можете бесконечно помещать в него данные. Как только он достигнет своего [[http://slovari.yandex.ru/dict/economic/article/ses2/ses-3239.htm?text=%D0%BB%D0%B8%D0%BC%D0%B8%D1%82 | лимита]], система сгенерирует исключение //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]]"// - "последним зашел - первым вышел". Для представления стека в программе обычно используется [[http://de.ifmo.ru/bk_netra/page.php?index=34&layer=1&tutindex=15 | одномерный массив]] (назовем его 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; [[Пример]] [[Литература]] [[Дополнительная литература]]