begin pAux:=pTop; sC:=pTop^.sD;

pTop:=pTop^.pNext

dispose(pAux);

end;

begin Clrscr;

writeln(' ВВЕДИ СТРОКУ '); readln(sC); CreateStack(pTop,sC); repeat

writeln(' ВВЕДИ СТРОКУ '); readln(sC); AddComp(pTop,sC)

until sC='END';

writeln('****** ВЫВОД РЕЗУЛЬТАТОВ

******');

repeat DelComp(pTop,sC); writeln(sC);

until pTop = NIL end.

3.4.1.1.2Очереди

Использование динамических структур по прин-

ципу очереди:

FIFO (First-In, First-Out) -

«поступивший первым, обслуживается первым».

Вэтом случае добавление компонент происходит

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

91

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

Описание компоненты очереди и переменных типа указатель дадим следующим образом:

type Comp=^PComp; PComp=record

D: SomeType;

pNext: Comp end;

var

pTop, pEnd, pAux: PComp;

где pTop - указатель начала очереди, pEnd - указатель конца очереди, pAux - вспомогательный указатель.

Тип SomeТype определяет тип данных компоненты очереди.

Начальное формирование очереди выполняется

следующим образом:

New(pTop);

pTop^

92

Nil

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

конец очереди:

New(pAux); pTop

93

pAux^.pNext:=NIL;

pTop^.pNext:=pAux; pTop

pEnd:=pAux; pTop

pEnd^.D:=D2;

94

В итоге имеем: pTop

Добавление последующих компонент производится аналогично.

Выборка компоненты из очереди осуществляется из начала очереди, одновременно компонента исключается из очереди. Пусть в памяти ЭВМ сформирована очередь, состоящая из двух элементов:

95

Выборка компоненты выполняется таким же образом как и для стека:

Work:=pTop^.D;

pAux:=pTop;

pTop:=pBop^.pNext;

dispose(pAux);

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

Program QUEUE;

uses Crt;

type Alfa=String[10]; PComp=^Comp; Comp=record

sD:Alfa;

pNext:PComp

96

end;

var

pTop, pEnd: PComp; sC: Alfa;

pAux: PComp;

begin New(pAux);

pAux^.pNext:=NIL;

pEnd^.pNext:=pAux;

pEnd:=pAux;

pEnd^.sD:=sC

end;

Procedure DelQueue(var pTop: PComp; var sC: Alfa);

var

pAux: pComp; begin

sC:=pTop^.sD;

pAux:=pTop;

pTop:=pTop^.pNext;

dispose(pAux);

97