Структуры и алгоритмы обработки данных

       

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


Любой односвязный список может рассматриваться в виде стека. Однако список по сравнению со стеком в виде одномерного массива имеет преимущество, так как заранее не задан его размер.

Стековые операции, применимые к спискам

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;



Содержание раздела