32. Моделирование массивом последовательностей: очереди

FIFO – “First In First Out” – «Первый пришел – первый ушел»

Очередь – структура данных, как и стек представляющая собой последовательность элементов. Добавление элементов происходит с одной стороны последовательности, удаление – с другой.

Значениями типа "очередь элементов типа T", как и для стеков, являются последовательности значений типа T. Разница состоит в том, что берутся элементы не с конца, а с начала (а добавляются по-прежнему в конец).

Операции с очередями:

Добавить (t: T, var x: очередь элементов типа T);

Полна(s: стек элементов типа Т): boolean

Взять (var t: T, var x: очередь элементов типа T);

Пуста (x: очередь элементов типа T): boolean;

Очередной (x: очередь элементов типа T): T.

При выполнении команды "Добавить" указанный элемент добавляется в конец очереди.

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

Значением функции "Очередной" (определенной для непустой очереди) является первый элемент очереди.

Будем хранить элементы очереди в соседних элементах массива. Тогда очередь будет прирастать справа и убывать слева. Поскольку при этом она может дойти до края, свернём массив в окружность.

Введем массив

Содержание: array [0..n-1] of T

и переменные

Первый: 0..n-1,

Длина : 0..n.

При этом элементами очереди будут

Содержание [Первый], Содержание [Первый + 1],...,Содержание [Первый + Длина - 1],

где сложение выполняется по модулю n.

Операции выполняются так:

Добавить элемент:

Если не полна

Содержание [(Первый + Длина) mod n] := t;

Длина := Длина + 1;

Взять элемент;

Если не пуста

t := Содержание [Первый];

Первый := (Первый + 1) mod n;

Длина := Длина - 1;

Пуста := (Длина = 0);

Полна := (Длина = n);

Очередной := Содержание [Первый];

33. Моделирование массивом последовательностей: деки

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

“Double Ended Queue”

34. Записи. Присоединяющий оператор.

Оператор with (позволяет сократить обращение к полям записи, а также к полям, методам и свойствам объекта):

with имя записи или объекта do оператор

или

with список имен do оператор

Всюду внутри оператора можно опускать имя записи при обращении к полю указанной записи или имя объекта при обращении к полю, методу или свойству указанного объекта.

Если внешняя переменная имеет то же имя, что и поле (метод, свойство), то предпочтение отдается полю (методу, свойству). При наличии вложенных операторов with вначале предпринимается попытка рассматривать переменную как поле записи или объекта самого внутреннего оператора with, затем непосредственно объемлющего его оператора with и т.д. Если оператор with  содержит список объектов, то они рассматривается справа налево.

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

record Date

список полей1: тип1;

...

список полейN: типN;

end

var d1,d2: Date;

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

Как и для массивов, можно скопировать содержимое полей одной переменной-записи в другую:

d2:=d1;