Главная Промышленная автоматика.

Листинг 2.10. Реализация операторов очередей

procedure MAKENULL (var Q: QUEUE ) ; begin

new{Q.front); { создание ячейки заголовка } Q. frontt. next-. nil; Q. rear: = Q. front

end; { MAKENULL }

function EMPTY { 0: QUEUE ) : boolean; begin

if Q. front = 0. rear then return(true)

else

return(true) end; { EMPTY }

function ERONT ( 0: QUEUE ) : elementtype; begin

if EMPTY(Q) then

error(Очередь пуста)

else

retum(0. fraTtt.nextt. element)

end; { ERONT }

procedure ENQUEUE ( x: elementtype; var Q: QUEUE ); begin

new(Q,rearT. next) ; 0.rear:= 0. reaz"T. next; O.rearT. element := x; 0.reart.next:= nil end; { ENQUEUE }

procedure DEQUEUE ( var Q: QUEUE ) ; begin

if EMPTY(0) then

&rror{Очередь пуста)

else

Q. front:- Q. frontT.next end; { DEQUEUE }

Ha рис. 2.10 показан результат последовательного применения команд MAKENULL(Q), ENQUEUE(*, Q), ENQUEUE(i/, Q) и DEQUEUE(Q). Отметим, что после исключения из очереди оператором DEQUEUE(Q) элемента х он остается в поле element ячейки заголовка, но перестает быть частью очереди.

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

Реализацию списков посредством массивов, которая рассматривалась в разделе 2.2, можно применить для очередей, но в данном случае это не рационально. Действительно, с помощью указателя на последний элемент очереди можно выполнить оператор DEQUEUE за фиксированное число щагов (независимое от длины очереди), но оператор ENQUEUE, который удаляет первый элемент, требует перемещения всех элементов очереди на одну позицию в массиве. Таким образом, ENQUEUE имеет время выполнения С1(п), где и - длина очереди.



MAKENULL(Q)

Q. front Q.rear

ENQUEUE(x.Q)

Q. front Orear

ENQUEUE(y,Q)

0. front Qrear


-►

DEQUEUE(Q)

Q. front Qrear

Рис. 2.10. Выполнение последовательности операторов

Чтобы избежать этих вычислительных затрат, воспользуемся другим подходом. Представим массив в виде циклической структуры, где первая ячейка массива следует за последней, как показано на рис. 2.П. Элементы очереди располагаются в "круге" ячеек в последовательньгх позициях, конец очереди находится по часовой стрелке на определенном расстоянии от начала. Теперь для вставки нового элемента в очередь достаточно переместить указатель Q.rear (указатель на конец очереди) на одну позицию по часовой стрелке и записать элемент в эту позицию. При удалении элемента из очереди надо просто переместить указатель Q./roяf (указатель на начало очереди) по часовой стрелке на одну позицию. Отметим, что при таком представлении очереди операторы ENQUEUE и DEQUEUE выполняются за фиксированное время, независимое от длины очереди.

Есть одна сложность представления очередей с помощью циклических массивов и в любых вариациях этого представления (например, когда указатель Q.rear указывает по часовой стрелке на позицию, следующую за последним элементом, а не на сам последний элемент). Проблема заключается в том, что только по формальному признаку взаимного расположения указателей Q.rear и Q.front нельзя сказать, когда очередь пуста, а когда заполнила весь массив. (Конечно, можно ввести специальную переменную, которая будет принимать значение true тогда и только тогда, когда очередь пуста, но если мы не собираемся вводить такую переменную, то необходимо предусмотреть иные средства, предотвращающие переполнение массива.)

Отметим, что "последовательность" (непрерывность) позиций здесь понимается как "циклическая непрерывность". Например, очередь из четырех элементов может последовательно занимать две последние и две первые ячейки массива.



maxlength

Q.rear


Q. front

очередь

Рис. 2.11. Реализация очереди посредством циклического массива

Чтобы разобраться в этой проблеме, предположим, что очередь состоит из maxlength элементов (рис. 2.11), т.е. полностью заполнила массив. Тогда указатель (Q.rear указывает на позицию рядом с Q.front,uo находящуюся против часовой стрелки. Что будет, если очередь пуста? Чтобы увидеть представление пустой очереди, сначала положим, что очередь состоит из одного элемента. Тогда указатели Q.rear и Q.front указьшают на одну и ту же позицию. Если мы удалим из очереди этот элемент, то указатель Q.front переместится на одну позицию по часовой стрелке, оформляя пустую очередь. Таким образом, в случае пустой очереди указатель Q.rear указывает на позицию рядом с Q.front, находящуюся против часовой стрелки, т.е. точно так же, как и при полном заполнении массива. Отсюда следует вывод, что без введения каких-либо механизмов определения пустых очередей при максимальной длине массива maxlength мы не можем позволить очереди иметь более maxlength - 1 элементов.

Теперь представим пять команд, выполняемых над очередями, использующими описанную реализацию. Формально очереди здесь определяются следующим образом:

type

queue = record

elements: array[1..maxlength] of elementtype;

front, rear: integer

end;

Соответствующие процедуры показаны в листинге 2.11. Функция <2rfdo/je(i) добавляет единицу к позиции / в "циклическом" смысле.

Листинг 2.11. Реализация очередей с помощью циклических массивов

function addone ( i: integer ) : integer; begin

return!(i mod maxlength) + 1) end; { addone }

procedure makenull ( var Q: queue ) ; begin

Q.front:= 1; Q.rear:= maxlength end; { MAKENULL )

function empty ( var Q: queue ) : boolean; begin

if addone(Q.rear) = Q.front tlien





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 [17] 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0044