yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Реализация стеков с помощью массивов

Алгоритмы структуры данных

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

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

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

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

type

STACK = record

top: integer;

element: array[1..maxlength] of elementtype

end;

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

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

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

procedure MAKENULL ( var S: STACK );

begin

S.top:= maxlength + 1

end; { MAKENULL }

 

function 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. еіеліел ts [ S. 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. elements[S. top] := x

end

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(x, Q) вставляет элемент х в конец очереди Q. С помощью операторов списка этот оператор можно выполнить следующим образом: INSERT(x, END(Q), Q)

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

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

 

23