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

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

Предположим, имеется функция 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 - только тогда ее локальные переменные будут размещаться в стеке.

Рекурсия использует стек в скрытом от программиста виде, но все рекурсивные функции могут быть реализованы и без рекурсии, но с явным использованием стека. В программном примере 1.15 лекции 4 была приведена реализация быстрой сортировки Хоара в рекурсивной функции. Программный пример 1.2 показывает, как будет выглядеть реализация того же алгоритма но с использованием программного стека.

{==== Программный пример 1.2 ====}

// Быстрая сортировка Хоара (стек)

void SortS(int* mas)

{

struct Board

{

int first, last; // границы обрабатываемого участка

};

Board stack[N]; // стек

bool flag;

int stp = 0, // указатель стека работает на увеличение

i, j, i0, j0, buf;

stack[0].first = 0; // в стек заносятся общие границы

stack[0].last = N-1;

while(stp>=0)

{

i0 = stack[stp].first; // выбрать границы из стека

j0 = stack[stp].last;

stp--;

i = i0; j = j0; flag = false; // проход перестановок от i0 до j0

while(i<j) // пока не встретятся i и j

{

if(mas[i]>mas[j])

{

buf = mas[i]; mas[i] = mas[j]; // перестановка

mas[j] = buf;

flag ^= 1;

}

if(flag) j--; else i++;

}

if(i-1 > i0) // занесение в стек границ левого участка

{

stp++;

stack[stp].first = i0;

stack[stp].last = i-1;

}

if(j0 > i+1) // занесение в стек границ правого участка

{

stp++;

stack[stp].first = i+1;

stack[stp].last = j0;

}

}

}

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

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