Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 69 стр.

            .        Практикум по курсу «Алгоритмизация и программирование». Часть 2

                                            Раздел 4. Стеки и очереди

     Стек и очередь – это такие динамические структуры данных (подобно
спискам), в которых добавление и извлечения элементов происходит по четко
определенным правилам. Стек работает по правилу LIFO (Last In First Out),
т.е. «последним вошел, первым вышел». Очередь работает по правилу FIFO
(First In First Out), т.е. «первым вошел, первым вышел». Для реализации сте-
ков и очередей можно использовать массивы или динамические списки. До-
бавление нового элемента в стек осуществляется в конец массива или списка,
а извлечение элемента – из конца массива или списка. Добавление элемента в
очередь осуществляется в конец массива или списка, а извлечение элемента –
из начала массива или стека.

    Далее приводится описание процесса решения некоторых задач с при-
менением пользовательских функций.
    Задача 1. Написать функции добавления и извлечения элемента из стека.
Стек реализовать в виде односвязного списка.
    По аналогии с реализацией списка требуется отдельная структура для
хранения одного элемента. Эта структура будет иметь следующий вид:
    struct Node
    {
          int info;        // информационное поле
          Node* next;      // указатель на следующий элемент
    };

    Для хранения стека вводится другая структура, в которой хранится адрес
начала списка.
    // структура стека
    struct Stack
    {
          Node* head; // указатель на вершину стека
                      //(начало списка)
    };

    Указатель на последний элемент, вошедший в стек, называется его вер-
шиной. Заголовок (начало) списка в приведенном примере указывает на вер-
шину стека. Поэтому добавление и извлечение элементов стека будет осуще-
ствляться в вершину стека (в начало списка).

                                       69