Размещение локальных переменных

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

Этот прием делает возможной легкую реализацию рекурсивных процедур. Когда процедура вызывает сама себя, то для всех ее локальных переменных выделяется новая память в стеке, и вложенный вызов работает с собственным представлением локальных переменных. Когда вложенный вызов завершается, занимаемая его переменными область памяти в стеке освобождается и актуальным становится представление локальных переменных предыдущего уровня.

За счет этого в языках PASCAL и С любые процедуры/функции могут вызывать сами себя.

Анализ математических выражений

Рассмотрим математическое выражение, в котором имеется несколько уровней вложения скобок, причем используются три различных типа скобок: квадратные, круглые и фигурные. Закрывающая скобка должна принадлежать к тому же скобочному типу, что и открывающая.

При анализе выражения необходимо не только следить за числом открытых скобок, но и за их типом.

Для решения этой задачи можно воспользоваться стеком. При обнаружении открывающей скобки она заносится в стек. При обнаружении закрывающей скобки анализируется содержимое стека. Если стек пуст, то открывающая скобка отсутствует и выражение составлено неправильно. Если стек не пуст, мы выбираем элемент из стека и проверяем, соответствует ли он типу закрывающей скобки. При совпадении процесс продолжается. В противном случае - ошибка. По окончанию обработки выражения стек должен быть пуст.

Таким образом, возможны четыре варианта окончания анализа выражения:

1. Пришла закрывающая скобка, а стек пуст.

• 2. Тип закрывающей скобки не соответствует типу открывающей скобки в вершине стека.
• 3. После завершения анализа всего выражения стек не пуст.
• 4. После завершения анализа всего выражения стек пуст.

Первые три варианта свидетельствуют о наличии ошибки в выражении, последний - о том, что в выражении скобки расставлены верно.

Использование стека допустимо и при слежении за правильностью вложения циклов и/или условных операторов в языках программирования.

Таким образом, существует ряд задач, для решения которых использование такой структуры, как стек, не только допустимо, но и является наиболее эффективным.

Использование двух стеков

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

В частном случае двух стеков это приводит к простому распределению памяти. Первый стек растет вправо, а второй - влево (рис. 6). При таком распределении один из стеков может занимать больше половины памяти. Переполнение может произойти только в том случае, если суммарный объем двух стеков превосходит выделенный объем памяти.

Рис. 6. Использование двух стеков

Например, если в одном стеке хранятся фамилии студентов, успешно сдавших сессию, а второй - студентов, получивших неудовлетворительные оценки, то очевидно, что число элементов в этих стеках взаимосвязано.

К сожалению, такая организация совместного хранения трех и более стеков невозможна.