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

Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники. Наиболее типичной из таких задач является обеспечение вложенных вызовов процедур.

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

Один проход сортировки Хоара разбивает исходное множество на два множества. Границы полученных множеств запоминаются в стеке. Затем из стека выбираются границы, находящиеся в вершине, и обрабатывается множество, определяемое этими границами. В процессе его обработки в стек может быть записана новая пара границ и т.д. При начальных установках в стек заносятся границы исходного множества. Сортировка заканчивается с опустошением стека.

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

Объект называется рекурсивным, если он содержит сам себя или определен с помощью самого себя.

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

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

Дата добавления: 2015-07-11