25. Реализация атд стек.
Определенный набор операций с АТД позволяет выделять различные абстрактные типы данных. Линейные списки, у которых операции вставки, удаления и доступа выполняются только для первой или последней позиции, получили специальные названия. Одним из них является стек, наиболее распространенный АТД в программировании. Стек (stack) - это линейный список, у которого операции вставки и удаления выполняются только на одном конце, называемом вершиной. Доступ к элементам стека осуществляется через вершину по принципу LIFO (Last-In - First-Out - первый пришел - первый ушел). Таким образом, АТД стек характеризуется следующими основными операциями:
1. Вставка элемента на вершину стека (устоявшийся термин англ. push - заталкивать).
2. Удаление элемента из вершины стека (уст. термин pop - выскакивать).
Реализация стека может быть основана как на связном списке, так и на массиве, причем в обоих случаях основные операции выполняются за время О(1).
В случае использования связного списка вершиной стека считается указатель на начало списка, а операции push и pop соответствуют вставке и удалению первого элемента списка.
Опишем стек как указатель на узел, содержащий элемент стека elem и указатель на следующий элемент next:
Type Stack=^node;
Node=record
Elem: integer;
Next: stack;
End;
Будем считать, что стек является пустым, если вершина стека нулевой указатель. Тогда операции создания списка StackInit, проверка, является ли стек пустым – StackEmpty, и основные операции push и pop могут быть следующими:
Procedure stackinit (var S: stack);
Begin
S:=nil;
End;
Function stackempty (s: stack): Boolean;
Begin
Stackempty:=S=nil;
End;
Procedure push (x: integer; var S: stack);
Var P: stack;
Begin
New(p);
P^.elem:=x;
P^.next:=S;
S:=P;
End;
Function pop (var S: stack): integer;
Var p: stack;
Begin
P:=S;
Pop:=p^.elem;
S:=p^.next;
Dispose(P);
End;
Если максимальный размер стека известен заранее, то можно организовать стек посредством массива. В такой реализации стек состоит из массива элементов elem и указателя вершины Top:
Const maxStackSize= ; (макс размер стека)
Type
Stack=record
Elem: array[1..maxstacksize] of integer;
Top: 0..maxsize;
End;
Будем считать, что указатель вершины Тор адресует последний записанный в стек элемент и растет в сторону увеличения адресов. В случае, если Тор=0, то стек считается пустым.
Операции вставки и удаления здесь могут быть реализованы более эффективно, чем у линейных, если принять во внимание, что обе операции выполняются на вершине стека и не требуют сдвига элементов. При вставке элемента в стек сначала указатель вершины увеличивается на единицу, а затем производится запись элемента на место, определяемое указателем стека. Операция удаления элемента состоит в уменьшении указателя вершины на единицу.
Procedure StackInit (var S: stack);
Begin
S.top:=0;
End;
Function StackEmpty (S: stack): Boolean;
Begin
Stackempty:=S.top=0;
End;
Procedure push (x: integer; var S: stack);
Begin
S.top:=S.top+1;
S.elem[S.top]:=x;
End;
Function pop (var S: stack): integer;
Begin
Pop:=s.elem[s.top];
s.top:=s.top-1;
end;
Реализация стека на массивах является достаточно рациональной (экономит память, используемую в списке под указатели) и эффективной. Недостатком по-прежнему является резервирование максимально возможного размера стека на стадии компиляции программы, при этом не исключается возможность переполнения стека; кроме того, память расходуется неэкономно, так как в процессе решения задачи стек может заполняться лишь частично. Стек является чрезвычайно удобной структурой данных для многих задач программирования: с их помощью организовано выполнение процедур, исключение рекурсии, управление динамической памятью, трансляторы арифметических выражений, семантический и синтаксический анализ, и т.д.