Стек
Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»).
Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
В цифровом вычислительном комплексе стек называется магазином — по аналогии с магазином в огнестрельном оружии (стрельба начнётся с патрона, заряженного последним).
В 1946 Алан Тьюринг ввёл понятие стека[1][2]. А в 1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею Тьюринга[3].
В некоторых языках (например, Lisp, Python[4]) стеком можно назвать любой список, так как для них доступны операции pop и push. В языке C++ стандартная библиотека имеет класс с реализованной структурой и методами[5]. И т. д.
Программный стекОрганизация в памят
Зачастую стек реализуется в виде однонаправленного списка (каждый элемент в списке содержит помимо хранимой информации в стеке на следующий элемент стека).
Но также часто стек располагается в с упорядоченными адресами. Такая организация стека удобна, если элемент информации занимает в памяти фиксированное количество слов, например, 1 слово. При этом отпадает необходимость хранения в элементе стека явного указателя на следующий элемент стека, что экономит память. При этом указатель стека (Stack Pointer, — SP) обычно является и указывает на адрес головы стека.
Предположим для примера, что голова стека расположена по меньшему адресу, следующие элементы располагаются по нарастающим адресам. При каждом вталкивании слова в стек SP сначала увеличивается на 1 и затем по адресу из SP производится запись в память. При каждом извлечении слова из стека (выталкивании) сначала производится чтение по текущему адресу из SP и последующее уменьшение содержимого SP на 1.
При организации стека в виде однонаправленного списка значением переменной стека является указатель на его вершину — адрес вершины. Если стек пуст, то значение указателя равно NULL.
Пример реализации стека на языке Си
Операции со стеком
Возможны три операции со стеком: добавление элемента (иначе проталкивание, push), удаление элемента (pop) и чтение головного элемента (peek.
При проталкивании (push) добавляется новый элемент, указывающий на элемент, бывший до этого головой. Новый элемент теперь становится головным.
При удалении элемента (pop) убирается первый, а головным становится тот, на который был указатель у этого объекта (следующий элемент). При этом значение убранного элемента возвращается
Область применения
Программный вид стека используется для обхода , например, или . При использовании также будет применяться стек, но его аппаратный вид. Кроме этих назначений, стек используется для организации , реализующей вычисления в . Примером использования стековой машины является программа Unix .
Для отслеживания точек возврата из используется .
, и язык используют стековую модель вычислени.
Идея стека используется в стековой машине среди .
Аппаратный стек
Другое название аппаратного стека — машинный стек. Работа с ним поддерживается аппаратно центральным процессором. Машинный стек используется для нужд выполняющейся программы: хранения переменных и вызова подпрограмм. При вызове подпрограммы (процедуры) процессор помещает в стек адрес команды, следующей за командой вызова подпрограммы «адрес возврата» из подпрограммы. По команде возврата из подпрограммы из стека извлекается адрес возврата в вызвавшую подпрограмму программу и осуществляется переход по этому адресу.
Аналогичные процессы происходят при аппаратном прерывании (процессор X86 при аппаратном прерывании сохраняет автоматически в стеке ещё и регистр флагов). Кроме того, компиляторы размещают локальные переменные процедур в стеке (если в процессоре предусмотрен доступ к произвольному месту стека).
В архитектуре X86 аппаратный стек — непрерывная область памяти, адресуемая специальными регистрами ESP (указатель стека) и SS (селектор сегмента стека)[6].
До использования стека он должен быть инициализирован так, чтобы регистры SS:ESP указывали на адрес головы стека в области физической оперативной памяти, причём под хранение данных в стеке необходимо зарезервировать нужное количество ячеек памяти (очевидно, что стек в ПЗУ, естественно, не может быть организован). Прикладные программы, как правило, от операционной системы получают готовый к употреблению стек. В защищённом режиме работы процессора сегмент состояния задачи содержит четыре селектора сегментов стека (для разных уровней привилегий), но в каждый момент используется только один стек[7].
Примечания
- ↑ Машина Тьюринга: Введение. Дата обращения: 12 февраля 2013.
- ↑ Ali Almossawi. Bad Choices: How Algorithms Can Help You Think Smarter and Live Happier. — John Murray Press, 2017-04-04. — 140 с. — ISBN 978-1-4736-5075-6.
- ↑ Немецкий патент. Дата обращения: 12 февраля 2013. Архивировано 15 февраля 2013 года.
- ↑ Python списки: Встроенные функции. Дата обращения: 12 февраля 2013. Архивировано 15 февраля 2013 года.
- ↑ LIFO stack. Дата обращения: 12 февраля 2013. Архивировано 15 февраля 2013 года.
- ↑ 8.1. Логическая структура памяти программы. Дата обращения: 20 февраля 2013. Архивировано из оригинала 3 декабря 2012 года.
- ↑ Стек. Дата обращения: 12 февраля 2013.
Аспекты операционных систем | |||||
|---|---|---|---|---|---|
| Типы | |||||
| Ядро |
| ||||
| Управление процессами |
| ||||
| Управление и адресация памяти | |||||
| Средства загрузки и инициализации | |||||
| Прочее | |||||
