Protected. fRear: pItem; // поле - указатель на конец очереди

fRear: pItem; // поле - указатель на конец очереди

Public

procedure Insert(v: tValue); // включение элемента со значением v

function Remove: tValue; // исключение элемента из очереди

function HeadValue: tValue; // возвращение значения первого элемента

function RearValue: tValue; // возвращение значения последнего элемента

constructor Create; // создание пустой очереди

end; // tQueue

// Описание класса tDEQ

tDEQ= class (tQueue) // класс - дек

procedure Push(v: tValue); // включение элемента со знач. v в начало дека

function Delete: tValue; // исключение элемента из конца дека

end; // tDEQ

Класс tQueue наследует у класса tStack поля fHead и fSize, свойство Size, методы Empty, Clear, Destroy и перекрывает метод Create.

Класс tDEQ наследует у класса tQueue поля fHead, fSize, fRear, свойство Size, методы Empty, Clear, Destroy, Insert, Remove, HeadValue, RearValue, Create и перекрывает метод Push класса tStack.

11. Реализация основных операций над очередью и деком

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

Реализация метода включения элемента в очередь:

procedure tQueue.Insert(v: tValue);

Var

NewItem: pItem; // вспомогательный указатель на новый элемент

Begin

NewItem: = New(pItem); // выделение памяти под новый элемент очереди

NewItem^.Value: = v; // запись v в поле значения нового элемента

NewItem^.Next: = nil; // включенный элемент будет последним

if fRear < > nil // если очередь была не пуста

then fRear^.Next: =NewItem // то новый элемент становится последним

else fHead: = NewItem; // иначе включенный элемент - первый

fRear: = NewItem; // перемещение указателя на конец очереди

Inc(fSize); // увеличение числа элементов очереди на 1

end; // procedure tQueue.Insert

Исключение элемента из начала очереди выполняется по той же схеме, что и исключение элемента из вершины стека. В связи с этим при реализации операции вместо написания последовательности операторов, выполняющих нужные действия, целесообразно использовать наследуемый от типа tStack метод Pop, исключающий элемент из вершины стека. Если элемент исключается из очереди, состоящей из единственного элемента, то после исключения указатель fRear, как и fHead, должен получить значение nil (очередь пуста).

Реализация метода исключения элемента из очереди:

function tQueue.Remove: tValue;

Begin

Remove: = Pop; // исключение элемента из начала методом Pop стека

// Если в очереди был один элемент, то очередь становится пустой:

if fHead = nil then fRear: = nil;

end; // function tQueue.Remove

Включение элемента со значением v в начало дека выполняется так же, как и включение элемента в стек. В связи с этим при реализации операции целесообразно использовать наследуемый от типа tStack метод Push, включающий элемент в вершину стека. Если элемент включается в пустой дек, то после включения указатели fHead и fRear будут ссылаться на один и тот же элемент.

procedure tDEQ.Push(v: tValue);

Begin

inherited Push(v); // включение элемента в начало методом Push стека.

// Если дек был пуст, то элемент становится также и последним:

if fRear = nil then fRear: = fHead;

end; // procedure tDEQ.DPush

Исключение элемента из конца дека выполняется по следующей схеме. Читается значение последнего элемента дека, и в переменную DisItem типа pItem из указателя fRear переписывается адрес этого элемента. Затем с помощью передвигаемого по элементам дека указателя Item типа pItem отыскивается предпоследний элемент дека, адрес которого записывается в переменную fRear, а в поле ссылки этого элемента – значение nil (элемент становится последним в деке). Элемент с указателем DisItem исключается из памяти. Если исключаемый элемент является единственным в деке (признак этого – равенство значений fHead и fRear), то после чтения значения исключаемого элемента необходимо присвоить переменным fHead и fRear значение nil.

function tDEQ.Delete: tValue;

Var

DisItem, PredItem: pItem; // исключаемый и предпоследний элементы

Begin

Delete: = fRear^.Value; // возвращение последнего элемента дека

DisItem: = fRear; // исключаемый элемент - последний

if fHead < > fRear // если в деке более одного элемента

then begin // то выполняется поиск предпоследнего элемента,

PredItem: = fHead;

while PredItem ^.Next< > fRear do PredItem: = PredItem ^.Next;

fRear: = PredItem; fRear^.Next: = nil; // который становится последним.

End

else begin // если в деке один элемент,

fHead: = nil; fRear: = nil; // то после исключения дек становится пустым

end;

Dispose(DisItem);

Dec(fSize); // уменьшение числа элементов дека на 1

end; // function tDEQ.Delete

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

12. Итератор

Итератор – обобщение итерационных методов, имеющихся в большинстве языков программирования. Итераторы позволяют выполнить итерации для произвольных типов данных. Примеры функций итераторов: выдача элементов некоторого множества в произвольном порядке; выдача элементов набора в заданном порядке, например, от меньшего к большему; выдача элементов очереди от начала к концу и т.д.

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

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

Пример. Суммирование элементов очереди без итератора.

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

Var

sum: tValue;

q, q1: pQueue; // основная и вспомогательная очереди

Begin

...

sum: =0;

q1: =q^.Copy; // копирование основной очереди во вспомогательную