comp-science.narod.ru ==> Дидактические материалы по информатике ==> Стеки


 

Динамические структуры данных: стеки

 

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

По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е. действует принцип "последний пришёл — первый ушёл".

Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.

Стек можно организовать на базе любой структуры данных, где возможно хранение нескольких однотипных элементов и где можно реализовать определение стека: линейный массив, типизированный файл, однонаправленный или двунаправленный список. В нашем случае наиболее подходящим для реализации стека является однонаправленный список, причём в качестве вершины стека выберем начало этого списка.

Выделим типовые операции над стеком и его элементами:

Реализуем эти операции, используя разработанный ранее модуль для однонаправленных списков (см. материал "Динамические структуры данных: списки").

 

{ Turbo Pascal, файл STACK.PAS }
Unit Stack;
Interface
 Uses Spisok;
 Procedure V_Stack(Var Versh : U; X : BT);
 Procedure Iz_Stack(Var Versh : U; Var X : BT);
 Function Pust(Versh : U) : Boolean;
 Function V_Vershine(Versh : U) : BT;
 Procedure Ochistka(Var Versh : U);
Implementation
 Procedure V_Stack;
 Begin
     V_Nachalo(Versh, X)
 End;
 Procedure Iz_Stack;
 Begin
     Iz_Nachala(Versh, X)
 End;
 Function Pust;
 Begin
     Pust := Versh = Nil
 End;
 Function V_Vershine;
 Begin
      V_Vershine := Versh^.Inf
 End;
 Procedure Ochistka;
 Begin
      Spisok.Ochistka(Versh)
 End;
Begin
End.
             
/* C++, файл STACK.CPP */
#include "SPIS.CPP"
Zveno *V_Stack(Zveno *Versh, BT X)
{
 return V_Nachalo(Versh, X);
}
Zveno *Iz_Stack(Zveno *Versh)
{
 return Iz_Nachala(Versh);
}
int SPust(Zveno *Versh)
{
	return !Versh;
}
BT V_Vershine(Zveno *Versh)
{
	return Versh->Inf;
}
Zveno *Chistka(Zveno *Versh)
{
while (!Pust(Versh)) Versh=Iz_Stack(Versh);
		return Versh;
}

 

Используя разработанные здесь библиотеки, решим задачу.

Пример. Написать программу, которая вычисляет как целое число значение выражений (без переменных), записаных (без ошибок) в постфиксной форме в текстовом файле. Каждая строка файла содержит ровно одно выражение.

Алгоритм решения. Выражение просматривается слева направо. Если встречается число, то его значение (как целое) заносится в стек, а если встечается знак операции, то из стека извлекаются два последних элемента (это операнды данной операции), над ними выполняется операция и ее результат записывается в стек. В конце в стеке остается только одно число — значение всего выражения.

 

{ Turbo Pascal, файл ST2.PAS }
 Program St2;
 Uses Spisok, Stack;
 Const Znak = ['+', '-', '*', '/'];
 Var S, S1 : String;
     T : Text;
     I, N : Byte;
     X, Y : BT; Code : Integer;
     NS : U;
 Begin
   Write('Введите имя файла: ');   ReadLn(S1);
   Assign(T, S1);   ReSet(T);
   NS := Nil;
   While Not Eof(T) Do
    Begin
      ReadLn(T, S);  I := 1;
      While I <= Length(S) Do
        Begin
          If S[I] In ['0'..'9']
          Then
          Begin
           N := I;
           While S[I] In ['0'..'9'] Do
            I := I + 1;
           Val(Copy(S, N, I - N), X, Code);
          V_Stack(NS, X);
          End
          Else
          If S[I] In Znak
          Then
           Begin
             Iz_Stack(NS, X);
             Iz_Stack(NS, Y);
             Case S[I] Of
             '+' : X := X + Y;
             '-' : X := Y - X;
             '*' : X := X * Y;
             '/' : X := Y Div X
             End;
             V_Stack(NS, X)
           End;
          I := I + 1
         End;
         Iz_Stack(NS, X);
         WriteLn(S, ' = ', X);
       End
   End.
             
/* C++, файл ST2.CPP */
#include "STACK.CPP"
#include < string.h >
#include < stdio.h >
void main(void)
{
char S[255];
FILE *T;
int I; BT X, Y;
Zveno *NS;
   clrscr();
   cout << "Введите имя файла: "; cin >> S;
   T=fopen(S, "r");
   NS = NULL;
   while (!feof(T))
   {
      fgets(S, 255, T);
      I = 0;
      while (I <= strlen(S)-1)
	{
	  if (S[I]>='0'&&S[I]<='9')
	  {
	   X=0;
	   while(S[I]>='0'&&S[I]<='9') {X=X*10+(S[I]-'0'); I++;}
	   NS=V_Stack(NS, X);
	  }
	  else
	  if (S[I]=='+'||S[I]=='-'||S[I]=='/'||S[I]=='*')
	  {
	     X=V_Vershine(NS);
	     NS=Iz_Stack(NS);
	     Y=V_Vershine(NS);
	     NS=Iz_Stack(NS);
	     switch (S[I]) {
	     case '+' : X += Y; break;
	     case '-' : X = Y - X; break;
	     case '*' : X *= Y; break;
	     case '/' : X = Y / X; break;}
	     NS=V_Stack(NS, X);
	  }
	  I++;
	 }
	 X=V_Vershine(NS);
	 NS=Iz_Stack(NS);
	 cout << S << " => " << X << "\n";}
}

 

Контрольные вопросы и задания
  1. Какую структуру данных называют стеком?
  2. На базе каких структур может быть организован стек?
  3. Приведите из жизни примеры организации чего-либо по принципу стека.
  4. Используя стек, напечатайте символы данной строки в обратном порядке.

Рейтинг ресурсов УралWeb

 

© А.П. Шестаков, 2002
X