Мова програмування Pascal

Стеки

Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу

LIFO (Last-In, First-Out) -

поступивший последним, обслуживается первым.

Обычно над стеками выполняется три операции:

1. начальное формирование стека (запись первой компоненты);
2. добавление компоненты в стек;
3. выборка компоненты (удаление).

Для формирования стека и работы с ним необходимо иметь две переменные типа указатель, первая из которых определяет вершину стека, а вторая - вспомогательная. Пусть описание этих переменных имеет вид:

 var pTop, pAux: Pointer;

где pTop - указатель вершины стека;

pAux - вспомогательный указатель.

ачальное формирование стека выполняется следующими операторами:

                    г=====¬        г=====¬
  New(pTop);         ¦  *--¦---¬   ¦     ¦
                     L=====-   ¦   ¦=====¦
                      pTop     L-->¦     ¦
                                   L=====-
                     г=====¬       г=====¬
  pTop^.pNext:=NIL;  ¦  *--¦---¬   ¦     ¦
                     L=====-   ¦   ¦=====¦
                      pTop     L-->¦ NIL ¦
                                   L=====-
                     г=====¬       г=====¬
  pTop^.D:=D1;       ¦  *--¦---¬   ¦ D1  ¦
                     L=====-   ¦   ¦=====¦
                      pTop     L-->¦ NIL ¦
                                   L=====-
   

Последний оператор или группа операторов записывает содержимое поля данных первой компоненты.

Добавление компоненты в стек призводится с использованием вспомогательного указателя:

  
                     г=====¬       г=====¬       г=====¬
  New(pAux);         ¦  *--¦---¬   ¦     ¦   ----¦--*  ¦
                     L=====-   ¦   ¦=====¦   ¦   L=====-
                      pTop     ¦   ¦     ¦<---    pAux
                               ¦   L=====-
                               ¦
                               ¦   г=====¬
                               ¦   ¦ D1  ¦
                               ¦   ¦=====¦
                               L-->¦ NIL ¦
                                   L=====-
                     г=====¬       г=====¬       г=====¬
  pAux^.pNext:=pTop; ¦  *--¦---¬   ¦     ¦   ----¦--*  ¦
                     L=====-   ¦   ¦=====¦<---   L=====-
                      pTop     ¦   ¦  *--¦-¬      pAux
                               ¦   L=====- ¦
                               ¦           ¦
                               ¦   г=====¬ ¦
                               ¦   ¦ D1  ¦ ¦
                               ¦   ¦=====¦ ¦
                               L-->¦ NIL ¦<-
                                   L=====-
                     г=====¬       г=====¬       г=====¬
  pTop:=pAux;        ¦  *--¦---¬   ¦     ¦   ----¦--*  ¦
                     L=====-   ¦   ¦=====¦<---   L=====-
                      pTop     L-->¦  *--¦-¬      pAux
                                   L=====- ¦
                                           ¦
                                   г=====¬ ¦
                                   ¦ D1  ¦ ¦
                                   ¦=====¦ ¦
                                   ¦ NIL ¦<-
                                   L=====-
                     г=====¬       г=====¬
  pTop^.D:=D2;       ¦  *--¦---¬   ¦ D2  ¦
                     L=====-   ¦   ¦=====¦
                      pTop     L-->¦  *--¦-¬
                                   L=====- ¦
                                           ¦
                                   г=====¬ ¦
                                   ¦ D1  ¦ ¦
                                   ¦=====¦ ¦
                                   ¦ NIL ¦<-
                                   L=====-

Добавление последующих компонент производится аналогично.

Рассмотрим процесс выборки компонент из стека. Пусть к моменту начала выборки стек содержит три компоненты:

                     г=====¬       г=====¬
                     ¦  *--¦---¬   ¦ D3  ¦
                     L=====-   ¦   ¦=====¦
                      pTop     L-->¦  *--¦-¬
                                   L=====- ¦
                                           ¦
                                   г=====¬ ¦
                                   ¦ D2  ¦ ¦
                                   ¦=====¦ ¦
                                 --¦--*  ¦<-
                                 ¦ L=====-
                                 ¦
                                 ¦ г=====¬
                                 ¦ ¦ D1  ¦
                                 ¦ ¦=====¦
                                 L>¦ NIL ¦
                                   L=====-

Первый оператор или группа операторов осуществляет чтение данных из компоненты - вершины стека. Второй оператор изменяет значение указателя вершины стека:

                         г=====¬       г=====¬
  D3:=pTop^.D;           ¦  *--¦---¬   ¦ D3  ¦
  pTop:=pTop^.pNext;     L=====-   ¦   ¦=====¦
                          pTop     ¦   ¦     ¦
                                   ¦   L=====-
                                   ¦
                                   ¦   г=====¬
                                   ¦   ¦ D2  ¦
                                   ¦   ¦=====¦
                                   L-->¦  *--¦-¬
                                       L=====- ¦
                                               ¦
                                       г=====¬ ¦
                                       ¦ D1  ¦ ¦
                                       ¦=====¦ ¦
                                       ¦ NIL ¦<-
                                       L=====-

Как видно из рисунка, при чтении компонента удаляется из стека.

Пример. Составить программу, которая формирует стек, добавляет в него произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея, В качестве данных взять строку символов. Ввод данных - с клавиатуры дисплея, признак конца ввода - строка символов END.

Program STACK;
  uses Crt;
  type
   Alfa= String[10];
   PComp= ^Comp;
   Comp= Record
           sD: Alfa;
           pNext: PComp
          end;
  var
   pTop: PComp;
   sC: Alfa;
  Procedure CreateStack(var pTop: PComp; var sC: Alfa);
   begin
    New(pTop);
    pTop^.pNext:=NIL;
    pTop^.sD:=sC
   end;
  Procedure AddComp(var pTop: PComp; var sC: Alfa);
   var pAux: PComp;
   begin
    NEW(pAux);
    pAux^.pNext:=pTop;
    pTop:=pAux;
    pTop^.sD:=sC
   end;
  Procedure DelComp(var pTop: PComp; var sC:ALFA);
   begin
    sC:=pTop^.sD;
    pTop:=pTop^.pNext
   end;
  begin
   Clrscr;
   writeln('  ВВЕДИ СТРОКУ ');
   readln(sC);
   CreateStack(pTop,sC);
   repeat
    writeln('  ВВЕДИ СТРОКУ ');
    readln(sC);
    AddComp(pTop,sC)
   until sC='END';
   writeln('****** ВЫВОД  РЕЗУЛЬТАТОВ ******');
   repeat
    DelComp(pTop,sC);
    writeln(sC);
   until pTop = NIL
  end.

Зверніть увагу на додаткові посилання

Головний розділ

Мова програмування Pascal