Просмотр кода страницы Стек

{{другие значения}}
[[Файл:Stack preview.png|thumb|400px|Иллюстрация организации стека]]
'''Стек''' ({{lang-en|stack}} — стопка; читается ''стэк'') — [[абстрактный тип данных]], представляющий собой [[Список (информатика)|список элементов]], организованных по принципу ''[[LIFO]]'' ({{lang-en|last in — first out}}, «последним пришёл — первым вышел»).

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

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

В 1946 [[Тьюринг, Алан|Алан Тьюринг]] ввёл понятие стека<ref>{{cite web|url=http://abc.vvsu.ru/Books/ebooks_iskt/Электронныеучебники/Теория%20автоматов/Теор_авт_темы/Машина%20Тьюринга.htm|title=Машина Тьюринга: Введение|accessdate=2013-02-12|archiveurl=|archivedate=}}</ref><ref>{{Книга|ссылка=https://books.google.ru/books?id=MIn1DAAAQBAJ&pg=PT36&lpg=PT36&dq=In+1946,+Alan+Turing+introduced+the+concept+of+stack.&source=bl&ots=-VILFtL-Ju&sig=ACfU3U1A52mE48ZF9P3SVAxvEBzci2QtZQ|автор=Ali Almossawi|заглавие=Bad Choices: How Algorithms Can Help You Think Smarter and Live Happier|год=2017-04-04|издательство=John Murray Press|страниц=140|isbn=978-1-4736-5075-6}}</ref>. А в 1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею Тьюринга<ref>{{cite web|url=http://worldwide.espacenet.com/publicationDetails/originalDocument?CC=DE&NR=1094019&KC=&FT=E|title=Немецкий патент|accessdate=2013-02-12|archiveurl=http://www.webcitation.org/6ERYlTWAH|archivedate=2013-02-15}}</ref>.

В некоторых языках (например, [[Lisp]], [[Python]]<ref>{{cite web|url=http://www.ibm.com/developerworks/ru/library/l-python_part_3/index.html|title=Python списки: Встроенные функции|accessdate=2013-02-12|archiveurl=http://www.webcitation.org/6ERYlx0vo|archivedate=2013-02-15}}</ref>) стеком можно назвать любой список, так как для них доступны операции pop и push. В языке [[C++]] [[Стандартная библиотека языка C++|стандартная библиотека]] имеет класс с реализованной структурой и методами<ref>{{cite web|url=http://www.cplusplus.com/reference/stack/stack/|title=LIFO stack|accessdate=2013-02-12|archiveurl=http://www.webcitation.org/6ERYmbSlC|archivedate=2013-02-15}}</ref>. И т. д.

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

=== Организация в памяти ===
[[Файл:Lifo stack.png|thumb|350px|right|Организация стека в виде одномерного упорядоченного по адресам массива. Показаны операции вталкивания и выталкивания данных из стека операциями ''push'' и ''pop''.]]
Зачастую стек реализуется в виде однонаправленного списка (каждый элемент в списке содержит помимо хранимой информации в стеке [[Указатель (тип данных)|указатель]] на следующий элемент стека).

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

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

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

Пример реализации стека на языке Си:
<source lang="c">struct stack
{
    char *data;
    struct stack *next;
};</source>

=== Операции со стеком ===
Возможны три операции со стеком: добавление элемента (иначе проталкивание, {{lang-en2|push}}), удаление элемента ({{lang-en2|pop}}) и чтение головного элемента ({{lang-en2|peek}})<ref>{{cite web|url=http://www.rsdn.ru/article/alg/adt/adt.xml|title=Введение|accessdate=2013-02-11|archiveurl=http://www.webcitation.org/6ERYn3XNS|archivedate=2013-02-15}}</ref>.

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

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

<source lang="cpp">
void push( STACK *ps, int x ) // Добавление в стек нового элемента
{
    if ( ps->size == STACKSIZE ) // Не переполнен ли стек?
    {
        fputs( "Error: stack overflow\n", stderr );
        abort();
    }
    else
    {
        ps->items[++ps->size] = x;
    }
}

int pop( STACK *ps ) // Удаление из стека
{
    if ( ps->size == 0 ) // Не опустел ли стек?
    {
        fputs( "Error: stack underflow\n", stderr );
        abort();
    }
    else
    {
        return ps->items[ps->size--];
    }
}</source>

=== Область применения ===
Программный вид стека используется для обхода [[Структура данных|структур данных]], например, [[Дерево (теория графов)|дерево]] или [[Граф (математика)|граф]]. При использовании [[Рекурсивные функции|рекурсивных функций]] также будет применяться стек, но его аппаратный вид. Кроме этих назначений, стек используется для организации [[Обратная польская запись|стековой машины]], реализующей вычисления в [[Обратная польская запись|обратной польской записи]]. Примером использования стековой машины является программа Unix [[dc]].

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

[[Математический сопроцессор|Арифметические сопроцессоры]], [[Программируемый калькулятор|программируемые микрокалькуляторы]] и язык [[Forth]] используют стековую модель вычислений<ref>{{cite web|url=http://savlm.ucoz.ru/publ/10-1-0-47|title=Стек|accessdate=2013-02-12|archiveurl=http://www.webcitation.org/6ERYq9IMI|archivedate=2013-02-15}}</ref>.

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

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

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

В [[X86|архитектуре X86]] аппаратный стек — непрерывная область памяти, адресуемая специальными регистрами ESP (указатель стека) и SS (селектор сегмента стека)<ref name=ReferenceA>{{cite web|url=http://dvo.sut.ru/libr/cvti/i618buz/8.htm|title=8.1. Логическая структура памяти программы|accessdate=2013-02-20|archiveurl=https://web.archive.org/web/20121203072017/http://dvo.sut.ru/libr/cvti/i618buz/8.htm|archivedate=2012-12-03|deadlink=yes}}</ref>.

До использования стека он должен быть инициализирован так, чтобы регистры SS:ESP указывали на адрес головы стека в области физической оперативной памяти, причём под хранение данных в стеке необходимо зарезервировать нужное количество ячеек памяти (очевидно, что стек в [[Постоянное запоминающее устройство|ПЗУ]], естественно, не может быть организован). Прикладные программы, как правило, от операционной системы получают готовый к употреблению стек. В защищённом режиме работы процессора сегмент состояния задачи содержит четыре селектора сегментов стека (для разных уровней привилегий), но в каждый момент используется только один стек<ref>{{cite web|url=https://math.semestr.ru/inf/memory9.php|title=Стек|accessdate=2013-02-12|archiveurl=|archivedate=}}</ref>.

== Примечания ==
{{wikibooks|Реализации алгоритмов/Стек|Стек}}
{{примечания}}

{{Структуры данных}}

[[Категория:Стек]]
[[Категория:Технологии процессоров]]