Стек является чрезвычайно удобной структурой данных для
многих задач вычислительной техники. Наиболее типичной из таких
задач является обеспечение вложенных вызовов процедур.
Предположим, имеется процедура 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.
В микропроцессорах семейства Intel, как и в большинстве сов-
ременных процессорных архитектур, поддерживается аппаратный стек.
Аппаратный стек расположен в ОЗУ, указатель стека содержится в
паре специальных регистров - SS:SP, доступных для программиста.
Аппаратный стек расширяется в сторону уменьшения адресов, указа-
тель его адресует первый свободный элемент. Выполнение команд
CALL и INT, а также аппаратных прерываний включает в себя запись
в аппаратный стек адреса возврата. Выполнение команд RET и IRET
включает в себя выборку из аппаратного стека адреса возврата и
передачу управления по этому адресу. Пара команд - PUSH и POP -
обеспечивает использование аппаратного стека для программного ре-
шения других задач.
Системы программирования для блочно-ориентированных языков
(PASCAL, C и др.) используют стек для размещения в нем локальных
переменных процедур и иных программных блоков. При каждой активи-
зации процедуры память для ее локальных переменных выделяется в
стеке; при завершении процедуры эта память освобождается. Пос-
кольку при вызовах процедур всегда строго соблюдается вложен-
ность, то в вершине стека всегда находится память, содержащая ло-
кальные переменные активной в данный момент процедуры.
Этот прием делает возможной легкую реализацию рекурсивных
процедур. Когда процедура вызывает сама себя, то для всех ее ло-
кальных переменных выделяется новая память в стеке, и вложенный
вызов работает с собственным представлением локальных переменных.
Когда вложенный вызов завершается, занимаемая его переменными об-
ласть памяти в стеке освобождается и актуальным становится предс-
тавление локальных переменных предыдущего уровня. За счет этого в
языках PASCAL и C любые процедуры/функции могут вызывать сами се-
бя. В языке PL/1, где по умолчанию приняты другие способы разме-
щения локальных переменных, рекурсивная процедура должна быть оп-
ределена с описателем RECURSIVE - только тогда ее локальные
переменные будут размещаться в стеке.
Рекурсия использует стек в скрытом от программиста виде, но
все рекурсивные процедуры могут быть реализованы и без рекурсии,
но с явным использованием стека. В программном примере 3.17 при-
ведена реализация быстрой сортировки Хоара в рекурсивной процеду-
ре. Программный пример 4.2 показывает, как будет выглядеть другая
реализация того же алгоритма.
{==== Программный пример 4.2 ====}
{ Быстрая сортировка Хоара (стек) }
Procedure Sort(a : Seq); { см. раздел 3.8 }
type board=record { границы обрабатываемого участка }
i0, j0 : integer; end;
Var i0, j0, i, j, x : integer;
flag_j : boolean;
stack : array[1..N] of board; { стек }
stp : integer; { указатель стека работает на увеличение }
begin { в стек заносятся общие границы }
stp:=1; stack[i].i0:=1; stack[i].j0:=N;
while stp>0 do { выбрать границы из стека }
begin i0:=stack[stp].i0; j0:=stack[stp].j0; stp:=stp-1;
i:=i0; j:=j0; flag_j:=false;{проход перестановок от i0 до j0}
while i<j do { пока не встретятся i и j }
begin if a[i]>a[j] then { перестановка }
begin x:=a[i]; a[i]:=a[j]; a[j]:=x; flag_j:= not flag_j;
end;
if flag_j then Dec(j) else Inc(i);
end; if i-1>i0 then {занесение в стек границ левого участка}
begin stp:=stp+1; stack[stp].i0:=i0; stack[stp].j0:=i-1;
end; if j0>i+1 then {занесение в стек границ правого участка}
begin stp:=stp+1; stack[stp].i0:=i+1; stack[stp].j0:=j0;
end; end;
Один проход сортировки Хоара разбивает исходное множество на
два множества. Границы полученных множеств запоминаются в стеке.
Затем из стека выбираются границы, находящиеся в вершине, и обра-
батывается множество, определяемое этими границами. В процессе
его обработки в стек может быть записана новая пара границ и т.д.
При начальных установках в стек заносятся границы исходного мно-
жества. Сортировка заканчивается с опустошением стека.