imported>Gromolyak: /* Программный стек */

2026-02-10T16:30:13Z

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

Новая страница

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

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

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

В 1946 [[Тьюринг, Алан|Алан Тьюринг]] ввёл понятие стека<ref>{{cite web|url=http://abc.vvsu.ru/Books/ebooks_iskt/%D0%AD%D0%BB%D0%B5%D0%BA%D1%82%D1%80%D0%BE%D0%BD%D0%BD%D1%8B%D0%B5%D1%83%D1%87%D0%B5%D0%B1%D0%BD%D0%B8%D0%BA%D0%B8/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F%20%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%BE%D0%B2/%D0%A2%D0%B5%D0%BE%D1%80_%D0%B0%D0%B2%D1%82_%D1%82%D0%B5%D0%BC%D1%8B/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0%20%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0.htm|title=Машина Тьюринга: Введение|access-date=2013-02-12|archive-url=https://web.archive.org/web/20140320172056/http://abc.vvsu.ru/Books/ebooks_iskt/%D0%AD%D0%BB%D0%B5%D0%BA%D1%82%D1%80%D0%BE%D0%BD%D0%BD%D1%8B%D0%B5%D1%83%D1%87%D0%B5%D0%B1%D0%BD%D0%B8%D0%BA%D0%B8/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F%20%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%BE%D0%B2/%D0%A2%D0%B5%D0%BE%D1%80_%D0%B0%D0%B2%D1%82_%D1%82%D0%B5%D0%BC%D1%8B/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0%20%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0.htm|archive-date=2014-03-20|url-status=live}}</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|archive-date=2022-08-07|archive-url=https://web.archive.org/web/20220807062146/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}}</ref>. А в 1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею Тьюринга<ref>{{cite web|url=http://worldwide.espacenet.com/publicationDetails/originalDocument?CC=DE&NR=1094019&KC=&FT=E|title=Немецкий патент|access-date=2013-02-12|archive-url=https://www.webcitation.org/6ERYlTWAH?url=http://worldwide.espacenet.com/publicationDetails/originalDocument?CC=DE|archive-date=2013-02-15|url-status=live}}</ref>.

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

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

=== {{Anchor|STACK-POINTER}}Организация в памяти ===
[[Файл:Lifo stack.svg|thumb|350px|right|Организация стека в виде одномерного упорядоченного по адресам массива. Показаны операции вталкивания и выталкивания данных из стека операциями ''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|push}}), удаление элемента ({{lang-en2|pop}}) и чтение головного элемента ({{lang-en2|peek}})<ref>{{cite web|url=http://www.rsdn.ru/article/alg/adt/adt.xml|title=Введение|access-date=2013-02-11|archive-url=https://www.webcitation.org/6ERYn3XNS?url=http://www.rsdn.ru/article/alg/adt/adt.xml|archive-date=2013-02-15|url-status=live}}</ref>.

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

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

<source lang="c++">
#include <iostream>
#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|url=http://savlm.ucoz.ru/publ/10-1-0-47|title=Стек|access-date=2013-02-12|archive-url=https://www.webcitation.org/6ERYq9IMI?url=http://savlm.ucoz.ru/publ/10-1-0-47|archive-date=2013-02-15|url-status=live}}</ref>.

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

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

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

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

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

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

{{Структуры данных}}
{{Аспекты операционных систем}}

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

Стек - История изменений

imported>Gromolyak: /* Программный стек */