Введение

Стек представляет собой динамическую структуру (то-есть структуру, размер которой может изменяться в процессе выполнения программы), предназначенную для временного хранения данных некоторого типа INF, который может быть как базовым, так и определяемым пользователем. Запись данных в стек и выборка данных из стека производятся путем обращения к его вершине.

В данной работе стек реализуется на базе односвязного списка. При записи в стек (операция PUSH) в начало списка добавляется узел, а при выборке из стека (операция POP) узел удаляется из начала списка. Чтобы получить доступ к следующей ячейке стека нужно удалить предыдущую. При выполнении операции POP данные из стека не считываются. Данные могут считываться только из вершины стека. Для чтения данных используется специальная функция, которая читает данные без удаления узла из вершины стека.

Для обеспечения доступа к данным, хранящимся в узлах типа ListNode, класс MyStack сделан дружественным по отношению к классу ListNode. В этом случае все методы класса MyStack получают доступ к скрытым данным класса ListNode.

Чтобы в узлах можно было бы хранить данные различных типов и чтобы узлы класса ListNode можно было бы использовать в различных структурах (например, для реализации списка или очереди), класс ListNode реализован в виде шаблона семейства классов с двумя формальными параметрами: типом хранимых данных (class INF) и дружественным классом, реализующим некоторую структуру данных, например стек (class FRIEND).

Методы шаблонного класса не должны зависеть от значений формальных параметров и должны быть одинаковыми для всех типов хранимых данных и дружественных классов. Для реализации этого требования в лабораторной работе класс ListNode сделан закрытым (то-есть в нем нет методов в разделе public:, хотя могли бы и быть), а доступ к его элементам осуществляется через интерфейс дружественного класса FRIEND, являющегося одним из двух формальных параметров класса ListNode (в данной работе это MyStack<INF>).

Пример внешнего определения методов шаблонного класса:

template<class INF>
bool MyStack<INF>::empty(void) {
    if (top == nullptr)
        return true;
    else
        return false;
}

Определение (переименование) типа узла ListNode, хранящего данные класса INF и использующего в качестве дружественного класса FRIEND шаблонный класс MyStack<INF>:

typedef class ListNode<INF, MyStack<INF>> Node;

Теперь вместо typedef class ListNode<INF, MyStack<INF>> он будет называться просто Node.