• Списки



• Стеки



• Очереди



• Деревья

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

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

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

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

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

• добавление элемента в стек;
• удаление элемента из стека;
• проверка, пуст ли стек;
• просмотр элемента в вершине стека без удаления;
• очистка стека.

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

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

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

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

// ST2.CPP

#include "STACK.H"
#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. Используя стек, напечатайте символы данной строки в обратном порядке.