Динамические структуры данных: стеки
    Стек - динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.
    По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е. действует принцип "последний пришёл - первый ушёл".
    Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.
    Стек можно организовать на базе любой структуры данных, где возможно хранение нескольких однотипных элементов и где можно реализовать определение стека: линейный массив, типизированный файл, однонаправленный или двунаправленный список. В нашем случае наиболее подходящим для реализации стека является однонаправленный список, причём в качестве вершины стека выберем начало этого списка.
    Выделим типовые операции над стеком и его элементами:
    добавление элемента в стек;
    удаление элемента из стека;
    проверка, пуст ли стек;
    просмотр элемента в вершине стека без удаления;
    очистка стека.
    Реализуем эти операции, используя разработанный ранее модуль для однонаправленных списков (см. материал "Динамические структуры данных: списки").
    
    { 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;
    } Используя разработанные здесь библиотеки, решим задачу.
    Пример. Написать программу, которая вычисляет как целое число значение выражений (без переменных), записаных (без ошибок) в постфиксной форме в текстовом файле. Каждая строка файла содержит ровно одно выражение.
    Алгоритм решения. Выражение просматривается слева направо. Если встречается число, то его значение (как целое) заносится в стек, а если встечается знак операции, то из стека извлекаются два последних элемента (это операнды данной операции), над ними выполняется операция и ее результат записывается в стек. ............