Главная Промышленная автоматика. же, позволяют написать простые процедуры для печати содержимого стека, начиная с обратного, конца стека. В общем случае необходимо извлекать элементы стека по одному и вставлять их последовательно в другой стек, затем распечатать элементы из второго стека в прямом порядке. □ Реализация стеков с помощью массивов Каждую реализацию списков можно рассматривать как реализацию стеков, поскольку стеки с их операторами являются частными случаями списков с операторами, выполняемыми над списками. Надо просто представить стек в виде однонаправленного списка, так как в этом случае операторы PURCH и POP будут работать только с ячейкой заголовка и первой ячейкой списка. Фактически заголовок может быть или указателем, или курсором, а не полноценной ячейкой, поскольку стеки не используют такого понятия, как "позиция", и, следовательно, нет необходимости определять позицию 1 таким же образом, как и другие позиции. Однако реализация списков на основе массивов, описанная в разделе 2.2, не очень подходит для представления стеков, так как каждое выполнение операторов PURCH и POP в этом случае требует перемещения всех элементов стека и поэтому время их выполнения пропорционально числу элементов в стеке. Можно более рационально приспособить массивы для реализации стеков, если принять во внимание тот факт, что вставка и удаление элементов стека происходит только через вершину стека. Можно зафиксировать "дно" стека в самом низу массива (в ячейке с наибольшим индексом) и позволить стеку расти вверх массива (к ячейке с наименьшим индексом). Курсор с именем top (вершина) будет указывать положение текущей позиции первого элемента стека. Схематично такое представление стека показано на рис. 2.9.
-первый элемент -второй элемент --последний элемент 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 |