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

Стек является чрезвычайно удобной структурой данных для

многих задач вычислительной техники. Наиболее типичной из таких

задач является обеспечение вложенных вызовов процедур.

Предположим, имеется процедура 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;

Один проход сортировки Хоара разбивает исходное множество на

два множества. Границы полученных множеств запоминаются в стеке.

Затем из стека выбираются границы, находящиеся в вершине, и обра-

батывается множество, определяемое этими границами. В процессе

его обработки в стек может быть записана новая пара границ и т.д.

При начальных установках в стек заносятся границы исходного мно-

жества. Сортировка заканчивается с опустошением стека.