Покажем на примере, как стековая память помогает нам легко определить, является ли такая последовательность, как g={[ ] ({[( )й{ })}• правильно построенной. Элементы g будем обозначать

Хи Хг.....Хп, где Xi есть одна из скобок {, ), (, ), [ или ].

Элементы {, ( и [ назовем ЛЕВЫМИ символами; скажем, что Xi - мвый партнер Xj, если Xi=[ и xj=], ила Xi={ и Xj-=), или

Xi={ и Xj=}.

Algorithm WELLFORMED (ПРАВИЛЬНО ПОСТРОЕННАЯ). Определяет, является ли произвольная последовательность символов Х1Х2. . .Xn, где каждый Xi - одна из скобок {, }, (, ), [, или ], правильно построенной.

Шаг 0. [Инициализация] Set ТОРч-0; /1. Шаг 1. [Читается последовательность слева направо] While /<iV do through шаг 3 od. Шаг 2. [Записывается в стек ЛЕВЫЙ символ]

И Xi ЛЕВЫЙ символ then [записывается else [выбирается символ из стека] if ТОР левый партнер Xj

then выбрать элемент ТОР из памяти else НАПЕЧАТАТЬ «НЕПРАВИЛЬНО ПОСТРОЕННАЯ»; and STOP fi fi. Шаг 3. [Прочесть следующий символ] Set / /-f 1. Шаг 4. [Память пуста?] К ТОР=0 then PRINT «ПРАВИЛЬНО ПОСТРОЕННАЯ»;

else PRINT «НЕПРАВИЛЬНО ПОСТРОЕННАЯ» fi; and

STOP.

Применим теперь алгоритм ПРАВИЛЬНО ПОСТРОЕННАЯ к последовательности

g={ [](([()]} { } ) } 1 2 3 4 5 6 7 8 9 10 11 12 13 14

На рис. 2.3.13 приведено содержимое стека, соответствующее операциям чтения элементов изg слева направо. Целое значение над /-й конфигурацией стека указывает на то, что в данный момент читается Xi-й. символ.

Для реализации стека на Фортране мы возьмем одномерный массив STORE [описанный как STORE (М)] и целую переменную с именем ТОР. Всегда, когда нам нужно поместить на вершину стека элемент -(/), мы выполняем следующие простые команды:

ТОР = ТОР+1

IF (ТОР. GT. М) GO ТО 100 STORE (ТОР) =Х(1) GO ТО 200

100 PRINT «ПЕРЕПОЛНЕНИЕ СТЕКА» "

CONTINUE

Рис 2.3.13. Конфигурации стековой памяти при работе алгоритма WELL-FORMED (ПРАВИЛЬНО ПОСТРОЕННАЯ).

Далее для выбора элемента выполняются следующие команды:

IF (ТОР. EQ. 0) GO ТО 300 X(I) = STORE(TOP) ТОР = ТОР -1 GO ТО 400 300 PRINT «СТЕК ПУСТ» 400 CONTINUE

Очереди

В стековой памяти для внесения и удаления элементов можно пользоваться только словом ТОР. В очереди элементы добавляются с одного конца, а выбираются с другого. Эти элементы обычно называются началом (FRONT) и концом (REAR) очереди. Термин «очередь» вы-

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

F=0 В=0

Рис. 2.3.14. Реализация очереди с использованием линейного массива.

Для моделирования очереди, как правило, используют линейный массив [например, QUEUE (500)] и две целые переменные FRONT и REAR, которые указывают на первые и последние элементы очереди соответственно. Вначале REARFRONT, но когда к очереди добавится свыше 500 элементов, то, по-видимому, некоторые записи будут удалены из начала очереди. Если это так, то, чтобы не допустить переполнения массива, мы присваиваем REAR=1 и продолжаем заполнять очередь с начала массива. Впрочем, REAR никогда не должен перегонять FRONT.

На рис. 2.3.14 показано то, что называется ситуацией одна очередь - одно обслуживание. В этом примере емкость очереди 5, конкретные клиенты помечены метками от А до Я, первый ожидающий в очереди клиент обслуживается за три единицы времени, после чего он покидает очередь. В момент Т=0 очередь пуста, и значения FRONT (F) и REAR (F) равны нулю. В момент 7=1 прибывает Л, ждет 3 единицы времени и покидает очередь в момент Т=4. Клиенты В, С, D, Е, G и Н прибывают в моменты времени 2, 3, 4, 7, 8 и 9 соответственно. С ждет 4 единицы, прежде чем продвинуться в начало очереди, и покидает ее в момент Т=10. Когда прибывает G, в момент Т=8, конец очереди находится Б массиве в положении 5. Здесь мы помещаем G в положение 1 очереди и присваиваем R = l. Когда в момент Т=9 прибывает Н,в R засылается 2, в этот момент очередь полностью заполнена. Теперь конец очереди сравнялся с ее началом, и, пока С не покинет очередь, в нее становиться нельзя.

Подпрограмма QADD (рис. 2.3.15) добавляет элемент VALUE к очереди. Предполагается, что, когда очередь пуста, FRONT = REAR= =0. Процесс удаления элемента из очереди аналогичен. Подпрограмма QDELET (рис. 2.3.16) выполняет эту работу; при удалении из оче-