Стек

{{#if: | }}

Иллюстрация организации стека

Стек (МФА: /stɛk/) (англ. Шаблон:Lang-en2 — стопка) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. Шаблон:Lang-en2, «последним пришёл — первым вышел»).

Чаще всего принцип работы стека сравнивают со стопкой : чтобы взять вторую сверху, нужно сначала взять первую.

В цифровом вычислительном комплексе стек называется магазином — по аналогии с магазином в огнестрельном оружии (стрельба начнётся с патрона, заряженного последним).

В 1946 Алан Тьюринг ввёл понятие стека<ref>Шаблон:Cite web</ref><ref>Шаблон:Книга</ref>. А в 1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею Тьюринга<ref>Шаблон:Cite web</ref>.

В некоторых языках (например, Lisp, Python<ref>Шаблон:Cite web</ref>) стеком можно назвать любой список, так как для них доступны операции pop и push. В языке C++ стандартная библиотека имеет класс с реализованной структурой и методами<ref>Шаблон:Cite web</ref> и т. д.

Программный стек

Шаблон:AnchorОрганизация в памяти

Организация стека в виде одномерного упорядоченного по адресам массива. Показаны операции вталкивания и выталкивания данных из стека операциями push и pop

Зачастую стек реализуется в виде однонаправленного списка (каждый элемент в списке содержит помимо хранимой информации в стеке указатель на следующий элемент стека).

Но также часто стек располагается в одномерном массиве с упорядоченными адресами. Такая организация стека удобна, если элемент информации занимает в памяти фиксированное количество слов, например, 1 слово. При этом отпадает необходимость хранения в элементе стека явного указателя на следующий элемент стека, что экономит память. При этом указатель стека (Stack Pointer, — SP) обычно является регистром процессора и указывает на адрес головы стека.

Предположим для примера, что голова стека расположена по меньшему адресу, следующие элементы располагаются по нарастающим адресам. При каждом вталкивании слова в стек SP сначала увеличивается на 1 и затем по адресу из SP производится запись в память. При каждом извлечении слова из стека (выталкивании) сначала производится чтение по текущему адресу из SP и последующее уменьшение содержимого SP на 1.

При организации стека в виде однонаправленного списка значением переменной стека является указатель на его вершину — адрес вершины. Если стек пуст, то значение указателя равно NULL.

Пример реализации стека на языке Си: <source lang="c">struct stack {

   void *data;
   struct stack *next;

};</source>

Операции со стеком

Возможны три операции со стеком: добавление элемента (иначе проталкивание, Шаблон:Lang-en2), удаление элемента (Шаблон:Lang-en2) и чтение головного элемента (Шаблон:Lang-en2)<ref>Шаблон:Cite web</ref>.

При проталкивании (Шаблон:Lang-en2) добавляется новый элемент, указывающий на элемент, бывший до этого головой. Новый элемент теперь становится головным.

При удалении элемента (Шаблон:Lang-en2) убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент). При этом значение убранного элемента возвращается.

<source lang="c++">

1. include <iostream>
2. include <stdexcept> // для std::overflow_error и std::underflow_error

class ArrayStack { private:

   static const int MAX_SIZE = 100; // Максимальный размер стека
   int stack[MAX_SIZE];
   int topIndex; // Индекс вершины стека

public:

   ArrayStack() : topIndex(-1) {} // Инициализация пустого стека

   // Проверка на пустоту
   bool isEmpty() const {
       return topIndex == -1;
   }

   // Проверка на переполнение
   bool isFull() const {
       return topIndex == MAX_SIZE - 1;
   }

   // Добавление элемента в стек
   void push(int value) {
       if (isFull()) {
           throw std::overflow_error("Стек переполнен!");
       }
       stack[++topIndex] = value;
   }

   // Удаление и возврат верхнего элемента
   int pop() {
       if (isEmpty()) {
           throw std::underflow_error("Стек пуст!");
       }
       return stack[topIndex--];
   }

   // Просмотр верхнего элемента без удаления
   int peek() const {
       if (isEmpty()) {
           throw std::underflow_error("Стек пуст!");
       }
       return stack[topIndex];
   }

   // Вывод стека
   void print() const {
       if (isEmpty()) {
           std::cout << "Стек пуст!" << std::endl;
           return;
       }
       std::cout << "Стек (сверху вниз): ";
       for (int i = topIndex; i >= 0; --i) {
           std::cout << stack[i] << " ";
       }
       std::cout << std::endl;
   }

};

int main() {

   ArrayStack stack;

   stack.push(10);
   stack.push(20);
   stack.push(30);

   stack.print(); // Вывод: 30 20 10

   std::cout << "Верхний элемент: " << stack.peek() << std::endl; // 30

   stack.pop();
   stack.print(); // Вывод: 20 10

   return 0;

}</source>

Область применения

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

Для отслеживания точек возврата из подпрограмм используется стек вызовов.

Арифметические сопроцессоры, программируемые микрокалькуляторы и язык Forth используют стековую модель вычислений<ref>Шаблон:Cite web</ref>.

Идея стека используется в стековой машине среди стековых языков программирования.

Аппаратный стек

Другое название аппаратного стека — машинный стек. Работа с ним поддерживается аппаратно центральным процессором. Машинный стек используется для нужд выполняющейся программы: хранения переменных и вызова подпрограмм. При вызове подпрограммы (процедуры) процессор помещает в стек адрес команды, следующей за командой вызова подпрограммы «адрес возврата» из подпрограммы. По команде возврата из подпрограммы из стека извлекается адрес возврата в вызвавшую подпрограмму программу и осуществляется переход по этому адресу.

Аналогичные процессы происходят при аппаратном прерывании (процессор X86 при аппаратном прерывании сохраняет автоматически в стеке ещё и регистр флагов). Кроме того, компиляторы размещают локальные переменные процедур в стеке (если в процессоре предусмотрен доступ к произвольному месту стека).

В архитектуре X86 аппаратный стек — непрерывная область памяти, адресуемая специальными регистрами ESP (указатель стека) и SS (селектор сегмента стека)<ref name=ReferenceA>Шаблон:Cite web</ref>.

До использования стека он должен быть инициализирован так, чтобы регистры SS:ESP указывали на адрес головы стека в области физической оперативной памяти, причём под хранение данных в стеке необходимо зарезервировать нужное количество ячеек памяти (очевидно, что стек в ПЗУ, естественно, не может быть организован). Прикладные программы, как правило, от операционной системы получают готовый к употреблению стек. В защищённом режиме работы процессора сегмент состояния задачи содержит четыре селектора сегментов стека (для разных уровней привилегий), но в каждый момент используется только один стек<ref>Шаблон:Cite web</ref>.