yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

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

2.3. Стеки

Стек — это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top). Стеки также иногда называют "магазинами", а в англоязычной литературе для обозначения стеков еще используется аббревиатура' LIFO (last-in-first-out — последний вошел — первый вышел). Интуитивными моделями стека могут служить колода карт на столе при игре в покер, книги, сложенные в стопку, или стопка тарелок на полке буфета; во всех этих моделях взять можно только верхний предмет, а добавить новый объект можно, только положив его на верхний. Абстрактные типы данных семейства STACK (Стек) обычно используют следующие пять операторов.

1.    MAKENULL(S). Делает стек S пустым.

2.    TOP(S). Возвращает элемент из вершины стека S. Обычно вершина стека идентифицируется позицией 1, тогда TOP(S) можно записать в терминах общих операторов списка как RETRIEVE(FIRST(S), S).

3.    POP(S). Удаляет элемент из вершины стека (выталкивает из стека), в терминах операторов списка этот оператор можно записать как DELETE(FIRST(S), S).

4.    PUSH(;c, S). Вставляет элемент ж в вершину стека S (заталкивает элемент в стек). Элемент, ранее находившийся в вершине стека, становится элементом, следующим за вершиной, и т.д. В терминах общих операторов списка данный оператор можно записать как INSERT(.r, FIRST(S), S).

5.    EMPTY(S). Эта функция возвращает значение true (истина), если стек S пустой, и значение false (ложь) в противном случае.

Пример 2.2. Все текстовые редакторы имеют определенные символы, которые служат в качестве стирающих символов (erase character), т.е. таких, которые удаляют (стирают) символы, стоящие перед ними; эти символы "работают" как клавиша <Backspace> на клавиатуре компьютера. Например, если символ # определен стирающим символом, то строка abc#d##e в действительности является строкой ае. Здесь первый символ # удаляет букву с, второй стирающий символ стирает букву d, а третий — букву b.

Текстовые редакторы имеют также символ-убийцу (kill character), который удаляет все символы текущей строки, находящиеся перед ним. В этом примере в качестве символа-убийцы определим символ @.

Операции над текстовыми строками часто выполняются с использованием стеков. Текстовый редактор поочередно считывает символы, если считанный символ не является ни символом-убийцей, ни стирающим символом, то он помещается в стек. Если вновь считанный символ — стирающий символ, то удаляется символ в вершине стека. В случае, когда считанный символ является символом-убийцей, редактор очищает весь стек. В листинге 2.7 представлена программа, выполняющая описанные действия (в этом листинге используется стандартная функция языка Pascal coin, возвращающая значение true, если текущий символ — символ конца строки. )

 

Листинг 2.7. Программа, реализующая действия стирающего символа и символа-убийцы J

procedure EDIT;

var

s:   STACK;

с:   char;

begin

MAKENULL(S);

while not eoln do begin

read(c);

if  с =   '#'   then

POP(S)

else if  с =   '@'   then

MAKENULL(S);

else { с — обычный символ }

PURSH (c, S)

end;

печать  содержимого стека  S в обратном порядке

end;   {  EDIT   }

 

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

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

Каждую реализацию списков можно рассматривать как реализацию стеков, поскольку стеки с их операторами являются частными случаями списков с операторами, выполняемыми над списками. Надо просто представить стек в виде однонаправленного списка, так как в этом случае операторы 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 }

 

13