Материал: Мансуров. Основы программирования в среде Lazarus. 2010

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

Pop_Stack. Сначала реализуем стек с помощью массива, рисунок 4.26.

N Глубина стека Рис. 4.26 Реализация стека на основе массивов.

Из рисунка видно, что для реализации стека нам нужны два массива, мас-

сив-указатель, назовем его ukaz[1..3] и массив-тело стека, назовем его

CTEK. Для определенности пусть он состоит из 100 элементов, т.е. глубина сте-

ка равна 100 элементам. Пусть, также для определенности, элементами стека являются просто целые числа. На практике элементами стека могут являться и более сложные структуры, например, записи. В массиве ukaz первый элемент,

т.е. ukaz[1] содержит индекс массива СТЕК, равный началу стека, обычно это

1. Элемент ukaz[3] содержит индекс массива СТЕК, равный концу стека, т.е.

заданной глубине стека N = 100 и обычно совпадает с максимальным размером массива СТЕК. Элемент массива ukaz[2] – это индекс в массиве СТЕК, куда будет помещен новый элемент стека, а ukaz[2]-1 это индекс, по которому из

СТЕК можно будет взять последний помещенный в него элемент.

Программа будет выводить на экран меню, с помощью которого можно помещать новый элемент в стек, брать элемент из верхушки стека и просматри-

341

4.3 Динамические структуры данных

____________________________________________________________________

вать весь массив стека.

program project1; {$mode objfpc}{$H+} uses

CRT, FileUtil; const

SizeOfArray = 100; type

c= array[1..SizeOfArray] of integer; u= array[1..3] of integer;

var

choose: integer; EMPTY: boolean; ERROR: boolean; CTEK: c;

ukaz: u; ELEM: integer;

{ ================================================= } procedure Put_Stack(var ELEM: integer; var CTEK: c;

var ukaz: u; var ERROR: Boolean); { ================================================= }

var k: integer; begin

if ukaz[2] > ukaz[3] then ERROR:= true

else begin

342

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

k:= ukaz[2]; CTEK[k]:= ELEM; ukaz[2]:= k + 1;

end;

end;

{ ================================================== } procedure Take_Stack(var ELEM: integer; var CTEK: c;

var ukaz: u; var EMPTY: Boolean); { ================================================== } var k: integer;

begin

if ukaz[2] <= ukaz[1] then EMPTY:= true

else begin

k:= ukaz[2] - 1; ELEM:= CTEK[k]; ukaz[2]:= k;

end;

end;

procedure View_Stack(var CTEK: c; var ukaz: u); var

i: integer; begin

writeln(UTF8ToConsole('Массив стека')); for i:= 1 to ukaz[2] - 1 do

write(CTEK[i], ' '); writeln;

343

4.3 Динамические структуры данных

____________________________________________________________________

end;

begin

{Инициализация стека}

ukaz[1]:= 1;

ukaz[2]:= 1;

ukaz[3]:= SizeOfArray;

repeat

EMPTY:= false;

ERROR:= false;

writeln(UTF8ToConsole('Выберите нужный режим работы :'));

writeln(UTF8ToConsole('Введите новый элемент стека')); readln(ELEM);

Put_Stack(ELEM, CTEK, ukaz, ERROR); if ERROR then

begin

writeln(UTF8ToConsole('Переполнение стека.')); writeln(UTF8ToConsole('Увеличьте размер массива')); writeln(UTF8ToConsole('Нажмите любую клавишу')); readkey;

end;

end;

344

Глава 4 Типовые алгоритмы обработки информации

____________________________________________________________________

2: begin

Take_Stack(ELEM, CTEK, ukaz, EMPTY); if EMPTY then

writeln(UTF8ToConsole('Стек пуст')) else

writeln(UTF8ToConsole('Из стека взят элемент '), ELEM);

end;

3: View_Stack(CTEK, ukaz); end; { end of case }

until choose = 4; end.

Процедура Put_Stack просто помещает новый элемент в массив СТЕК по индексу ukaz[2] и затем увеличивает значение этого индекса на единицу.

Перед этим процедура проверяет стек на переполнение, т.е. не перешли ли мы за пределы массива СТЕК.

Процедура Take_Stack возвращает элемент массива СТЕК с индексом ukaz[2]-1 и уменьшает значение индекса на единицу. Перед этим она прове-

ряет не пуст ли уже стек.

Если внимательно присмотреться к процедурам Put_Stack и Take_Stack, то возникает вполне резонный вопрос, а зачем, собственно гово-

ря, здесь нужен массив-указатель ukaz? И мы будем абсолютно правы. При реализации стека вполне можно обходиться одним массивом, только для раз-

мещения элементов стека. А в качестве указателя использовать простую цело-

численную переменную, которую назовем также ukaz. Вот листинг другой,

улучшенной реализации стека:

345