ОЧЕРЕДЬ

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

Каждый элемент очереди характеризуется одним и тем же набором полей.

Логическая структура очереди приведена на рис. 1.5.

Исключение

Включение

Начало

Конец

Рис. 1.5. Логическая структура очереди

Очередь функционирует по принципу FIFO (First In — First Out: «первым пришел — первым исключается»),

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

ОПЕРАЦИИ НАД ОЧЕРЕДЬЮ

Над очередью Q (от англ, queue — очередь) могут быть выполнены следующие операции:

• 1) включение нового элемента со значением v в конец очереди — Insert(Q, v);
• 2) исключение элемента из начала очереди — Remove(Q) и возвращение его значения;
• 3) выработка признака «очередь пуста» — Empty(Q);
• 4) считывание первого элемента без его удаления — HeadValue(Q);
• 5) считывание последнего элемента очереди — RearValue(Q);
• 6) определение числа элементов очереди Size(Q);
• 7) очистка очереди — Clear(Q).

Первые три операции над очередью являются основными. Операции Empty, Size, и Clear для очереди аналогичны соответствующим операциям для стека.

ДЕК

Деком (DEQ — от англ, double ended queue — очередь с двумя концами) называется упорядоченный набор элементов, включение и исключение элементов в котором могут осуществляться с любого из двух его КОНЦОВ.

Логическая структура дека представлена на рис. 1.6.

—» Исключение <— Включение

Начало

Конец

? ?

Рис. 1.6. Логическая структура дека

Частные случаи дека — дек с ограниченным входом и дек с ограниченным выходом (включение или исключение элементов осуществляется только с одного из концов дека).

ОПЕРАЦИИ НАД ДЕКОМ

Над деком О могут быть выполнены все операции, определенные для очереди 0, а также добавляются две основные операции:

• — включение элемента со значением V в начало — РщЬКЭ, V);
• — исключение элемента из конца дека — 0е1е1е(0) и возвращение его значения в качестве значения функции.

РЕАЛИЗАЦИЯ ОЧЕРЕДИ И ДЕКА

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

Head Value Next Value Next Value Next

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

Вводятся две переменные типа указателя на элемент очереди или дека: Head — на начало, Rear — на конец очереди или дека. В поле ссылки последнего элемента записывается значение nil.

Описание классов tQueue и tDEQ — наследников класса tStack — может быть следующим:

type

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

tQueue = class(tStack) //класс - очередь

protected

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

public

procedure lnsert(v: tValue);//включение элемента со знач. vв конец function Remove: tValue; //исключение элемента из начала function HeadValue:tValue;//возвращение значения 1-го элемента function RearValue: tValue;//возвращение знач. послед, элемента procedure Clear; override; //очистка очереди constructor Create; // создание пустой очереди

end; // tQueue

// Описание класса tDEQ tDEQ= class(tQueue) // класс - дек

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

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

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

РЕАЛИЗАЦИЯ ОСНОВНЫХ ОПЕРАЦИИ НАД ОЧЕРЕДЬЮ И ДЕКОМ

Включение элемента со значением V в конец очереди выполняется по схеме, приведенной на рис. 1.8. В схеме не отражена ситуация, когда новый элемент включается в пустую очередь. В этом случае после включения указатели Шеай и Яіеаг должны ссылаться на один и тот же вновь созданный элемент, т.е. очередь будет состоять из одного элемента.

fHead

Рис. 1.8. Включение элемента со значением v в конец очереди

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

procedure tQueue.Insert(v: tValue);

// Включение элемента со значением v в конец очереди

var

Newltem: pltem; //указатель на новый элемент

begin

Newltem:= New(pltem); //выделение памяти под новый элемент Newltem^A.Value:= v; //запись v в поле значения нового элемента Newltem^A.Next:=nil; //включенный элемент будет последним if fRear <> nil // если очередь была не пуста

then fRear^A.Next:=Newltem//новый элемент становится последним else fHead:= Newltem; // иначе включенный элемент - первый fRear:= Newltem; //перемещение указателя на конец очереди

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);

// Включение элемента со значением v в начало дека

begin

inherited Push(v); //включение элемента методом Push стека. if fRear = nil // если дек был пуст then fRear:= fHead;

end; //procedure tDEQ.Push

Исключение элемента из конца дека выполняется по схеме, приве денной на рис. 1.9.

Рге<Шет Б^Иет

i

fHead

fRear

Т

I

8

T

nil

nil

Рис. 1.9. Исключение элемента из конца дека

Читается значение последнего элемента дека и в переменную Disltem типа pltem из указателя fRear переписывается адрес этого элемента. Затем с помощью передвигаемого по элементам дека указателя Item типа pltem отыскивается предпоследний элемент дека, адрес которого записывается в переменную fRear, а в поле ссылки этого элемента — значение nil (элемент становится последним в деке). Элемент с указателем Disltem исключается из памяти.

Если исключаемый элемент является единственным в деке (признак этого — равенство значений fHead и fRear), то после чтения значения исключаемого элемента необходимо присвоить переменным fHead и fRear значение nil.

function tDEQ.Delete: tValue;

// Исключение элемента из конца дека и возвращение его значения

var

Disltem, Predltem: pltem; // исключаемый и предпоследний элементы

begin

Delete:= fRear^A.Value; //возвращение последнего элемента дека Disltem:= fRear; // исключаемый элемент - последний

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

then begin // то выполняется поиск предпоследнего элемента, Predltem:= fHead; while Predltem^A.Next<>fRear do Predltem:= Predltem^A.Next; fRear:= Predltem;

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

end

else begin //в деке один элемент - после исключения дек пуст fHead:= nil; fRear:= nil; end;

Dispose(Disltem);

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

end; //function tDEQ.Delete

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

ИТЕРАТОР

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

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

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

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

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

var

sum: tValue; //значение суммы

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

begin

sum:=0;

q1 :=q.Copy; //копирование основной очереди q в очередь q1

while not q1.Empty do sum:=sum+q1 .Remove;

q1. Destroy;

end.

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

Итератор включает в себя три операции:

• 1) инициализация итератора;
• 2) выдача очередного элемента;
• 3) проверка, все ли элементы выданы.

Итератор удобно реализовать в виде операций в абстрактном типе данных (например, в очереди).

Для этого в секцию protected описания типа tQueue добавим новое поле

fltem: pltem; //указатель на текущий элемент очереди

и в секцию public методы:

procedure Iterlnit; function IterDone: Boolean; function lterNext:tValue;

Реализация методов итератора: procedure tQueue.Iterlnit;

// Инициализация итератора

begin

fltem:=fHead; end; // tQueue. Iterlnit

function tQueue.IterDone: Boolean;

// Возвращение True, если все элементы очереди выданы

begin

lterDone:= fltem = nil; end; // tQueue. IterDone

function tQueue.IterNext: tValue;

// Выдача итератором значения очередного элемента очереди

begin

if not IterDone then begin

lterNext:=fltem^A.Value;

fltem:=fltem^A.Next;

end;

end; // tQueue.IterNext

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

var

sum: tValue; q : tQueue;

begin

sum:=0; q.Iterlnit;

while not q.IterDone do sum:=sum+q.IterNext;

Контрольные вопросы и задания

• 1. В чем заключаются достоинства и недостатки последовательного и связанного способов реализации динамических структур данных?
• 2. Назовите принципы функционирования стека, очереди и дека.
• 3. Приведите примеры использования стека в программировании.
• 4. Реализуйте класс — стек с базовым набором методов на основе массива нетипированных указателей на размещенные в динамической памяти элементы.
• 5. С использованием основных методов работы со стеком составить программу копирования элементов стека в новый стек в том же порядке.
• 6. Преобразуйте в префиксную форму записи инфиксное выражение (ах² +)/(bx + a)-abx при условии, что все идентификаторы — однобуквенные.
• 7. Преобразуйте в постфиксную форму записи инфиксное выражение (а * (Ь + с) + d) / 2 при условии, что все идентификаторы — однобуквенные.
• 8. Опишите процесс функционирования стека при вычислении значения постфиксного выражения abc + *d -г 2 / при а = 2,Ь = 5,с = 3, d = 4.
• 9. Реализуйте метод копирования элементов очереди в новую очередь.
• 10. С использованием стандартного набора методов составьте программу копирования элементов стека в новый стек в обратном порядке.
• 11. С использованием стандартного набора методов составьте программу записи элементов очереди в новую очередь в обратном порядке.
• 12. С использованием стандартного набора методов составьте программу переноса из очереди строк в новую очередь элементов, начинающихся на буквы «F» или «f».

Лабораторная работа 1. СТЕКИ, ОЧЕРЕДИ, ДЕКИ

Задание

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

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

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

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

Варианты заданий

• 1. Проверить правильность расстановки скобок в арифметическом выражении (допустимы четыре типа скобок: круглые, квадратные, фигурные и угловые). Для слежения за скобками воспользоваться стеком.
• 2. Сформировать две очереди с фамилиями клиентов. Слить обе очереди в третью, расположив клиентов через одного.
• 3. Создать стек, каждый элемент которого является совокупностью двух целых значений. Заменить нулевыми все элементы с заданной суммой значений.
• 4. Сформировать стек с элементами — строками. Прочитать три нижних элемента стека и поменять местами верхний и нижний элементы.
• 5. Вычислить значение выражения, записанного в постфиксной форме. Операнды представляют собой переменные с однобуквенным идентификатором или (и) цифры от 0 до 9, и в выражении используются только операции «+», «—», «*», «/».
• 6. Прочитать из входного файла последовательность слов Pop и Push. Слово Push вталкивается в стек и выводится число элементов стека, при чтении слова Pop выполняется операция исключения элемента из стека. При невозможности выполнения операции Pop вывести нужное сообщение и работу прекратить.
• 7. Ввести программу на языке Бейсик, состоящую из произвольного числа расположенных последовательно или вложенных инструкций:
• 40 NEXT x

и определить правильность вложения циклов. Для каждой строки выводить сообщение вида: «Цикл по х открыт», «Цикл по х закрыт» или сообщение об ошибке.

• 8. Преобразовать бесскобочную инфиксную запись выражения в постфиксную. Операнды представляют собой переменные с однобуквенным идентификатором или цифры от 0 до 9, и в выражении используются только операции «+», «—», «*», «/».
• 9. Сформировать дек целочисленных элементов и преобразовать его таким образом, чтобы первый элемент стал последним, второй — предпоследним и т.д. При преобразовании исключить из дека нулевые элементы.
• 10. Сформировать две очереди с элементами — фамилиями клиентов. Удалить из второй очереди клиентов, стоящих также и в первой.
• 11. Ввести программу на языке Бейсик, состоящую из произвольного числа расположенных последовательно или вложенных инструкций:
• 10 FOR х=а ТО b STEP с
• 40 NEXT х

и перевести ее в следующую форму:

• 10 х=а-с
• 20 х=х+с
• 50 IF x

Номер строки перехода, переменная цикла и ее конечное значение сохраняются в стеке и выталкиваются из него при достижении строки со словом NEXT.

• 12. Создать очередь с элементами — строками. Исключить из очереди элементы, начинающиеся с буквы А. Вывести длину получившейся очереди и значения ее первого и последнего элементов.
• 13. Создать очередь клиентов и распределить клиентов по двум вспомогательным очередям (через одного).
• 14. Сформировать дек, каждым элементом которого являются сведения о студенте (фамилия, номер группы, год рождения). Переписать в очередь студентов заданного года рождения.
• 15. Создать дек, каждый элемент которого представляет собой совокупность трех вещественных значений. Исключить из дека все элементы, у которых каждое из трех значений превышает заданное. Вывести длину получившегося дека и значения его первого и последнего элементов.
• 16. Сформировать очередь для двух стеков вещественных значений таким образом, чтобы вершина первого стека стала началом очереди, а вершина второго — ее концом.
• 17. Вычислить значение выражения, записанного в префиксной форме. Операнды представляют собой переменные с однобуквенным идентификатором или (и) цифры от 0 до 9, и в выражении используются только операции «+», «—», «*», «/».
• 18. Сформировать очередь целых чисел. С использованием дека расположить все элементы очереди в обратном порядке.
• 19. Ввести программу на языке Бейсик, состоящую из произвольного числа расположенных последовательно или вложенных инструкций:
• 10 FOR х=а ТО b STEP с 40 NEXT х

при условии, что один оператор NEXT может завершать одновременно несколько вложенных циклов (например: NEXT z,y,x), и определить правильность вложения циклов. Для каждого цикла выводить сообщение вида: «Цикл по х открыт», «Цикл по х закрыт».

• 20. Преобразовать выражение в инфиксной форме в префиксную. Операнды представляют собой переменные с однобуквенным идентификатором или (и) цифры от 0 до 9, и в выражении используются только операции «+», «-», «*», «/».
• 21. Сформировать две очереди с элементами — фамилиями клиентов. Удалить из первой очереди клиентов, стоящих в двух очередях.
• 22. Исключить из стека строк три нижних элемента, если в вершине содержится текст «Вершина». В противном случае изменить содержимое трех нижних элементов на «Первый», «Второй», «Третий».
• 23. Создать дек с элементами — двумя целочисленными значениями. Подсчитать количество элементов с заданной суммой значений, прочитать пятый и шестой элементы от начала сформированного дека.
• 24. Сформировать два дека с фамилиями клиентов. Слить оба дека в третий, расположив клиентов через одного, начиная с конца.
• 25. Сформировать очередь целых чисел. С использованием стека расположить все элементы исходной очереди в обратном порядке.
• 26. Создать деке элементами — фамилиями студентов. Перенести в очередь элементы с фамилиями, начинающимися с букв «А» — «К».
• 27. Создать дек целочисленных значений и распределить все его элементы по двум стекам через одного, начиная с последнего элемента.
• 28. Сформировать дек, каждым элементом которого являются сведения о студенте (фамилия, номер группы, год рождения). Переписать в очередь студентов заданной группы.
• 29. Определить, имеет ли вводимая строка вид хСу, где х — строка, состоящая из букв А и В, а у — строка, обратная строке х. Если да, то определить, имеет ли вводимая строка форму aDbD...Dz, где а, Ь,

z — строки вида хСу.

• 30. Ввести программу на языке Бейсик, состоящую из произвольного числа расположенных последовательно или вложенных инструкций:
• 10 FOR х=а ТО b STEP с 40 NEXT х

при условии, что один оператор NEXT может завершать одновременно несколько вложенных циклов (например: NEXT z,y,x), и перевести ее в следующую форму:

• 10 х=а-с 20 х=х+с
• 50 IF x