Стеки в вычислительных системах

Стеки

Стек – последовательный список с переменной длиной, включение и исключение элементов из которого выполняются с одной стороны списка, называемого вершиной. Другие названия стека – магазин или очередь, функционирующая по принципу LIFO (Last-In-First-Out – «последним пришел - первым исключается»). Основные операции над стеком – включение нового элемента (англ. push заталкивать) и исключение элемента из стека (англ. pop – выскакивать). Полезными могут быть также такие как определение текущего числа элементов в стеке и очистка стека.

Рассмотрим пример, демонстрирующий принцип включения элементов в стек и исключения элементов из стека. На рис. 5.1 изображены состояния стека: пустого (а), после последовательного включения в него элементов с именами 'A', 'B', 'C' (б-г), после последовательного удаления из стека элементов 'C' и 'B' (д, е), после включения в стек элемента 'D' (ж).

Рис 5.1. Включение и исключение элементов из стека.

При представлении стека в статической памяти для него выделяется память, как для вектора. В дескрипторе вектора кроме обычных параметров должен находиться указатель стека – адрес вершины стека. Указатель стека может указывать либо на первый свободный элемент стека, либо на последний записанный в стек элемент. Все равно, какой из этих двух вариантов выбрать, важно впоследствии строго придерживаться его при работе со стеком.

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

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

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

Стек является удобной структурой данных для многих задач вычислительной техники. Наиболее типичной задачей является обеспечение вложенных вызовов процедур. Предположим, имеется процедура A, которая вызывает процедуру B, а та в свою очередь – процедуру C. Когда выполнение процедуры A дойдет до вызова B, процедура A приостанавливается и управление передается на входную точку процедуры B. Когда B доходит до вызова C, приостанавливается B и управление передается на процедуру C. Когда заканчивается выполнение процедуры C, управление должно быть возвращено в B, причем в точку, следующую за вызовом C. При завершении B управление должно возвращаться в A, в точку, следующую за вызовом B.

Правильную последовательность возвратов легко обеспечить, если при каждом вызове процедуры записывать адрес возврата в стек. В результате, когда процедура A вызывает процедуру B, в стек заносится адрес возврата в A; когда B вызывает C, в стек заносится адрес возврата в B. Когда C заканчивается, адрес возврата выбирается из вершины стека – а это адрес возврата в B. Когда заканчивается B, в вершине стека находится адрес возврата в A, и возврат из B произойдет в A.

Языки программирования блочного типа (PASCAL, C и др.) используют стек для размещения локальных переменных процедур и иных программных блоков. При каждой активизации процедуры память для ее локальных переменных выделяется в стеке, а при завершении процедуры память освобождается. Поскольку при вызовах процедур всегда строго соблюдается вложенность, то в вершине стека всегда находится память, содержащая локальные переменные активной в данный момент процедуры.

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

Дата добавления: 2014-01-07