Лабораторная работа №3. Динамическая структура СТЕК

Цель работы: изучить алгоритмы работы с динамическими структурами данных в виде стека.

Краткие теоретические сведения

Стек – структура типа LIFO (Last In, First Out) – последним вошел, первым выйдет. Элементы в стек можно добавлять или извлекать только через его вершину. Программно стек реализуется в виде однонаправленного списка с одной точкой входа – вершиной стека.

Максимальное число элементов стека не ограничивается, т.е. по мере добавления в стек нового элемента память под него должна запрашиваться, а при удалении – освобождаться. Таким образом, стек – динамическая структура данных, состоящая из переменного числа элементов.

Для работы со стеком введем следующую структуру (вместо приведенного типа Stack может быть любой другой идентификатор):

struct Stack {

int info; // Информационная часть элемента, например, int

Stack *next;// Адресная часть – указатель на следующий элемент

} *begin; // Указатель вершины стека

При работе со стеком обычно выполняются следующие операции*:

– формирование стека (добавление элемента в стек);

– обработка элементов стека (просмотр, поиск, удаление);

– освобождение памяти, занятой стеком.

Приведем примеры основных функций для работы со стеком, взяв для простоты в качестве информационной части целые числа, т.е. объявленную выше структуру типа Stack.