Стеки и очереди

Значение стека как структуры данных в программировании не исчерпывается лишь стеком отложенных заданий. В этом разделе мы решим с помощью стека задачу о вычислении значения арифметического выражения, заданного своей постфиксной (“польской”) записью. Пусть, например, требуется вычислить значение выражения ((6+7)*3)-(8*(9-5)), тогда его постфиксная запись будет иметь вид 67+3*895-*-. Алгоритм преобразования инфиксной (обычной) записи в постфиксную известен, он также использует стек, но здесь мы не будем его рассматривать. Поскольку числа в выражении могут состоять не только из одной цифры, мы примем постфиксную запись в виде #6#7+#3*#8#9#5-*- , где символ # означает начало очередного числа. Алгоритм решения этой задачи довольно прост и широко известен: будем брать из постфиксной записи по одному элементу (числу или знаку операции): если взято число, просто поместим его в стек, если взят знак операции, то возьмем из стека два числа, выполним над ними эту операцию и поместим результат в стек. Когда все элементы постфиксной записи обработаны, в стеке окажется значение выражения.

 

Type T_Num_Stack = Array[1..100] Of LongInt;

{В этой программе будем хранить стек в массиве}

Function Value_By_Postfix(Postfix:String):LongInt;

{Функция вычисляет значение выражения, заданного постфиксной записью.}

Function Get_From_Postfix

(Var Postfix:String; Var Op:Char; Var Val:LongInt):Boolean;

{Функция "забирает" из постфиксной записи очередной элемент (число или знак операции) и возвращает True, если это число, и False, если это знак операции. Отработанные символы удаляются из постфиксной записи, так что очередной символ всегда Postfix[1]}

Begin

If Postfix[1]='#' Then Begin {признак числа}

Get_From_Postfix:=True;

Delete(Postfix,1,1);

Val:=0;

While Postfix[1] In ['0'..'9'] Do Begin

{формируем число из цифр по схеме Горнера}

Val:=10*Val+Ord(Postfix[1])-Ord('0');

Delete(Postfix,1,1);

End;

End

Else Begin

Get_From_Postfix:=False;

Op:=Postfix[1];

Delete(Postfix,1,1);

End;

End;

Function Execute(op:Char;x1,x2:LongInt):LongInt;

{Функция выполняет арифметическую операцию, заданную знаком op}

Begin

Case op Of

'+': Execute:=x1+x2;

'-': Execute:=x1-x2;

'*': Execute:=x1*x2;

End;

End;

Var

Stack : T_Num_Stack; {стек для чисел}

Top : Byte; {номер первого элемента стека}

Op : Char;

x1,x2 : LongInt;

Number : Boolean;

Begin

Top:=0; {стек сделали пустым}

While True Do Begin

{условие окончания цикла будет проверено в теле цикла}

Number:=Get_From_Postfix(Postfix,Op,x1);

{взяли из постфиксной записи число или операцию}

If Number Then Begin {взяли число - помещаем его в стек}

Inc(Top);

Stack[Top]:=x1;

End

Else Begin {взяли операцию - извлекаем из стека два числа (обратите внимание, в каком порядке), выполняем над ними операцию и результат помещаем в стек}

x2:=Stack[Top];

Dec(Top);

x1:=Stack[Top];

Dec(Top);

Inc(Top);

Stack[Top]:=Execute(Op,x1,x2);

End;

If Postfix='' Then Begin {постфиксная запись пуста, теперь в стеке находится одно число, которое и есть значение выражения}

Value_By_Postfix:=Stack[Top];

Exit;

End;

End;

End;

Const Postfix : String='#6#7+#3*#8#9#5-*-';

Begin

WriteLn(Postfix,'=',Value_By_Postfix(PostFix));

End.

 

Еще раз внимательно посмотрим, как организовано хранение стека в массиве. Когда мы держали стек в списке, мы по-настоящему добавляли туда элементы и по настоящему удаляли элементы оттуда. Если стек размещен в массиве, то, конечно, этого делать не надо, достаточно лишь иметь одну дополнительную переменную, равную номеру “верхнего” элемента стека, в данной программе это переменная Top. Если стек пуст, то Top=0; чтобы добавить число в стек, достаточно увеличить Top на единицу и записать число в элемент с индексом Top. Чтобы удалить число из стека, достаточно просто уменьшить Top на единицу.

Еще одна структура данных, также уже известная нам, которая часто используется при решении различных задач, - это очередь, или FIFO-структура. Очередь отличается от стека тем, что элемент, попавший туда первым, и извлекается оттуда первым, а не последним, как в стеке. Очередь так же, как и стек, можно хранить и в списке, и в массиве. Реализация очереди в списке не представляет большой сложности, а вот хранение ее в массиве - не вполне тривиальная задача. Рассмотрим ее более подробно. Элементы очереди добавляются в “хвост” массива, а удаляются из “головы”, поэтому очередь по мере ее использования “ползет” по массиву слева направо и, если размер массива не очень велик, может достигнуть края массива, и тогда добавление нового элемента станет невозможным. Использование очень больших массивов, заведомо превышающих любые потребности очереди, неэкономно, а часто и невозможно. Гораздо лучше использовать “закольцованный” массив, в котором за последним элементом массива непосредственно следует первый его элемент. В этом случае очередь, достигнув конца массива, “переползет” в его начало, которое к этому моменту будет уже свободно. Пусть массив Q содержит N элементов, пронумерованных от 0 до N-1. В переменных Top и Len будем хранить номер “верхнего” элемента очереди и длину (количество элементов) очереди. В начальный момент очередь пуста иTop=Len=0. Чтобы добавить элемент в очередь, нужно записать добавляемый элемент в элемент массива Q[(Top+Len)Mod N],а затем увеличить Len на единицу, значение Top при этом не изменяется. Чтобы удалить элемент из очереди (всегда удаляется только первый элемент), нужно уменьшить Len на единицу и вычислить новое значение Top по формуле Top=(Top+1) Mod N. Решим, используя очереди, такую задачу: напечатать в порядке возрастания первые n натуральных чисел, в разложение которых на простые множители входят только числа 2, 3 и 5. Будем хранить очереди в массивах. Один из алгоритмов решения этой задачи таков: организуем три очереди Q2,Q3 и Q5. Выведем число 1 и добавим в очередь Q2 число 2, в Q3 число 3 и в Q5 число 5. Затем в цикле от 2 до n:

- найдем элемент m, наименьший из первых элементов очередей;

- удалим этот элемент из всех очередей, где он является первым;

- выведем этот элемент и добавим в Q2 число 2m, в Q3 число 3m и в Q5 число 5m.

 

Const n=240;

Type Queue = Object {объект - очередь}

Body : Array[0..n-1] Of LongInt;

Top : 0..n-1;

Len : 0..n;

Procedure Clear;

Procedure Add(x:LongInt);

Procedure Get(Var x : LongInt);

Function Upper : LongInt;

End;

Procedure Queue.Clear; {процедура делает очередь пустой}

Begin

Len:=0;

Top:=0;

End;

Procedure Queue.Add(x:LongInt); {процедура добавляет элемент в очередь}

Begin

Body[(Top+Len)Mod n]:=x;

Inc(Len);

End;

Procedure Queue.Get(Var x : LongInt);

{процедура забирает элемент из очереди}

Begin

x:=Body[Top];

Top:=(Top+1) Mod n;

Dec(Len);

End;

Function Queue.Upper:LongInt;

{функция возвращает первый элемент очереди, но не удаляет его}

Begin

Upper:=Body[Top];

End;

Procedure Add_And_Print(t:LongInt; Var Q2,Q3,Q5:Queue);

Begin

Write(t:8);

Q2.Add(2*t);

Q3.Add(3*t);

Q5.Add(5*t);

End;

Var

Q2,Q3,Q5 : Queue;

m,x : LongInt;

k : Word;

Begin

Q2.Clear; {делаем все очереди пустыми}

Q3.Clear;

Q5.Clear;

Add_And_Print(1,Q2,Q3,Q5);

{выводим 1 и добавляем в очереди 2,3,5}

k:=1;

While k<n Do Begin

m:=Q2.Upper; {находим наименьший из первых элементов}

If m>Q3.Upper Then m:=Q3.Upper;

If m>Q5.Upper Then m:=Q5.Upper;

Add_And_Print(m,Q2,Q3,Q5);

{выводим его и добавляем новые элементы в очереди}

If m=Q2.Upper Then Q2.Get(x);

{удаляем первый элемент, если он равен m}

If m=Q3.Upper Then Q3.Get(x);

If m=Q5.Upper Then Q5.Get(x);

Inc(k);

End;

WriteLn;

End.