Стеки
Очередь вида LIFO (Last In First Out - Последним пришел, первым ушел ), при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним, называется стеком. Это одна из наиболее употребляемых структур данных, которая оказывается весьма удобной при решении различных задач.
В силу указанной дисциплины обслуживания, в стеке доступна единственая его позиция, которая называется вершиной стека- это позиция, в которой находится последний по времени поступления в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх прежней вершины и теперь уже сам находится в вершине стека. Выбрать элемент можно только из вершины стека; при этом выбранный элемент исключается из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом (структура с ограниченным доступом к данным).
Графически стек можно представить следующим образом:
Первый элемент заносится вниз стека . Выборка из стека осуществляется с вершины, поэтому стек является структурой с ограниченным доступом.
Операции, производимые над стеками:
1. Занесение элемента в стек.
Push(S,I), где S - идентификатор стека, I - заносимый элемент.
2. Выборка элемента из стека.
Pop(S)
3. Определение пустоты стека.
Empty(S)
4. Прочтение элемента без его выборки из стека.
StackTop(S)
Пример реализации стека на Паскале с использованием одномерного массива:
type
Stack = Array[1..10] of Integer; {стек вместимостью 10 элементов типа Integer}
var
StackCount: Integer; {Переменная - указатель на вершину стека, ее начальное значение должно быть равно 0}
S: Stack; {Объявление стека}
Procedure Push(I: Integer; var S: Stack);
begin
Inc(StackCount);
S[StackCount]:=I;
end;
Procedure Pop(var I: Integer; S: Stack);
begin
I:=S[StackCount];
Dec(StackCount);
end;
Function Empty: Boolean;
begin
If I = 0 then Empty:=True Else Empty:=False;
end;
При выполнении операции выборки из стека сначала необходимо осуществить проверку на пустоту стека. Если он пуст, то Empty возвращает значение True. Если Empty возвращает False, то это означает, что стек не пуст и из него еще можно выбирать элементы.
Procedure StackTop(var I: Integer; S: Stack);
begin
I:=S[StackCount];
end;
