Структуры данных и алгоритмы (1021739), страница 16
Текст из файла (страница 16)
Некоторые реализации стеков, например с помощью массивов, как описано ни1В этом листинге используется стандартная функция языка Pascal eoln, возвращающаязначение true, если текущий символ — символ конца строки. — Прим. ред.2.3. СТЕКИ59же, позволяют написать простые процедуры для печати содержимого стека, начинаяс обратного, конца стека. В общем случае необходимо извлекать элементы стека поодному и вставлять их последовательно в другой стек, затем распечатать элементы извторого стека в прямом порядке. ПРеализация стеков с помощью массивовКаждую реализацию списков можно рассматривать как реализацию стеков, поскольку стеки с их операторами являются частными случаями списков с операторами, выполняемыми над списками.
Надо просто представить стек в виде однонаправленного списка, так как в этом случае операторы PURCH и POP будут работатьтолько с ячейкой заголовка и первой ячейкой списка. Фактически заголовок можетбыть или указателем, или курсором, а не полноценной ячейкой, поскольку стеки неиспользуют такого понятия, как "позиция", и, следовательно, нет необходимости определять позицию 1 таким же образом, как и другие позиции.Однако реализация списков на основе массивов, описанная в разделе 2.2, не оченьподходит для представления стеков, так как каждое выполнение операторов PURCHи POP в этом случае требует перемещения всех элементов стека и поэтому время ихвыполнения пропорционально числу элементов в стеке.
Можно более рациональноприспособить массивы для реализации стеков, если принять во внимание тот факт,что вставка и удаление элементов стека происходит только через вершину стека.Можно зафиксировать "дно" стека в самом низу массива (в ячейке с наибольшим индексом) и позволить стеку расти вверх массива (к ячейке с наименьшим индексом).Курсор с именем top (вершина) будет указывать положение текущей позиции первогоэлемента стека. Схематично такое представление стека показано на рис.
2.9.1fop4—первый элемент-«—второй элемент-последний элементmaxlenghtelementsРис. 2.9. Реализация стека на основе массиваДля такой реализации стеков можно определить абстрактный тип STACK следующим образом:typeSTACK = recordtop: integer;element: array[1..maxlength] of elementtypei .end;-- g ;,:n,.->:,.-. ,',«га ,В этой реализации стек состоит из последовательности элементов element[top],element[top + 1], .'.., element[maXlength]. Отметим, если top = maxlength + 1, то стекпустой.Процедуры для реализаций пяти типовых операторов, выполняемых над стеками,представлены в листинге 2.9.
Заметим, что значение, возвращаемое функцией ТОР,имеет тип elemerittype, который должен быть разрешенным типом результата, воз-60ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХвращаемого функцией. Если это не так, данную функцию нужно преобразовать впроцедуру или она должна возвращать указатель на элемент типа elementtype.Листинг 2.9. Реализация операторов, выполняемых над стекамиprocedure MAKENULL ( var S: STACK );beginS.top:= maxlength + 1end; { MAKENULL }function EMPTY ( S: STACK ): boolean;beginif S.top > maxlength thenreturn(true)elsereturn(false)end; { EMPTY }function TOP ( var S: STACK ): elementtype;beginif EMPTY(S) thenerror('Стек пустой')elsereturn(S.eleraen ts[S.top])end; { TOP }procedure POP ( var S: STACK ) ,beginif EMPTY(S) thenerror('Стек пустой')elseS.tcp:= S.top + 1end; { POP }procedure PUSH ( x: elementtype; var S: STACK );beginif S.top = 1 thenerror('Стек полон')else beginS.top:= S. top - 1S.elements[S.top]:= xendend; { PUSH }2.4.
ОчередиДругой специальный тип списка — очередь (queue), где элементы вставляются с одного конца, называемого задним (rear), а удаляются с другого, переднего (front). Очереди также называют "списками типа FIFO" (аббревиатура FIFO расшифровывается какfirst-in-first-out: первым вошел — первым вышел). Операторы, выполняемые над очередями, аналогичны операторам стеков. Существенное отличие между ними состоит втом, что вставка новых элементов осуществляется в конец списка, а не в начало, как встеках. Кроме того, различна устоявшаяся терминология для стеков и очередей. Мыбудем использовать следующие операторы для работы с очередями.2.4.
ОЧЕРЕДИ611.2.3.4.5.MAKENULL(Q) очищает очередь Q, делая ее пустой.FRONT(Q) — функция, возвращающая первый элемент очереди Q. Можно реализовать эту функцию с помощью операторов списка как RETRIEVE(FIRST(Q), Q).ENQUEUED, Q) вставляет элемент х в конец очереди Q. С помощью операторов списка этот оператор можно выполнить следующим образом: INSERTO*, END(Q), Q).DEQUEUE(Q) удаляет первый элемент очереди Q. Также реализуем с помощьюоператоров списка как DELETE(FIRST(Q), Q).EMPTY(Q) возвращает значение true тогда и только тогда, когда Q является пустой очередью./Реализация очередей с помощью указателейКак и для стеков, любая реализация списков допустима для представления очередей. Однако учитывая особенность очереди (вставка новых элементов только с одного, заднего, конца), можно реализовать оператор ENQUEUE более эффективно, чемпри обычном представлении списков.
Вместо перемещения списка от начала к концукаждый раз при пополнении очереди мы можем хранить указатель (или курсор) напоследний элемент очереди. Как и в случае со стеками, можно хранить указатель наначало списка — для очередей этот указатель будет полезен при выполнении командFRONT и DEQUEUE. В языке Pascal в качестве заголовка можно использовать динамическую переменную и поместить в нее указатель на начало очереди. Это позволяетудобно организовать очищение очереди.Сейчас мы рассмотрим реализацию очередей с использованием указателей языкаPascal.
Читатель может разработать аналогичную реализацию с применением курсоров, но в случае очередей мы имеем возможность более эффективного их (очередей)представления, основанного на массивах, и с непосредственным использованием указателей, чем при попытке моделирования указателей с помощью курсоров. В концеэтого раздела мы обсудим также реализацию очередей на основе так называемых"циклических массивов". Для начала реализации очередей с помощью массивов необходимо сделать объявление ячеек следующим образом:typecelltype = recordelement: elementtype;next: Т celltypeend;Теперь можно определить список, содержащий указатели на начало и конец очереди.
Первой ячейкой очереди является ячейка заголовка, в которой поле elementигнорируется. Это позволяет, как указывалось выше, упростить представление длялюбой очереди. Мы определяем АТД QUEUE (Очередь)type:QUEUE = recordfront, rear: Т celltypeend;В листинге 2.10 представлены программы для пяти операторов, выполняемых надочередями. В процедуре MAKENULL первый оператор new(Q.front) определяет динамическую переменную (ячейку) типа celltype и назначает ей адрес Q.front.
Второйоператор этой процедуры задает значение поля next этой ячейки как nil. Третий оператор делает заголовок для первой и последней ячеек очереди.Процедура DEQUEUE(Q) удаляет первый элемент из очереди Q, "отсоединяя" старый заголовок от очереди. Первым элементом списка становится новая динамическаяпеременная ячейки заголовка.62ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХ... ,.ч... „Листинг 2.10. Реализация операторов очередейprocedure MAKENULL (var Q: QUEUE );beginnew(Q.front); { создание ячейки заголовка }Q.frontT.next:= nil;Q.rear:= Q.frontend; { MAKENULL }function EMPTY ( Q: QUEUE ): boolean;beginif Q.front = Q.rear thenreturn(true)elsereturn(true)end; { EMPTY }function FRONT ( Q: QUEUE ): elementtype;beginif EMPTY(Q) thenerror('Очередь пуста')elsereturn(Q.
frontt. л ex tT. element)end; { FRONT }procedure ENQUEUE ( x: elementtype; var Q: QUEUE );beginnew(Q.reart.next);Q.rear:= Q.reart.next;Q.reart.element:- x;Q.reart.next:= nilend; { ENQUEUE }procedure DEQUEUE ( var Q: QUEUE );beginif EMPTY(Q) thenerror('Очередь пуста')elseQ.front-.= Q. frontT.nextend; { DEQUEUE }На рис. 2.10 показан результат последовательного применения командMAKENULL(Q), ENQUEUED, Q), ENQUEUED, Q) и DEQUEUE(Q). Отметим, что после исключения из очереди оператором DEQUEUE(Q) элемента ж он остается в полеelement ячейки заголовка, но перестает быть частью очереди.Реализация очередей с помощью циклических массивовРеализацию списков посредством массивов, которая рассматривалась в разделе2.2, можно применить для очередей, но в данном случае это не рационально.
Действительно, с помощью указателя на последний элемент очереди можно выполнитьоператор DEQUEUE за фиксированное число шагов (независимое от длины очереди),но оператор ENQUEUE, который удаляет первый элемент, требует перемещения всехэлементов очереди на одну позицию в массиве. Таким образом, ENQUEUE имеетвремя выполнения П(п), где п — длина очереди.2.4. ОЧЕРЕДИ63MAKENULL(Q)Q. frontQ.rearENQUEUED,->с^л, w;Q. frontО тягUl-\y,4/Q. frontО тягQ. frontО тагг—*г»X—*XX•JУ•— »• У•¥>JrРис. 2.10. Выполнение последовательности операторовЧтобы избежать этих вычислительных затрат, воспользуемся другим подходом.
Представим массив в виде циклической структуры, где первая ячейка массива следует за последней, как показано на рис. 2.11. Элементы очереди располагаются в "круге" ячеек впоследовательных позициях1, конец очереди находится по часовой стрелке на определенном расстоянии от начала.
Теперь для вставки нового элемента в очередь достаточно переместить указатель Q.rear (указатель на конец очереди) на одну позицию по часовойстрелке и записать элемент в эту позицию. При удалении элемента из очереди надо просто переместить указатель Q.front (указатель на начало очереди) по часовой стрелке наодну позицию. Отметим, что при таком представлении очереди операторы ENQUEUE иDEQUEUE выполняются за фиксированное время, независимое от длины очереди.Есть одна сложность представления очередей с помощью циклических массивов ив любых вариациях этого представления (например, когда указатель Q.rear указывает по часовой стрелке на позицию, следующую за последним элементом, а не на сампоследний элемент).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
