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

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

Реализация стеков с помощью массивов

Каждую реализацию списков можно рассматривать как реализацию стеков, поскольку стеки с их операторами являются частными случаями списков с операторами, выполняемыми над списками. Надо просто представить стек в виде однонаправленного списка, так как в этом случае операторы PURCH и POP будут работать только с ячейкой заголовка и первой ячейкой списка. Фактически заголовок может быть или указателем, или курсором, а не полноценной ячейкой, поскольку стеки не используют такого понятия, как "позиция", и, следовательно, нет необходимости определять позицию 1 таким же образом, как и другие позиции.

Однако реализация списков на основе массивов, описанная в разделе 2.2, не очень подходит для представления стеков, так как каждое выполнение операторов PURCH и POP в этом случае требует перемещения всех элементов стека и поэтому время их выполнения пропорционально числу элементов в стеке. Можно более рационально приспособить массивы для реализации стеков, если принять во внимание тот факт, что вставка и удаление элементов стека происходит только через вершину стека. Можно зафиксировать "дно" стека в самом низу массива (в ячейке с наибольшим индексом) и позволить стеку расти вверх массива (к ячейке с наименьшим индексом). Курсор с именем top (вершина) будет указывать положение текущей позиции первого элемента стека. Схематично такое представление стека показано на рис. 2.9.

maxlenght

-первый элемент -второй элемент

--последний элемент

elements

Рис. 2.9. Реализация стека на основе массива

Для такой реализации стеков можно определить абстрактный тип STACK следующим образом:

type

STACK = record

top: integer;

element: array[ 1. .ma.xlength] of elementtype

end;

В этой реализации стек состоит из последовательности элементов element[top\, element[top+ 1], elementlmaxlength]. Отметим, если top = maxlength + 1, то стек пустой.

Процедуры для реализаций пяти типовых операторов, выполняемых над стеками, представлены в листинге 2.9. Заметим, что значение, возвращаемое функцией ТОР, имеет тип elementtype, который должен быть разрешенным типом результата, воз-



вращаемого функцией. Если это не так, данную функцию нужно преобразовать в процедуру или она должна возвращать указатель на элемент типа elementtype.

Листинг 2.9. Реализация операторов, выполняемых над стеками

procedure MAKENULL { var S: STACK ) ; begin

S. top: = maxlength + 1 end; { MAKENULL }

fimction EMPTY { S: STACK ): boolean; begin

if S. top > maxlength then return(true)

else

return(false)

end; { EMPTY }

function TOP ( var S: STACK ) : elementtype; begin

if EMPTY (S) then

error(Стек пустой)

else

return(S.elementslS. top])

end; { top }

procedure POP ( var S: STACK ) ; begin

if EMPTY (S) then

error{Стек пустой)

else

S.top:= S. top + 1

end; { POP }

procedure PUSH ( x: elementtype; var S: STACK ); begin

if S. top = 1 then

error{Стек полон) else begin

S. top;= S. top - 1

S.eIements[S.top]:= x

end; { PUSH }

2.4. Очереди

Другой специальный тип списка - очередь (queue), где элементы вставляются с одного конца, называемого задним (rear), а удаляются с другого, переднего (front). Очереди также называют "списками типа FIFO" (аббревиатура FIFO расщифровывается как first-in-first-out: первым вощел - первым выщел). Операторы, выполняемые над очередями, аналогичны операторам стеков. Существенное отличие между ними состоит в том, что вставка новых элементов осуществляется в конец списка, а не в начало, как в стеках. Кроме того, различна устоявщаяся терминология для стеков и очередей. Мы будем использовать следующие операторы для работы с очередями.



1. MAKENULL(Q) очищает очередь Q, делая ее пустой.

2. FRONT(Q) - функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как RETRIEVE(FIRST(Q), Q).

3. ENQUEUE(a;, q) вставляет элемент х в конец очереди Q. С помощью операторов списка этот оператор можно выполнить следующим образом: INSERT(a;, END(Q), Q).

4. DEQUEUE(Q) удаляет первый элемент очереди Q. Также реализуем с помощью операторов списка как DELETE(nRST(Q), q).

5. EMPTY(Q) возвращает значение true тогда и только тогда, когда Q является пустой очередью.

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

Как и для стеков, любая реализация списков допустима для представления очередей. Однако учитывая особенность очереди (вставка новых элементов только с одного, заднего, конца), можно реализовать оператор ENQUEUE более эффективно, чем при обычном представлении списков. Вместо перемещения списка от начала к концу каждый раз при пополнении очереди мы можем хранить указатель (или курсор) на последний элемент очереди. Как и в случае со стеками, можно хранить указатель на начало списка - для очередей этот указатель будет полезен при выполнении команд FRONT и DEQUEUE. В языке Pascal в качестве заголовка можно использовать динамическую переменную и поместить в нее указатель на начало очереди. Это позволяет удобно организовать очищение очереди.

Сейчас мы рассмотрим реализацию очередей с использованием указателей языка Pascal. Читатель может разработать аналогичную реализацию с применением курсоров, но в случае очередей мы имеем возможность более эффективного их (очередей) представления, основанного на массивах, и с непосредственным использованием указателей, чем при попытке моделирования указателей с помощью курсоров. В конце этого раздела мы обсудим также реализацию очередей на основе так называемых "циклических массивов". Для начала реализации очередей с помощью массивов необходимо сделать объявление ячеек следующим образом:

type

celltype = record

element: elementtype; next: T celltype

end;

Теперь можно определить список, содержащий указатели на начало и конец очереди. Первой ячейкой очереди является ячейка заголовка, в которой поле element игнорируется. Это позволяет, как указывалось выше, упростить представление для любой очереди. Мы определяем АТД QUEUE (Очередь)

type

QUEUE = record

front, rear: T celltype

end;

В листинге 2.10 представлены программы для пяти операторов, выполняемых над очередями. В процедуре MAKENULL первый оператор геец)(./гол()определяет динамическую переменную (ячейку) типа celltype и назначает ей адрес Q.front. Второй оператор этой процедуры задает значение поля next этой ячейки как nil. Третий оператор делает заголовок для первой и последней ячеек очереди.

Процедура DEQUEUE(Q) удаляет первый элемент из очереди Q, "отсоединяя" старый заголовок от очереди. Первым элементом списка становится новая динамическая переменная ячейки заголовка.





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.002