. Диаграмма стековой памяти

Покажем на примере ,как стековая память помогает нам легко определить, является ли такая последовательность, как g={[ ]({[( )]}{ })}, правильно построенной. Элементы g будем обозначать х₁,х₂,… ,х_n , где x_i есть одна из скобок {, } , ( , ), [ или ]. Элементы {, ( и [ назовем ЛЕВЫМИ символами ; скажем, что x_i—левый партнер х_j, если x_i=[ и х_j=] , или x_i=( и x_j=), или x_i ={ и x_j =}/

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

Шаг 0. [Инициализация ]Set TOP ←0; I←1.

Шаг 1.[ Читается последовательность слева направо]

While I≤N do through шаг 3 od/

Шаг 2.[Записывается в стек ЛЕВЫЙ символ]

If х_i ЛЕВЫЙ символ then[ записывается x_i]

else [выбирается символ из стека ]

if TOP левый партнер х_i

then выбирать элемент ТОР из памяти

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

Шаг 3.[Прочесть следующий символ ] Set I ←I +1.

Шаг 4 . [Память пуста?] If TOP=0 then PRINT « ПРАВИЛЬНО ПОСТРОЕННАЯ»;

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

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

g={ [ ] ( { [ ( ) ] } { } ) }

1 2 3 4 5 6 7 8 9 10 11 12 13 14

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

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

TOP = TOP +1

IF ( TOP. GT.M) GO TO 100

STORE (TOP)=X(I)

GO TO 200

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

200 CONTINUE

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

IF (TOP. EQ.0) GO TO 300

X (I) =STORE (TOP)

TOP=TOP-1

GO TO 400

300. PRINT «СТЕК ПУСТ»

400. CONTINUE

Очереди

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

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

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

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