С++: Ввод в структуры данных. Стек

 Стек. Операции, выполняемые над стеком

Стек представляет собой динамическую структуру, доступ к элементам которой осуществляется через указатель на вершину. Каждый элемент стека , во-первых, хранит какую-то информацию, во-вторых, указывает на предыдущий элемент. Вершина стека указывает на NULL. Стек работает по принципу: «последний вошел – первый вышел (LIFO: last input – first output)». Элемент стека доступен, только если он находится на вершине стека. Для представления стека с помощью указателей вводится тип:

struct Node

       {

               char inf;      //информационное поле, данные, любой порядковый тип

               Node *prev;         //указатель на предыдущий элемент

       };

typedef Node * PNode;

Рассмотрим работу со стеком на примере. Пусть требуется написать программу, позволяющую добавлять символ в стек, если перед символом стоит знак «+», удалять символ из стека, если перед ним стоит «–», вывести на экран содержимое стека, если перед текущим символом стоит «=». Описать функцию Push (Top, inf) – втолкнуть символ в стек, функции Pop (Top) – вытолкнуть вершину стека, Empty(Top) – проверка на пустоту.

// Example_stack;

struct Node

{

      char inf;      //информационное поле, данные, любой порядковый тип

      Node *prev;         //указатель на предыдущий элемент

};

typedef Node * PNode;

bool Empty (PNode Top)

//проверка на пустоту, Top – вершина стека

{

      return (Top == NULL);

}

void Push (PNode &Top, char k)

//поместить символ в стек; p – новая вершина стека

{

PNode p;

      p = new Node;     //выделение памяти

      p -> inf = k;         //формирование информационного поля

      p -> prev = Top;  //Top теперь – предыдущий элемент

      Top = p;     //новая вершина

}

char Pop (PNode &Top)

{ //удаление символа из стека

      char c;

PNode p;

      c = Top -> inf;     //сохранение информационного поля

p = Top -> prev; //наведение связи: p – ссылка на предыдущий //элемент

delete Top  ;        //освобождение памяти: вершина удаляется

Top = p;              //предыдущий элемент – новая вершина

return c;

}

void main()

{

PNode T;

      char c;

      T = NULL;           //обнуление ссылки

      do

{

      cout<< "Enter symbol (+, –, =)";

cin>>c;

      switch (c)

{

      case '+': { cin>>c;

      Push (T, c); //втолкнуть в стек

                        }

      break;

      case '–': if (Empty (T)) cout<<"стек пуст";

else cout <<Pop (T);

         break;

         case '=': while (! Empty (T))           //пока стек не пуст

cout<<Pop (T)<<"  ";

break;

}        //case

} while (c != '=');

}        // main()

   Еще один вариант функции выталкивания из стека.

char Pop (PNode &Top)

{ //удаление символа из стека

      char c;

PNode p;

      c = Top -> inf;     //сохранение информационного поля

      p=Top;

      Top=p->prev;      //наведение связи: Top – ссылка на предыдущий //элемент

delete p  ;   //освобождение памяти: вершина удаляется

                   //предыдущий элемент – новая вершина

return c;

}