Stack

Что такое структура данных "стек" (англ. - stack) на языке C++.

Давайте представим, что перед вами стоит цилиндр, в котором верхняя часть срезана, тем самым образуя цилиндрическую коробку. На дне этой коробки расположена пружина, а диаметр этого цилиндра равен диаметру обычных тарелок.

Кладем в нашу коробку тарелки, допустим 5 штук. И теперь вопрос: как достать 4-ю тарелку?

Правильный ответ - это вытащить три предыдущие и затем уже четвертую. Именно так работает структура данных "стек" - "первым пришел, последним ушел" или FILO (First In Last Out) . Только теперь представьте, что тарелки- это информационная, а цилиндр- это структурная части. Теперь перейдем к разновидностям стеков.

Стеки бывают двух типов:

1. Статические
2. Динамические

В чём их отличие?

Статический стек в отличие от динамического имеет ограниченное кол-во тарелок(информации). В этом и есть их главное различие.

Вот пример объявления статического стека:

struct Stack_1 
{ 
int info_1; 
int count_1; 
}; 
//объявляем статический стек. 
Stack p_1;

Вот пример объявления динамического стека:

struct Stack_2 { 
int info_2; 
Stack *next_2; 
} ; 
//объявляем динамический стек
Stack *begin_1,*t_1;

где *begin - вершина стека (первая тарелка, которую нужно вытащить) и *t - текущий указатель.

Для стеков существуют три главные операции это:

1. Добавление
2. Удаление
3. Чтение

Давайте рассмотрим каждую из функций по отдельности. Начнем с чтения динамического стека:

void View_1 (Stack_1 *p_1) { 
Stack_1 *t_1 = p_1; 
if ( p_1 == 0 ) { //проверка, есть ли элементы в стеке. 
cout << “ Стек пуст! ” << endl; 
return; 
} 
while( t != 0) { //выполнять цикл, пока не наткнемся на последний элемент. 
cout << t_1->info_1 << endl; 
t_1 = t_1 -> next_1; //переходим к следующему элементу. 
} 
}

Данной функцией, вы сможете прочитать весь ваш стек от А до Я.

Для удаления стека, вы можете воспользоваться данной функцией:

void Del ( Stack **p_1 ) { 
Stack *t_1; 
while ( *p_1 != 0) { 
t_1 = *p_1; 
*p_1 = (*p_1) -> next_1; 
delete t_1; 
} 
}

И для добавления элементов в стек можно использовать данную функцию:

Stack_1* InStack_1 (Stack_1 *p+1, int in_1) { 
Stack_1 *t_1 = new Stack_1; 
t_1 -> info_1 = in_1; //формируем информационную часть. 
t_1 -> next_1 = p_1; //формируем адресную часть. 
return t_1; 
}

Код был написан на Visual studio 2015. Надеемся, что теперь вы полностью разобрались со структурой данных stack.