Стек  — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO.Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.В цифровом вычислительном комплексе стек называется магазином — по аналогии с магазином в огнестрельном оружии.В 1946 Алан Тьюринг ввёл понятие стека. А в 1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею Тьюринга.В некоторых языках стеком можно назвать любой список, так как для них доступны операции pop и push. В языке C++ стандартная библиотека имеет класс с реализованной структурой и методами. И т. д.Программный стек:Организация в памяти:Но также часто стек располагается в одномерном массиве с упорядоченными адресами. Такая организация стека удобна, если элемент информации занимает в памяти фиксированное количество слов, например, 1 слово. При этом отпадает необходимость хранения в элементе стека явного указателя на следующий элемент стека, что экономит память. При этом указатель стека обычно является регистром процессора и указывает на адрес головы стека.Предположим для примера, что голова стека расположена по меньшему адресу, следующие элементы располагаются по нарастающим адресам. При каждом вталкивании слова в стек SP сначала уменьшается на 1 и затем по адресу из SP производится запись в память. При каждом извлечении слова из стека сначала производится чтение по текущему адресу из SP и последующее увеличение содержимого SP на 1.При организации стека в виде однонаправленного списка значением переменной стека является указатель на его вершину — адрес вершины. Если стек пуст, то значение указателя равно NULL.Операции со стеком:Возможны три операции со стеком: добавление элемента, удаление элемента и чтение головного элемента.При проталкивании добавляется новый элемент, указывающий на элемент, бывший до этого головой. Новый элемент теперь становится головным.При удалении элемента убирается первый, а головным становится тот, на который был указатель у этого объекта. При этом значение убранного элемента возвращается.Область применения:Программный вид стека используется для обхода структур данных, например, дерево или граф. При использовании рекурсивных функций также будет применяться стек, но его аппаратный вид. Кроме этих назначений, стек используется для организации стековой машины, реализующей вычисления в обратной польской записи.Арифметические сопроцессоры, программируемые микрокалькуляторы и язык Forth используют стековую модель вычислений.Аппаратный стек:Другое название аппаратного стека — машинный стек. Работа с ним поддерживается аппаратно центральным процессором. Машинный стек используется для нужд выполняющейся программы: хранения переменных и вызова подпрограмм. При вызове подпрограммы процессор помещает в стек адрес команды, следующей за командой вызова подпрограммы «адрес возврата» из подпрограммы. По команде возврата из подпрограммы из стека извлекается адрес возврата в вызвавшую подпрограмму программу и осуществляется переход по этому адресу.Аналогичные процессы происходят при аппаратном прерывании. Кроме того, компиляторы размещают локальные переменные процедур в стеке.В архитектуре X86 аппаратный стек — непрерывная область памяти, адресуемая специальными регистрами ESP и SS.До использования стека он должен быть инициализирован так, чтобы регистры SS:ESP указывали на адрес головы стека в области физической оперативной памяти, причём под хранение данных в стеке необходимо зарезервировать нужное количество ячеек памяти. Прикладные программы, как правило, от операционной системы получают готовый к употреблению стек. В защищённом режиме работы процессора сегмент состояния задачи содержит четыре селектора сегментов стека, но в каждый момент используется только один стек.