Явное использование стека

Стеком называется структура данных, в которой добавление и извлечение данных происходит с одного конца, называемого вершиной стека (рис. 13). Наглядным образом стека может служить стопка тарелок – добавлять или забрать тарелки можно только сверху. Каждая тарелка соответствует элементу данных.

Рис. 13. Наглядное представление стека. Push (проталкивание) – традиционное название для операции добавления данных в стек, Pop (выталкивание) – традиционное название для операции извлечения данных из стека.

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

При рекурсивных вызовах стек вызовов хранит цепочку из данных об одновременно работающих процедурах. Во всех продвинутых средах разработки эту цепочку вместе с запомненными параметрами процедур можно просмотреть во время отладки. Соответствующая команда обычно называется “Call Stack” (в Delphi ей соответствует сочетание клавиш Ctrl – Alt – S).

Универсальный способ избавиться от рекурсии – это самостоятельно запрограммировать те действия со стеком, которые фактически происходят, когда вы используете рекурсивные вызовы. Покажем, как это можно сделать, на примере дважды вызывающей себя рекурсивной процедуры.

Для начала реализуем в виде класса стек, хранящий параметры процедуры:

type //Запись для хранения параметров процедур Parameters = record //Список параметров end;   //Стек удобно реализовать с помощью связанных списков //(http://www.tvd-home.ru/prog/16_4) PList = ^List; List = record Data: Parameters; Next: PList; end;   //Описанный одновсязанный список соединим с методами //добавления и удаления элементов и получим стек. Stack = class private StackTop: PList; public //Добавление данных procedure Push(NewData: Parameters); //Извлечение данных function Pop: Parameters; //Проверка наличия данных function Empty: boolean; end;   implementation   //Добавление данных procedure Stack.Push(NewData: Parameters); var NewElement: PList; begin New(NewElement); NewElement^.Data:= NewData; NewElement^.Next:= StackTop; StackTop:= NewElement; end;   //Извлечение данных function Stack.Pop: Parameters; var PopedElement: PList; begin PopedElement:= StackTop; StackTop:= StackTop^.Next; Pop:= PopedElement^.Data; Dispose(PopedElement); end;   //Проверка наличия данных function Stack.Empty: boolean; begin Empty:= StackTop = nil; end;

Рассмотрим обобщенную рекурсивную процедуру с двумя вызовами самой себя.

procedure Recurs(P1: Parameters); begin DoSomething(P1); if <условие> then begin P2:= F(P1); Recurs(P2); P3:= G(P1); Recurs(P3); end; end;

В данной процедуре некоторые действия (DoSomething) выполняются много раз при разных значениях параметров. Нерекурсивный аналог должен хранить эти параметры в стеке. Каждый рекурсивный вызов будет соответствовать добавлению очередных параметров в стек. Вместо рекурсии появляется цикл, который выполняется, пока в стеке есть необработанные параметры.

procedure NonRecurs(P1: Parameters); var S: Stack; P: Parameters; begin S:= Stack.Create; S.Push(P1); while not S.Empty do begin P1:= S.Pop; DoSomething(P1); if <условие> then begin P3:= G(P1); S.Push(P3); P2:= F(P1); S.Push(P2); end; end; end;

Обратите внимание, что рекурсивные вызовы шли сначала для параметров P2, потом для P3. В нерекурсивной процедуре в стек отправляются сначала параметры P3, а только потом P2. Это связано с тем, что при рекурсивных вызовах в стек, по сути, отправляется недовыполненная часть процедуры, которая в нашем случае содержит вызов Recurs(P3).[21]

Дата добавления: 2015-08-09