и наоборот: для "выталкивания " верхнего элемента из стека и передачи его данных узлу Y следует выполнить такие операции:

Еспи Т = Л, то UNDERFLOW;

в противном случае Р <- Т, Т <- LINK(P), У i- INFO(P), AVAIL <f= P. (9)

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

До изучения очередей найдем наиболее удобное выражение операций со стеками в программах для компьютера MIX. Программа вставки элемента, где Р = гП, может выглядеть так.

INFO LINK

AVAIL.

(10)

Для ее выполнения потребуется 17 тактов, по сравнению с 12 тактами для аналогичной операции в последовательной таблице (хотя для обработки события переполнения (OVERFLOW) при последовательном распределении памяти в большинстве случаев необходимо гораздо больше времени). В этой программе, как и в других программах данной главы, OVERFLOW обозначает либо завершение процедуры, либо подпрограмму поиска свободного пространства и возвращения в позицию rJ - 2. Программа удаления элемента также очень проста.

Интересно, что для выполнения этих операций необходимо осуществить циклическую перестановку трех ссылок. Допустим, что перед выполнением операции вставки элемента указатель Р равен AVAIL. Если Р Л, то после выполнения этой операции

значение AVAIL стало равным предыдущему значению LINK(P), значение LINK(P) стало равным предыдущему значению Т и значение Т стало равным предыдущему значению AVAIL.

Таким образом, процесс вставки (за исключением присвоения INFO(P) Y) является циклической перестановкой

AVAIL

Т LINK(P) --->Г

Аналогично в случае удаления элемента, если до выполнения этой операции Р имеет значение Т и предполагается, что ¥ ф К, получим У <г- INFO(P) и

AVAIL

Т LINK(P)

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

Хотя алгоритмы вставки и удаления (8) и (9) созданы для стеков, их можно применять и в более широком смысле для вставки и удаления в любом линейном списке. Допустим, требуется вставить элемент непосредственно перед узлом, на который указывает переменная связи Т. Тогда вставка элемента 2 в приведенном выше списке (2) может быть выполнена с помощью операции (8), где Т = LINK(LINK(FIRST)).

Связанное распределение памяти особенно удобно применять для очередей. Нетрудно заметить, что связи должны быть направлены от начала очереди к ее концу, а при удалении начального узла должен существовать механизм прямого указания нового начального узла. Здесь указатели начального и конечного узлов очереди будут обозначены символами F и R соответственно:

Rl R-И TjV- (12)

За исключением указателя R, эта схема практически идентична схеме на рис. 5 на с. 298.

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

Проиллюстрируем замечания из предыдущего абзаца, применив их к очередям. Сначала рассмотрим операцию вставки: если диаграмма (12) соответствует состоянию до вставки, то диаграмма состояния после вставки элемента данных с конца

очереди будет выглядетьак:

AVAIL =>

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

Р" AVAIL, INF0(P)4-y, LINK(P)f-A, LINK(If)4-P, R 4-P. (14)

A теперь рассмотрим "граничное" состояние, когда очередь пуста. В этом случае состояние до вставки еще потребуется определить, а состояние "после" выглядит так:

F->Г

AVAIL

<-R

(15)

Было бы желательно снова использовать операции (14), даже если для вставки в пустую очередь придется изменить оба указателя, F и R, а не только R. Нетрудно обнаружить, что операции (14) можно будет использовать для этого, если R = LOC(F), когда очередь пуста, при условии, что F = LINK(LOC(F)). Иначе говоря, для реализации этой идеи значение переменной F должно храниться в поле LINK ее же ячейки. Для максимально эффективной проверки граничных условий при работе с пустой очередью предположим, что F = Л. Следовататьно,

пустая очередь задается указателями F = Л и Д = LOC(F).

Выполнив операции (14) при этих условиях, получим (15).

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

(16)

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

Если F = Л, то UNDERFLOW;

в противном случае Р F, F LINK(P), У INFO(P), AVAIL

а если F = Л, тоК<~ LOC(F).

Р, (17)

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

Изложенный выше метод - вовсе не единственный способ представления очередей в виде линейно связанного списка. Например, в упр. 30 описывается в некоторой