Использование стека. Как это работает

При освоении программирования, рано или поздно, возникает вопрос: "Что такое стек? ".
Наиболее наглядным способом объяснения я считаю программу на языке ассемблера (не пугайтесь), которая просто добавляет данные в стек.

Стек - это структура данных присущая всей программируемой технике. Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю. Часто стек называют магазином - по аналогии с магазином в огнестрельном оружии (стрельба начнётся с патрона, заряженного последним).

Зачем все это нужно?

Вы вряд ли сможете написать программу, которая не будет использовать функции (подпрограммы). При вызове функции в стек копируется адрес для возврата после окончания выполнения данной подпрограммы. По окончании её выполнения адрес возвращается из стека в счетчик команд и программа продолжает выполняться с места после функции.
Также в стек необходимо помещать регистры, которые используются в данной подпрограмме (в языках высокого уровня этим занимается компилятор).
Все вышесказанное характерно для так называемого аппаратного стека. Надеюсь вы догадываетесь, что такая структура данных (LIFO - last in, first out) полезна далеко не только при работе на низком уровне. Часто возникает необходимость хранить данные в таком порядке (например известный алгоритм разбора арифметических выражений основан на работе со стеком), тогда программисты реализуют программный стек.

Как это работает?

Давайте разберем работу со стеком на примере контроллеров семейства MSP430. Я выбрал их только из-за того что у меня оказалась установленной среда для работы с ними.
В MSP430 стек основан на предекрементной схеме. Т.е. перед тем как вы записываете данные в стек он уменьшает адрес вершины стека (верхней тарелки). Бывает также постдекрементный/постинкрементный (вычитание/добавление вершины стека происходит после записи данных) и прединкрементный (перед записью адрес вершины увеличивается).
Если стек увеличивает свой адрес при записи данных, говорят о стеке растущем вверх, если же уменьшает - вниз.
За хранения адреса вершины стека отвечает регистр SP.

Как видите адрес вершины по умолчанию у нас 0x0A00.

Рассмотрим вот такую программу:

PUSH #0123h ; Помещение числа 0123h на вершину стека (TOS) ; копируем данные из памяти MOV.W &0x0A00, R5 MOV.W &0x09FE, R6 ; пишем еще два числа PUSH #9250h PUSH #0000h ; выводим данные из стека POP R8 POP R9 POP R10

Что делает эта программа?

Командой PUSH мы помещаем данные 0123h в стек. Казалось бы этой командой мы запишем 0123h в память по адресу 0x0A00, но мы ведь помним, что стек у нас предекрементный. Поэтому сначала адрес уменьшается на 2 (0x0A00 - 2 = 0x09FE) и в ячейку с полученным адресом записываются данные.

Вот так выглядела память изначально:

После выполнения команды PUSH (красным выделены изменения):

Итак данные записались.
Проверим так ли это выполнив две команды пересылки (mov). Сначала получим данные из ячейки 0x0A00 и запишем их в регистр R5, а затем запишем в регистр R6 данные из ячейки 0x09FE.
После этого в регистрах будет данные:

При выполнении команд POP вершина стека будет увеличиваться на 2 при каждой команде, а в регистры R8-10 попадут данные: 0x0000, 0x9250 и 0x0123 соответственно.
При добавлении других данные память (которая все еще содержит данные, выведенные из стека) будет заполнена новыми значениями.

Проиллюстрировать работу со стеком можно так (слева на право):

Изначально адресом стека был 0x0A00, в нем хранились 0000. При выполнении PUSH верхушкой стека стала ячека ниже (с адресом 0x09FE) и в неё записались данные. С каждой следующей командой верхушка находиться ниже в памяти.
При выполнении команды POP картина обратная.

Жду ваши вопросы в комментариях.

IBM совершила драматическую ошибку, не предусмотрев аппаратную реализацию стека. Эта серия содержала много других неудачных решений, но, к сожалению, была скопирована в Советском Союзе под названием ЕС ЭВМ (Единая Серия), а все собственные разработки были приостановлены. Это отбросило советскую промышленность на много лет назад в области разработки компьютеров.

Очередь

Очередь как структура данных понятна даже людям, не знакомым с программированием. Очередь содержит элементы, как бы выстроенные друг за другом в цепочку. У очереди есть начало и конец. Добавлять новые элементы можно только в конец очереди, забирать элементы можно только из начала. В отличие от обычной очереди, которую всегда можно при желании покинуть, из середины программистской очереди удалять элементы нельзя.

Очередь можно представить в виде трубки. В один конец трубки можно добавлять шарики - элементы очереди, из другого конца они извлекаются. Элементы в середине очереди, т.е. шарики внутри трубки, недоступны. Конец трубки, в который добавляются шарики, соответствует концу очереди, конец, из которого они извлекаются - началу очереди. Таким образом, концы трубки не симметричны, шарики внутри трубки движутся только в одном направлении.

В принципе, можно было бы разрешить добавлять элементы в оба конца очереди и забирать их также из обоих концов. Такая структура данных в программировании тоже существует, ее название - " дек ", от англ. Double Ended Queue, т.е. очередь с двумя концами. Дек применяется значительно реже, чем очередь.

Использование очереди в программировании почти соответствует ее роли в обычной жизни. Очередь практически всегда связана с обслуживанием запросов, в тех случаях, когда они не могут быть выполнены мгновенно. Очередь поддерживает также порядок обслуживания запросов. Рассмотрим, к примеру, что происходит, когда человек нажимает клавишу на клавиатуре компьютера. Тем самым человек просит компьютер выполнить некоторое действие. Например, если он просто печатает текст, то действие должно состоять в добавлении к тексту одного символа и может сопровождаться перерисовкой области экрана, прокруткой окна, переформатированием абзаца и т.п.

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

В системе Windows работа оконных приложений основана на сообщениях, которые посылаются этим приложениям. Например, бывают сообщения о нажатии на клавишу мыши, о закрытии окна, о необходимости перерисовки области окна, о выборе пункта меню и т.п. Каждая программа имеет очередь запросов . Когда программа получает свой квант времени на выполнение, она выбирает очередной запрос из начала очереди и выполняет его. Таким образом, работа оконного приложения состоит, упрощенно говоря, в последовательном выполнении запросов из ее очереди. Очередь поддерживается операционной системой.

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

Реализация очереди на базе массива

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

При непрерывной реализации очереди в качестве базы выступает массив фиксированной длины N , таким образом, очередь ограничена и не может содержать более N элементов. Индексы элементов массива изменяются в пределах от 0 до N - 1 . Кроме массива, реализация очереди хранит три простые переменные: индекс начала очереди, индекс конца очереди, число элементов очереди. Элементы очереди содержатся в отрезке массива от индекса начала до индекса конца.

При добавлении нового элемента в конец очереди индекс конца сперва увеличивается на единицу, затем новый элемент записывается в ячейку массива с этим индексом. Аналогично, при извлечении элемента из начала очереди содержимое ячейки массива с индексом начала очереди запоминается в качестве результата операции, затем индекс начала очереди увеличивается на единицу. Как индекс начала очереди, так и индекс конца при работе двигаются слева направо. Что происходит, когда индекс конца очереди достигает конца массива, т.е. N - 1 ?

Ключевая идея реализации очереди состоит в том, что массив мысленно как бы зацикливается в кольцо. Считается, что за последним элементом массива следует его первый элемент (напомним, что последний элемент имеет индекс N - 1 , а первый - индекс 0). При сдвиге индекса конца очереди вправо в случае, когда он указывает на последний элемент массива, он переходит на первый элемент. Таким образом, непрерывный отрезок массива, занимаемый элементами очереди, может переходить через конец массива на его начало.

Стек

Стек - самая популярная и, пожалуй, самая важная структура данных в программировании. Стек представляет собой запоминающее устройство, из которого элементы извлекаются в порядке, обратном их добавлению. Это как бы неправильная очередь, в которой первым обслуживают того, кто встал в нее последним. В программистской литературе общепринятыми являются аббревиатуры, обозначающие дисциплину работы очереди и стека. Дисциплина работы очереди обозначается FIFO, что означает первым пришел - первым уйдешь (First In First Out). Дисциплина работы стека обозначается LIFO, последним пришел - первым уйдешь (Last In First Out).

Стек можно представить в виде трубки с подпружиненым дном, расположеной вертикально. Верхний конец трубки открыт, в него можно добавлять, или, как говорят, заталкивать элементы. Общепринятые английские термины в этом плане очень красочны, операция добавления элемента в стек обозначается push, в переводе "затолкнуть, запихнуть". Новый добавляемый элемент проталкивает элементы, помещеные в стек ранее, на одну позицию вниз. При извлечении элементов из стека они как бы выталкиваются вверх, по-английски pop ("выстреливают").

Примером стека может служить стог сена, стопка бумаг на столе, стопка тарелок и т.п. Отсюда произошло название стека, что по-английски означает стопка. Тарелки снимаются со стопки в порядке, обратном их добавлению. Доступна только верхняя тарелка, т.е. тарелка на вершине стека . Хорошим примером будет также служить железнодорожный тупик, в который можно составлять вагоны.

Использование стека в программировании

Стек применяется довольно часто, причем в самых разных ситуациях. Объединяет их следующая цель: нужно сохранить некоторую работу, которая еще не выполнена до конца, при необходимости переключения на другую задачу. Стек используется для временного сохранения состояния не выполненного до конца задания. После сохранения состояния компьютер переключается на другую задачу. По окончании ее выполнения состояние отложенного задания восстанавливается из стека, и компьютер продолжает прерванную работу.

Почему именно стек используется для сохранения состояния прерванного задания? Предположим, что компьютер выполняет задачу A . В процессе ее выполнения возникает необходимость выполнить задачу B . Состояние задачи A запоминается, и компьютер переходит к выполнению задачи B . Но ведь и при выполнении задачи B компьютер может переключиться на другую задачу C , и нужно будет сохранить состояние задачи B , прежде чем перейти к C . Позже, по окончании C будет сперва восстановлено состояние задачи B , затем, по окончании B , - состояние задачи A . Таким образом, восстановление происходит в порядке, обратном сохранению, что соответствует дисциплине работы стека.

Стек позволяет организовать рекурсию, т.е. обращение подпрограммы к самой себе либо непосредственно, либо через цепочку других вызовов. Пусть, например, подпрограмма A выполняет алгоритм, зависящий от входного параметра X и, возможно, от состояния глобальных данных. Для самых простых значений X алгоритм реализуется непосредственно. В случае более сложных значений X алгоритм реализуется как сведение к применению того же алгоритма для более простых значений X . При этом подпрограмма A обращается сама к себе, передавая в качестве параметра более простое значение X . При таком обращении предыдущее значение параметра X , а также все локальные переменные подпрограммы A сохраняются в стеке. Далее создается новый набор локальных переменных и переменная, содержащая новое (более простое) значение параметра X . Вызванная подпрограмма A работает с новым набором переменных, не разрушая предыдущего набора. По окончании вызова старый набор локальных переменных и старое состояние входного параметра X восстанавливаются из стека, и подпрограмма продолжает работу с того места, где она была прервана.

На самом деле даже не приходится специальным образом сохранять значения локальных переменных подпрограммы в стеке. Дело в том, что локальные переменные подпрограммы (т.е. ее внутренние, рабочие переменные , которые создаются в начале ее выполнения и уничтожаются в конце) размещаются в стеке, реализованном аппаратно на базе обычной оперативной памяти. В самом начале работы подпрограмма захватывает место в стеке под свои локальные переменные, этот участок памяти в аппаратном стеке называют обычно блок локальных переменных или по-английски frame ("кадр "). В момент окончания работы подпрограмма освобождает память, удаляя из стека блок своих локальных переменных.

Кроме локальных переменных, в аппаратном стеке сохраняются адреса возврата при вызовах подпрограмм. Пусть в некоторой точке программы A вызывается подпрограмма B . Перед вызовом подпрограммы B адрес инструкции, следующей за инструкцией вызова B , сохраняется в стеке. Это так называемый адрес возврата в программу A . По окончании работы подпрограмма B извлекает из стека адрес возврата в программу A и возвращает управление по этому адресу. Таким образом, компьютер продолжает выполнение программы A , начиная с инструкции, следующей за инструкцией вызова. В большинстве процессоров имеются специальные команды, поддерживающие вызов подпрограммы с предварительным помещением адреса возврата в стек и возврат из подпрограммы по адресу, извлекаемому из стека. Обычно команда вызова назывется call , команда возврата - return .

В стек помещаются также параметры подпрограммы или функции перед ее вызовом. Порядок их помещения в стек зависит от соглашений, принятых в языках высокого уровня. Так, в языке Си или C++ на вершине стека лежит первый аргумент функции, под ним второй и так далее. В Паскале все наоборот, на вершине стека лежит последний аргумент функции. (Поэтому, кстати, в Си возможны функции с переменным числом аргументов, такие, как printf , а в Паскале нет.)

В Фортране-4, одном из самых старых и самых удачных языков программирования, аргументы передаются через специальную область памяти, которая может располагаться не в стеке, поскольку до конца 70-х годов XX века еще существовали компьютеры вроде IBM 360 или ЕС ЭВМ без аппаратной реализации стека. Адреса возврата также сохранялись не в стеке, а в фиксированных для каждой подпрограммы ячейках памяти. Программисты называют такую память статической в том смысле, что статические переменные занимают всегда одно и то же место в памяти в любой момент работы программы. При использовании только статической памяти рекурсия невозможна, поскольку при новом вызове предыдущие значения локальных переменных разрушаются. В эталонном Фортране-4 использовались только статические переменные, а рекурсия была запрещена. До сих пор язык Фортран широко используется в научных и инженерных расчетах, однако, современный стандарт Фортрана-90 уже вводит стековую память, устраняя недостатки ранних версий языка.

Реализация стека на базе массива

Реализация стека на базе массива является классикой программирования. Иногда даже само понятие стека не вполне корректно отождествляется с этой реализацией.

Базой реализации является массив размера N , таким образом, реализуется стек ограниченного размера, максимальная глубина которого не может превышать N . Индексы ячеек массива изменяются от 0 до N - 1 . Элементы стека хранятся в массиве следующим образом: элемент на дне стека располагается в начале массива, т.е. в ячейке с индексом 0. Элемент, расположенный над самым нижним элементом стека, хранится в ячейке с индексом 1, и так далее. Вершина стека хранится где-то в середине массива. Индекс элемента на вершине стека хранится в специальной переменной, которую обычно называют указателем N - 1 . Элементы стека занимают непрерывный отрезок массива, начиная с ячейки, индекс которой хранится в указателе стека, и заканчивая последней ячейкой массива. В этом варианте стек растет в сторону уменьшения индексов. Если стек пуст, то указатель стека содержит значение N (которое на единицу больше, чем индекс последней ячейки массива).

Стек - это феномен программирования и естественное решение. Стек сразу пришел в компьютерное дело и стал таким «родным», как будто именно с него все начиналось.

Без стека не работает процессор, нет рекурсии и эффективные вызовы функций организовать невозможно. Любой алгоритм может обойтись без очереди, списка, коллекции, массива или системы организованных объектов, но без памяти и стека не работает ничего, в том числе все перечисленное.

На заре начала: процессор, память и стек

Идеальная память обеспечивает адресацию прямо к значению - это уровни машины и языка высокой степени. В первом случае процессор последовательно перебирает адреса памяти и выполняет команды. Во втором случае программист манипулирует массивами. В обоих эпизодах есть:

адрес = значение;
индекс = значение.

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

Стопка тарелок - традиционная новелла о сути стека: понятие stack и перевод в общебытовом сознании. Нельзя взять тарелку снизу, можно брать только сверху, и тогда все тарелки будут целы.

Все, что последним приходит в стек, уходит первым. Идеальное решение. По сути, stack, как перевод одного действия в другое, трансформирует представления об алгоритме как последовательности операций.

Суть и понятие стека

Процессор и память - основные конструктивные элементы компьютера. Процессор исполняет команды, манипулирует адресами памяти, извлекает и изменяет значения по этим адресам. На языке программирования все это трансформируется в переменные и их значения. Суть стека и понятие last in first out (LIFO) остается неизменным.

Аббревиатура LIFO уже не используется так часто, как раньше. Вероятно потому, что списки трансформировались в объекты, а очереди first in first out (FIFO) применяются по мере необходимости. Динамика типов данных потеряла свою актуальность в контексте описания переменных, но приобрела свою значимость на момент исполнения выражений: тип данного определяется в момент его использования, а до этого момента можно описывать что угодно и как угодно.

Так, стек - что это такое? Теперь вы знаете, что это вопрос неуместный. Ведь без стека нет современного программирования. Любой вызов функции - это передача параметров и адреса возврата. Функция может вызвать другую функцию - это опять передача параметров и адреса возврата. Наладить механизм вызова значений без стека - это лишняя работа, хотя достижимое решение, безусловно, возможное.

Многие спрашивают: "Стек - что это такое?". В контексте вызова функции он состоит из трех действий:

сохранения адреса возврата;
сохранения всех передаваемых переменных или адреса на них;
вызова функции.

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

Свойства стека

Стек - это не абстрактный тип данных, а реальный механизм. На уровне процессора - это «движок», который уточняет и дополняет работу основного цикла процессора. Как битовая арифметика, стек фиксирует простые и очевидные правила работы. Это надежно и безопасно.

Характерные свойства стека - это его размер и длина элементов. На уровне процессора все определяется разрядностью, адресацией памяти и физикой доступа к ней. Интересная особенность и традиция: стек растет вниз, то есть в сторону уменьшения адресов памяти, а память программ и данных - вверх. Это обычно, но не обязательно. Здесь важен смысл - пришел последним, а ушел первым. Это удивительно простое правило позволяет строить интересные алгоритмы работы прежде всего на языках высокого уровня. Теперь вы не будете спрашивать, стек - что это такое.

Безукоризненная работа аппаратного обеспечения уже очень давно является нормой, но на передовом крае информационных технологий идея стека обретает новые и перспективные применения.

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

Массивы, коллекции, списки, очереди... Стек!

Часто люди задают вопрос: "Стек - что это такое?". "Программирование" и "систематизация" - интересные понятия: они не синонимы, но так тесно связаны. Программирование прошло очень быстро такой длительный путь, что достигнутые вершины кажутся идеальными. Скорее всего, это не так. Но очевидно другое.

Идея стека стала привычной не только на уровне различных языков программирования, но и на уровне их конструкций и возможностей по созданию типов данных. Любой массив имеет push и pop, а понятия "первый и последний элементы массива" стали традиционными. Раньше были просто элементы массива, а сегодня есть:

элементы массива;
первый элемент массива;
последний элемент массива.

Операция помещения элемента в массив сдвигает указатель, а извлечение элемента с начала массива или с его конца имеет значение. По сути это тот же стек, но в применении к другим типам данных.

Особенно примечательно, что популярные языки программирования не имеют конструкции stack. Но они предоставляют его идею разработчику в полном объеме.

last in - first out , «последним пришёл - первым вышел»).

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

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

Энциклопедичный YouTube

1 / 3

Информатика. Структуры данных: Стек. Центр онлайн-обучения «Фоксфорд»

#9. Стек / 1. Ассемблер и процедуры / Программирование с нуля

Основы сетей передачи данных. Модель OSI и стек протоколов TCP IP. Основы Ethernet.

Субтитры

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

Организация в памяти

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

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

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

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

Пример реализации стека на языке С:

struct stack { char * data ; struct stack * next ; };

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

Возможны три операции со стеком: добавление элемента (иначе проталкивание, push ), удаление элемента (pop ) и чтение головного элемента (peek ) .

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

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

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 ]; } }

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

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

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

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

(англ. last in - first out , «последним пришёл - первым вышел»).

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

Организация в памяти

Пример реализации стека на языке С:

struct stack { char * data ; struct stack * next ; };

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

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

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

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

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

Применение стека упрощает и ускоряет работу программы, так как идет обращение к нескольким данным по одному адресу.

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

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

Примечания

Машина Тьюринга: Введение (неопр.) . Проверено 12 февраля 2013.