16.2. Работа со стеком

Стек – это структура данных, организованная по принципу «первый вошел – последний вышел». Образно это можно представить как запаянную с одной стороны трубку, в которую закатываются шарики:

Первый шарик всегда будет доставаться из трубки последним. Элементы в стек можно добавлять или извлекать только через его вершину. Программно стек реализуется в виде однонаправленного списка с одной точкой входа (вершиной стека).

Для работы со стеком можно определить следующий тип:

Type Tps=^Ts; // Указатель на запись

Ts=Record; // Сама запись элемента стека

inf:TInf; // Информационная часть элемента стека,

// например Tinf=String

Ps: Tps; // Указатель на предыдущий элемент стека

End;

Графически стек с тремя элементами можно представить следующим образом:

Рис.16.1. Структура стека

Здесь P – указатель на вершину стека. Самый первый элемент стека не имеет впереди себя других элементов, поэтому в указатель Ps записывается пустой указатель – Nil. Следует помнить, что процедуры освобождения памяти Dipose и FreeMem не полагают освобождаемый указатель константе Nil.

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

Inf₃

Ps₃

Inf₂

Ps₂

Inf₁

Ps₁=nil

P

unit Ustack;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

Type

TForm1 = class(TForm)

Memo1: TMemo;

Memo2: TMemo;

Button1: TButton;

Button2: TButton;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

type Tps=^Ts; // Определяет тип элемента стека

Ts=record

inf:word; // Информационная часть элемента стека

ps:Tps; // Указатель на предыдущий элемент стека

end;

var p:Tps; // Указатель на вершину стека

const n=10; // Размерность стека

implementation

{$R *.dfm}

// Процедура добавления нового элемента в стек

Procedure AddStack(var P:Tps; n:word);

var pt:Tps;

Begin

new(pt); // Выделяем память для нового элемента стека

pt^.inf:=n; // Записываем новое число в элемент стека

pt^.ps:=p; // Запоминаем указатель на предыдущий элемент стека

p:=pt; // Возвращаем этот новый указатель на вершину стека

end;

// Процедура извлечения числа из стека с освобождением памяти

Procedure FromStack(var p:Tps;var n:word);

var pt:Tps;

Begin

if p<>nil then Begin

pt:=p; // Запоминаем старое значение вершины стека

n:=p^.inf; // Извлекаем число из текущего элемента стека

p:=p^.ps; // Устанавливаем новый указатель на вершину стека

dispose(pt); // Освобождаем память старого элемента стека

end else n:=0;

end;

// Процедура однократного прохода по стеку и замены значений соседних

// элементов стека, если их значения в направлении от вершины ко дну стека

// не возрастаютProcedure exchange(var p:Tps; var n:word);

var nt:word;

Begin

if p^.ps<>nil then Begin // Проверка наличия следующего элемента стека

if p^.inf>p^.ps^.inf then Begin // Проверка на возрастание значений стека

nt:=p^.inf; // Запоминаем значение числа в вершине стека

p^.inf:=p^.ps^.inf; // Переставляем числа соседних элементов стека

p^.ps^.inf:=nt;

inc(n); // Увеличиваем счетчик перестановок на единицу

end;

exchange(p^.ps,n); // Рекурсивно вновь вызываем процедуру перестановок

end;

end;

// Процедура упорядочения элементов стека методом «пузырька»

Procedure SortStack(var p:Tps);

var n:word;

Begin

Repeat // Открытие цикла упорядочений

n:=0;// Счетчик числа перестановок за один проход полагаем равным нулю

exchange(p,n); // Вызываем процедуру однопроходного упорядочения

// Продолжаем цикл, пока не будет ни одной перестановки

until n=0;

end;

// Процедура формирования начального стекаprocedure TForm1.Button1Click(Sender: TObject);

var i,j:integer;begin

randomize; // Инициируем датчик случайных чисел

memo1.Clear;// Очищаем текстовый редактор Memo1

p:=nil; // Указатель на вершину стека полагаем равным константе nil

for i:=1 to n do Begin // Открываем цикл записей в стек

j:=random(20); // Получаем случайное число

addstack(p,j); // Записываем его в стек

memo1.lines.Add(inttostr(j)); // Выводим его значение в Memo1

end;

end;

// Процедура упорядочения элементов стека и вывод результата

procedure TForm1.Button2Click(Sender: TObject);

var k:word;

begin

memo2.Clear; // Очистка Memo2

SortStack(p); // Сортировка стека

while p<>nil do Begin // Проход по стеку

Fromstack(p,k); // Извлечение элемента из стека и освобождение памяти

Memo2.Lines.Add(inttostr(k)); // Запись элемента стека в Memo2

end;

end;

end.