Очереди и их применение

Стеки

Линейные списки

Линейным списком называется упорядоченная структура, каждый элемент которой связан со следующим элементом. Наибольшее распространение получили два вида линейных списков: стеки и очереди.

Стек это список типа LIFO (последним пришел – первым вышел). Стек имеет одну точку доступа, которая называется вершиной.

Аналогом стека является стопка книг, в которой дополнение и изъятие книг происходит сверху. Другим примером может служить обойма с патронами (магазин), в которой зарядка и подача для стрельбы выполняется с одного конца. Именно этим примером объясняется бывшее в употреблении русскоязычное название стека “магазин”.

Широкое применение нашли стеки в программировании. Иногда они реализуются аппаратным образом. Через стеки передаются параметры при обращении к процедурам. Если имеется цепочка вызова вложенных процедур, то локальные переменные могут сохраняться в стеке, который расширяется при загрузке процедуры и сокращается при возврате из нее. В Ассемблере имеется регистр стека и соответствующие команды для работы с ним.

Стеки могут представляться как в статической, так и динамической памяти. В статическом представлении стек задается одномерным массивом, величина которого определяется с запасом. Пусть он описан в виде Var Stack[1..N] of T, где T – тип элементов стека. Вершина стека задается индексом массива Top.

Дополнение в стек производится командами

Top:= Top+1;

Stack[Top]:=NewElement;

Удаление из стека выполняется командой Top:= Top-1.

Для обработки возможных ошибок при дополнении необходимо проверять выход за границы массива, а при удалении проверять непустоту стека.

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

Program StekWork; { процедуры работы со стеком }

Uses Crt;

Type

Ukaz=^Stek;

Stek=record

Name: string;

Next: ukaz

end;

Var

Top, Kon: ukaz;

Rname: string;

C, Pr: char;

B: boolean;

N: integer;

Procedure SozdDob;

{создание стека и добавление элементов}

Var B: boolean;

Begin

B:=True;

While B do

Begin

Write('Введите очередной элемент ');

ReadLn(Rname);

if Rname='конец' then B:=False

else

begin

New(Kon);

{создание элемента, на который указывает Kon}

Kon^.Next:=Top;

Kon^.Name:=Rname;

Top:=Kon

end

end;

End;

Procedure Udal; {удаление из стека}

Begin

if Top=Nil then

WriteLn('Удаление из пустого стека!!!')

else

begin

Kon:=Top;

Top:=Top^.Next;

Dispose(Kon);

{ удаление бывшей вершины стека }

end

End;

Procedure Pech; {выдача содержимого стека на экран}

Begin

if Top=Nil then

WriteLn(' Стек пуст!!!')

else

begin

Kon:=Top;

WriteLn(' Состояние стека: ');

While Kon<>Nil do

begin

WriteLn(Kon^.Name);

Kon:=Kon^.Next

end

end

End;

{ НАЧАЛО ОСНОВНОЙ ПРОГРАММЫ }

Begin

ClrScr;

Top:=Nil;

B:=True;

While B do

begin

WriteLn(' Выберите режим работы:');

WriteLn('1-добавление в стек');

WriteLn('2-удаление из стека');

WriteLn('3-выдача на экран');

WriteLn('4-конец работы');

ReadLn(N);

case N of

1: SozdDob;

2: Udal;

3: Pech;

4: B:=False

end

end

End.

Иногда приходится вставлять элементы в середину списка. При статическом описании в этом случае приходится сдвигать часть массива. Это достаточно трудоемкая операция, особенно если она повторяется в цикле.

Для демонстрации гибкости динамических структур данных рассмотрим следующую простую задачу. Имеется стек, описанный в предыдущем примере. Требуется вставить элемент с именем NewName после элемента KeyName. Пусть переменные P и Q имеют тип Ukaz.

P:=Top; B:=True;

While (P<>Nil) and B do

if P^.Name = KeyName then

Begin

B:=False; {для выхода из цикла}

New(Q);

Q^.Name:= NewName;

Q^.Next:=P^.Next;

P^.Next:=Q

End

else P:= P^.Next;

А теперь видоизменим задачу. Пусть вставка требуется перед элементом KeyName. На первый взгляд кажется, что сейчас придется сохранять указатель на предыдущий элемент либо анализировать вместе с текущим и следующий элемент, но указатели позволяют выбрать более простое и красивое решение. Изменения касаются последних трех операторов, следующих после New(Q).

Q^:= P^;

P^.Name:=NewName;

P^.Next:=Q;

Первый оператор обеспечивает копирование элемента KeyName на место вновь организуемого элемента. При этом автоматически обеспечивается связь с элементом, стоявшим ранее после KeyName, так как поле указателя Next также копируется. Остается откорректировать старый элемент KeyName. В качестве упражнения предлагается проследить, потребуются ли изменения в том случае, когда элемент KeyName находится в вершине стека.

Рассмотрим более содержательную задачу. С клавиатуры вводится строка, представляющая собой математическое выражение с вложенными скобками трех видов: “{}”, “[]” и “()”. Старшинство скобок не задано, то есть любая пара скобок может быть вложена в любую другую. Требуется проверить синтаксическую правильность расстановки скобок, что определяется следующим правилом: каждой закрывающей скобке должна предшествовать открывающая того же вида и того же уровня вложенности.

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

Program Syntax;

{ анализ вложенности скобок, стек на указателях }

Type

Ukaz=^Stek;

Stek=record { элемент стека }

Ch: char; { символ (открывающие скобки) }

Next:ukaz { следующий элемент }

end;

Var

Top, Kon: ukaz;

Vir: string[80]; { исходное выражение }

I, N: integer;

A, B, Pr: char;

Procedure Dob;

{ добавление в стек; A-добавляемый символ }

Begin

New(Kon);

Kon^.Next:=Top;

Kon^.Ch:=A;

Top:=Kon

End;

Procedure Udal(var Pr:char);

{ исключение из стека; Pr='e'-признак ошибки }

Begin

Pr:='o';

if Top=Nil then Pr:='e'

else

case A of

')': if Top^.Ch<>'(' then Pr:='e';

']': if Top^.Ch<>'[' then Pr:='e';

'}': if Top^.Ch<>'{' then Pr:='e';

end;

if Pr<>'e' then

begin { удаление элемента из вершины }

Kon:=Top;

Top:=Top^.Next;

Dispose(Kon);

end

End;

Begin { начало основной программы }

WriteLn('Введите выражение');

ReadLn(Vir);

Top:=Nil;

N:=Length(Vir); { длина выражения }

For I:=1 to N do

begin

A:=Vir[I]; { очередной символ }

case A of

'(','[','{': Dob;

{ добавление в стек открывающей скобки }

')',']','}':

begin

Udal(Pr);

{ проверка вершины стека; удаление, если нет ошибки }

if Pr='e' then

begin

WriteLn('Ошибка в позиции ', I);

ReadLn; { пауза }

Exit { выход из программы }

end

end

end

end;

if Top<>Nil then

{ в конце не пустой стек }

WriteLn('Нет последних закрывающих скобок')

else

WriteLn('Все в порядке!!!');

ReadLn { заключительная пауза }

End.

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

Program Syntax; {анализ вложенности скобок, стек - массивом}

Var

Stek:array [1..80] of char;

Top, Kon: integer;

Vir: string[80]; { исходное выражение }

I, N: integer;

A, B, Pr: char;

Procedure Dob;

{ добавление в стек; A-добавляемый символ }

Begin

Top:=Top+1;

Stek[Top]:=A

End;

Procedure Udal(var Pr:char);

{ исключение из стека; Pr='e'-признак ошибки }

Begin

Pr:='o';

if Top=0 then Pr:='e'

else

case A of

')': if Stek[Top]<>'(' then Pr:='e';

']': if Stek[Top]<>'[' then Pr:='e';

'}': if Stek[Top]<>'{' then Pr:='e';

end;

if Pr<>'e' then Top:=Top-1;

{ удаление элемента из вершины }

End;

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

Вторым распространенным типом линейных списков являются очереди. Это список типа FIFO (первым пришел – первым вышел) с двумя точками входа: начало и конец. Очередь пополняется с конца и продвигается с начала.

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

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

Пусть очередь описана Var Och[1..N] of T, где T – тип элементов очереди. Конец очереди задан индексом Endo.

Постановка в очередь производится командами

Endo:= Endo+1;

Och[Endo]:=NewElement;

Продвижение очереди выполняется команками

For I:=1 to Endo-1 do Och[I]:= Och[I+1];

Endo:= Endo-1;

Как и для стека, необходимо проверять выход за границы массива при постановке и непустоту очереди при удалении элементов.

При организации очереди на основе указателей используется следующее описание

Type

Ukaz=^Och;

Och=record

Info: …;

{ поля информационной части элемента }

Next: ukaz

end;

Var

Bego, Endo: ukaz; { начало и конец очереди }

Выгодно указатели Next ориентировать в направлении от начала очереди к концу, а не наоборот. В этом случае постановка в очередь выполняется командами

New(Kon);

Endo^.Next:=Kon;

Kon^.Next:=Nil;

и далее присвоение значений информационным полям.

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