Структура данных — Стек (LIFO, Stack)

После описания базовой структуры данных очередь, как правило, необходимо сразу рассказывать про стек. Эти две базовые конструкции, наиболее массово распространены в информатике, логистике и просто в быту. Они всегда идут рядом и достаточно похожи друг на друга. Единственная разница только в методе доступа к элементам данных и способу добавления новых значений в «пачку».

Стек (Stack) — это абстрактная структура данных для организации хранения списка элементов. Сам термин впервые был введён Аланом Тьюрингом ещё в далеком 1946 году. В основе стека стоит аббревиатура LIFO (Last In – First Out; первым попал — первым и вылетел), что означает, что каждый новый поступающий элемент попадает не в хвост списка (как это было с очередью), а в голову — в начало.

Каноническим и самым распространённым примером стека — является пример с тарелками. Допустим, вы холостяк 🙂 и у вас полная раковина грязных тарелок. Пришло время наконец-то помыть посуду. Скорее всего, ваш алгоритм будет таким: взять первую грязную тарелку, помыть и отложить в сторону. Следующие вымытые тарелки ставим поверх помытых, таким образом у нас появляется массив посуды, в котором снизу будет самая первая тарелка, а сверху — самая последняя. Это способ внесения новых элементов — добавляем новое сверху стопки (в голову нашего стека, если говорить абстрактно). Следующая операция после добавления — считывание элементов, когда мы во время обеда берём чистую тарелку сверху нашей вымытой стопки. Таким образом, когда будем перемыта вся посуда и настанет время обеда — мы первой возьмём ту тарелку, которая была вымыта последней. Это и есть основной принцип LIFO — кто последний был добавлен, первым и будет использован.

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

Примеры У стека широкая область применения: прокладки пути в графах и деревьях, существуют целые стековые языки программирования (в первую очередь использующие ассемблер, как финальный результат компиляции, как это реализовано в Java/C#), организация работы «стековых» машин (к примеру, для расчётов по алгоритму обратной польской нотации)

В повседневной жизни существуют и другие примеры стека: выглаженные футболки, магазин с патронами, стек вызовов ваших функций\методов, рекурсивные функции и т.д.

В программировании, стек играет очень важную роль, если не самую главную. В иерархии методов (call history) всегда будет именно (и только) стек. Приведём следующий псевдокод для примера:

ФУНКЦИЯ MAIN(){
A();
}

ФУНКЦИЯ A(){
B();
}

ФУНКЦИЯ B(){
C();
D();
}

ФУНКЦИЯ C(){
D();
}

ФУНКЦИЯ D(){
E();
}

ФУНКЦИЯ E(){
}

Вызываемые функции будут также, как и тарелки складываться в одну стопку. Начиная с функции MAIN, будет вызвана A, затем B, C, D, E, D и E. После чего управление будет возвращаться «назад» — пока вновь не дойдёт до MAIN и работы программы будет завершена.

Рекурсивные методы вызываются подобным образом. Отсюда и классическая проблема stack overflow (знакомый сайт, да?), когда стек забивается до отказа выполняемыми методами и мы упираемся в физическое ограничение по памяти или возможностям вашего компьютера или ОС. С этим нужно быть осторожными.

Привычными методами внутри стека являются Push – добавление наверх и Pop – считывание и удаление с верхушки. Иногда добавляются также методы Peek для считывания верхнего элемента без удаления, а также IsFull и IsEmpty — для понимания заполненности стека. Алгоритм организации стека не сложнее очереди:

Шаг №1 — объявление переменных:

• Объявим целочисленную переменную size, в которой будет хранится размер стека;
• Объявляем локальный массив stack типа T с необходимой нам размерностью (size);
• Объявим целочисленную локальную переменную top равной 0, данную переменную ;

Шаг №2 — функция\метод добавления элемента в стек (push):

• Проверяем не заполнен ли стек полностью (условие, когда top==size);
• Если стек переполнен — выбрасываем ошибку;
• Если есть место — вставляем элемент в массив stack[top]=value и после этого делаем инкремент для top;

Шаг №3 — функция\метод считывания элемента из головы стека (pop):

• Деинкрементим переменную top и возвращаем значение из stack[top];
• При этом массив по нужному индексу не очищается, просто при следующем push — будет произведена замена значений;

Вот и всё. Для понимания стек не сложнее очереди. Знание этой базовой структуры данных пригодится не только в программировании. Данной терминологией оперируют и в организации доставки грузов, складов и просто в повседневной жизни. Чуть позже я напишу нативную реализацию стека на языке C# (без использования стека из фреймворка System.Collections.Stack) и мы перейдём к рассмотрению других фундаментальных структур данных.