Стек — это упорядоченный набор элементов, причем при обращении к нему можно получить доступ лишь к одному из элементов. Этот элемент называется вершиной стека. Число элементов стека (его длина) является переменным. Добавления или удаления можно делать только на вершине стека, поэтому его называют магазинным списком, или списком, организованным по принципу "последним вошел - первым вышел" (last-in-first-out — LIFO).
Для реализации стека необходим набор ячеек памяти, в которые будут заноситьсяего элементы. Типичный подход проиллюстрирован на рис. 1.25. В основной (или виртуальной) памяти для стека резервируется блок смежных ячеек. Большую часть времени он частично заполнен элементами стека. Для обеспечения нормальной работы нужно помнить следующие адреса, которыехранятся в регистрах процессора.
• Указатель стека. Содержит адрес вершины стека. Если в стек добавляется новый элемент (PUSH) или из него удаляется элемент (POP), указатель соответственно увеличивается или уменьшается на единицу. После этого он вновь содержит адрес вершины стека.
• База стека. Содержит адрес нижней ячейки зарезервированного блока. При добавлении элемента в пустой стек, эта ячейка используется первой. При попытке извлечь элемент из пустого стека генерируется сигнал ошибки.
• Предел стека. Содержит адрес второго конца, т.е. вершины зарезервированного блока. При попытке добавить новый элемент в заполненный стек генерируется сигнал ошибки.
Традиционно сложилось так, что у большинства современных машин основойстека является ячейка с максимальным адресом, а его пределом — ячейка с минимальным адресом. Таким образом, стек является обращенным, и при его возрастании заполняются ячейки с убывающими адресами.