Теория

Стек часто описывают в двух реализациях: как статическая структура данных (массив) и как динамическая структура данных (связный список). На практике первый вариант используется редко и он не представляет большого интереса, поэтому остановим своё внимание на второй реализации. Визуально стек можно представить следующим образом (рис.1).

Рис 1 Представление стека в графическом виде.

Связные списки, такие как стек, имеют несколько стандартных функций push(затолкнуть элемент), pop(вытолкнуть элемент), clean(удалить все элементы), view(просмотр элементов). Рассмотрим перечисленные функции более подробно. Функция push выполняет несколько операций: создание нового узла, инициализация информационного поля, ссылочное поле нового узла ссылается на head, head указывает на новый элемент. Добавим новое значение в стек (push 4). После операции push линейный список содержит один элемент (рис. 2).

Рис 2. Добавление нового значения.

Добавим ещё несколько значений в список (push 6 и push 7). Стек содержит три элемента (рис. 3) в следующем порядке.

Рис 3. Добавление новых значений.

Далее рассмотрим функцию pop, она выполняет следующие операций: перемещает head указатель на следующий элемент в линейном списке, удаляет текущий элемент, возвращает значение информационного поля. Выполнив функцию pop над линейным списком. Получим следующее состояние списка (рис. 4). Принцип работы стека можно описать так, первым вошёл, но последним вышел.

Рис 4. Выталкивание элемента из списка.

Функция view пробегает по всем элементам и выводит в консоль значение информационного поля. Функция clean удаляет все элементы из списка и присваивает заголовку пусто (head=null). После данной операции стек возвращается в исходное состояние.

Программная реализация

typedef int newtp;
struct node //описание структуры
{
newtp data;
node *next;
} *Head=NULL;
void push(newtp val)//добавить узел в стек
{
node *a=new node;
a->data=val;
a->next=Head;
Head=a;
}
newtp pop()//вытолкнуть узел из стека
{
if(Head==NULL)
return (newtp)0;
node *a=Head;
newtp val=a->data;
Head=a->next;
delete a;
return val;
}
void clean()//удалить все элементы из стека
{
for(node *a=Head;a!=NULL;a=a->next) delete a;
Head=NULL;
}
void view()//просмотр элементов стека
{
for(node *a=Head;a!=NULL;a=a->next) printf ("Value=%d \n",(int)a->data);//печать зависит от типа выводимого значения в данном примере int, но если тип измениться печать необходимо изменить
}