Структура данных - способ хранения данных, определяющий правила добавления, поиска, изменения и удаления этих данных. Структуры в основном различают по эффективности использования памяти и алгоритмической сложности операций с данными. Простейшим примером структуры данных является массив. Существует набор структур данных, получивший распространение в компьютерных и информационных технологиях, одним из них является стек.
Стек - структура данных, основанная принципе LIFO. Расшифровка акронима LIFO (Last In First Out) относится к единице данных - последний
добавленный (last in) элемент будет первым на выдачу (first out). При последовательном добавлении нескольких элементов данных в LIFO
извлекаться они будут в порядке, обратном порядку добавления. Основанный на принципе LIFO стек определяет всего две операции для изменения
своего содержимого - это добавить элемент (традиционно операция называется push) и извлечь элемент (pop). Никаких операций для поиска и
изменения данных в "чистом" стеке не предусматривается. Рисунок ниже иллюстрирует последовательное добавление в стек и извлечение из него 5
элементов.
Обычно дополнительно вводят понятие верхушки стека. Верхушкой стека называют последний добавленный элемент стека, указатель на него или любой другой его идентификатор. Обычно именно верхушка стека является операндом push и pop, отвечающим за идентификацию самого стека. При этом в случае первой операции (добавление элемента, push) верхушка стека автоматически изменяется так, чтобы указывать на добавленный
элемент, а после исполнения второй операции (извлечение, pop) верхушка стека должна указывать на предпоследний элемент.
В подавляющем большинстве процессоров эта структура данных представлена на уровне ISA
: есть команды push, pop и регистр верхушки стека (stack pointer, %sp) и их аналоги. Дело в том, что почти в каждом языке
программирования есть функции, подпрограммы и т.д., цепочки вызовов которых очень удачно представляются в виде стека (callstack). В стек я́дра операционных систем
могут складывать прерывания, ядро и обычные программы - локальные переменные.