Реализация стеков с помощью односвязных списков
Любой односвязный список может рассматриваться в виде стека. Однако список по сравнению со стеком в виде одномерного массива имеет преимущество, так как заранее не задан его размер.
Стековые операции, применимые к спискам
1). Чтобы добавить элемент в стек, надо в алгоритме заменить указатель Lst на указатель Stack (операция Push(S, X)).
P = GetNode
Info(P) = X
Ptr(P) = Stack
Stack = P
2) Проверка стека на пустоту (Empty(S))
If Stack = Nil then Print “Стек пуст”
Stop
3) Выборка элемента из стека (POP(S))
P = Stack
X = Info(P)
Stack = Ptr(P)
FreeNode(P)
Реализация на Паскале:
Стек
Вместо указателя Lst используется указатель Stack
Процедура Push (S, X)
procedure Push(var Stack: PNode; X: Integer);
var
P: PNode;
begin
New(P);
P^.Info:=X;
P^.Next:=Stack;
Stack:=P;
end;
Проверка на пустоту (Empty)
function Empty(Stack: PNode): Boolean;
begin
If Stack = nil then Empty:=True Else Empty:=False;
end;
Процедура Pop
procedure Pop(var X: Integer; var Stack: PNode);
var
P: PNode;
begin
P:=Stack;
X:=P^.Info;
Stack:=P^.Next;
Dispose(P);
end;
Операции с очередью, применимые к спискам.
Указатель начала списка принимаем за указатель начала очереди F, а указатель R, указывающий на последний элемент списка - за указатель конца очереди.
1) Операция удаления из очереди (Remove(Q, X)).
Операция удаления из очереди должна проходить из ее начала.
P = F
F = Ptr(P)
X = Info(P)
FreeNode(P)
2) Проверка очереди на пустоту. (Empty(Q))
If F = Nil then Print “Очередь пуста”
Stop
3) Операция вставки в очередь. (Insert(Q, X))
Операция вставки в очередь должна осуществляться к ее концу.
P = GetNode
Info(P) = X
Ptr(P) = Nil
Ptr(R)= P
R = P
Реализация на Паскале:
procedure Remove(var X: Integer; Fr: PNode);
var
P: PNode;
begin
New(P);
P:=Fr;
X:=P^.Info;
Fr:=P^.Next;
Dispose(P);
end;
function Empty(Fr: PNode): Boolean;
begin
If Fr = nil then Empty:=True Else Empty:=False;
end;
procedure Insert(X: Insert; var Re: PNode);
var
P: PNode;
begin
New(P);
P^.Info:=X;
P^.Next:=nil;
Re^.Next:=P;
end;
