Где используется стек. Алгоритмы и структуры данных для начинающих: стеки и очереди
В рамках данной статьи, я расскажу вам что такое стек , а так же для чего он нужен и где применяется.
Большое количество задач, связанных с информацией, поддаются типизированному решению. Поэтому нет ничего удивительного в том, что для многих из них уже давно придуманы методы, термины и описания. Например, нередко можно услышать такие слово, как стек. Звучит весьма сложно, однако все существенно проще.
Стек (stack) - это метод представления однотипных данных (можно просто называть типом) в порядке LIFO (Last In - First Out, что означает "первый вошел - последний вышел"). Стоит упомянуть, что в русской технике его так же называют "магазином". И речь тут не о продуктовом магазине, а о рожке с патронами для оружия, так как принцип весьма схож - первый вставленный патрон будет использован последним.
Примечание : Стоит знать, что у этого слова могут быть и другие значения. Поэтому если речь не касается компьютеров, то имеет смысл уточнить.
Чтобы лучше понять, приведу жизненный пример. Допустим у вас есть стопка листов. Каждый исписанный лист вы кладете рядом, а каждый следующий поверх остальных. Чтобы достать к примеру, самый первый лист из полученной стопки, вам необходимо вытащить все остальные листы. Вот по этому же самому принципу и устроен stack. То есть, каждый последний добавленный элемент становится верхним и чтобы достать, к примеру, самый первый элемент необходимо вытащить все остальные.
Для чего нужен стек? Основное предназначение это решение типовых задач, где необходимо поддерживать последовательность состояний чего-либо или где нужно инверсионное представление данных (то есть в обратную сторону).
В компьютерной сфере стек используется в аппаратных устройствах (например, процессоре), в операционной системе и многих программах. Если рассматривать пример, с которым знаком практически каждый, кто занимался программированием, то без стека не была бы возможна рекурсия, ведь при каждом повторном входе в функцию нужно сохранять текущее состояние на вершине, а при каждом выходе из функции быстро восстанавливать это состояния (то есть, как раз последовательность LIFO). А если копнуть еще глубже, то в принципе весь подход к запуску и выполнению программ устроен на принципе стека, где прежде чем следующая программа, запущенная из основной, будет выполняться, состояние предыдущей заносится в стек, чтобы когда запущенное приложение или подпрограмма закончила выполняться, предыдущая программа нормально продолжила выполняться с места остановки.
Какие операции у stack? Основных операций всего две:
1. Добавление элемента в вершину стека называется push
2. Извлечения верхнего элемента называется pop
Но, так же периодически можно встретить реализацию операции чтения верхнего элемента без его извлечения - называется peek .
Как организуется стек? Обычно стек реализуется двумя вариантами:
1. С помощью массива и переменной, которая указывает на ячейку с вершиной стека
2. С помощью связанных списков
У каждого из этих 2-х вариантов есть свои плюсы и минусы. Например, связанные списки более безопасны в плане применения, так как каждый добавляемый элемент помещается в динамически созданную структуру (нет проблем с количеством элементов - нет дырок безопасности, позволяющих свободно перемещаться в памяти программы). Однако, в плане хранения и быстроты использования они менее эффективны (требуют дополнительное место для хранения указателей; разбросаны в памяти, а не расположены друг за другом, как в массивах).
Теперь, вы знаете что такое стек, а так же зачем он нужен и для чего применяется.
Память, которую используют программы, состоит из нескольких частей — сегментов :
сегмент кода (или «текстовый сегмент»), где находится скомпилированная программа. Сегмент кода обычно доступен только для чтения;
сегмент bss (или «неинициализированный сегмент данных»), где хранятся глобальные и , инициализированные нулем;
сегмент данных (или «сегмент инициализированных данных»), где хранятся инициализированные глобальные и статические переменные;
к уча (heap), откуда выделяются динамические переменные;
стек вызовов , где хранятся , локальные переменные и другая информация, связанная с функциями.
В этом уроке мы рассмотрим только кучу и стек, поскольку всё самое интересное происходит именно там.
Куча
Сегмент кучи (или просто «куча ») отслеживает память, используемую для динамического выделения. Мы уже немного поговорили о куче в .
В C++, при использовании оператора new для выделения динамической памяти, эта память выделяется в сегменте кучи самого приложения.
int *ptr = new int; // ptr выделяется 4 байта из кучи int *array = new int; // array выделяется 40 байтов из кучи
Адрес выделяемой памяти передается обратно оператором new и затем он может быть сохранен в . О механизме хранения и выделения свободной памяти нам сейчас беспокоиться не за чем. Однако стоит знать, что последовательные запросы памяти не всегда приводят к выделению последовательных адресов памяти!
int *ptr1 = new int; int *ptr2 = new int; // ptr1 и ptr2 могут не иметь последовательных адресов
При удалении динамически выделенной переменной, память возвращается обратно в кучу и затем может быть переназначена (исходя из последующих запросов). Помните, что удаление указателя не удаляет переменную, это просто приводит к возврату памяти по этому адресу обратно в операционную систему.
Куча имеет свои преимущества и недостатки:
Выделение памяти в куче сравнительно медленное.
Выделенная память остается выделенной до тех пор, пока не будет освобождена (остерегайтесь утечек памяти) или пока приложение не завершит своё выполнение (в этот момент ОС должна вернуть память обратно).
Доступ к динамически выделенной памяти осуществляется только через указатель. Разыменование указателя происходит медленнее, чем доступ к переменной напрямую.
Поскольку куча представляет собой большой резервуар памяти, то именно она используется для выделения больших , или классов.
Стек вызовов
Стек вызовов (или просто «стек ») имеет гораздо более интересную роль. Стек вызовов отслеживает все активные функции (те, которые были вызваны, но еще не завершены) от начала программы и до текущей точки выполнения, и обрабатывает выделение всех параметров функции и локальных переменных.
Стек вызовов реализуется как структура данных «Стек». Поэтому, прежде чем мы поговорим о том, как работает стек вызовов, нам нужно понять, что такое «Стек» как структура данных.
Структура данных «Стек»
Структура данных - это механизм в программировании для организации данных, чтобы они могли эффективно использоваться. Вы уже видели несколько типов структур данных, таких как массивы и структуры. Они обеспечивают механизмы для эффективного хранения данных и доступа к ним. Существует еще много дополнительных структур данных, которые обычно используются в программировании, некоторые из которых реализованы в стандартной библиотеке C++, и «Стек» является одним из таких.
Рассмотрим стопку (стек) тарелок на столе. Поскольку каждая тарелка тяжелая и они сложены (друг на друге), то вы можете сделать только одну из следующих трех вещей:
Посмотреть на поверхность верхней тарелки.
Взять верхнюю тарелку из стопки (открывая таким образом следующую, которая находится снизу – если она вообще есть).
Положить новую тарелку поверх стопки (спрятав под ней самую верхнюю тарелку — если она была).
В компьютерном программировании стек представляет собой контейнер, как структуру данных, который содержит несколько переменных (подобно массиву). Однако, в то время как массив позволяет получить доступ и изменять элементы в любом порядке (так называемый «произвольный доступ »), то стек более ограничен. Операции, которые могут выполняться в стеке, соответствуют трем перечисленным выше. В стеке вы можете :
Посмотреть на верхний элемент в стеке (используется функция top () или peek () ).
Вытянуть верхний элемент стека (используется функция pop () ).
Добавить новый элемент на вершину стека (используется функция push () ).
Стек – это структура типа LIFO (Last In, First Out – последним пришёл, первым ушёл). Последний элемент, помещенный на вершину стека, будет первым, который и выйдет из стека. Если вы положите новую тарелку поверх стопки других тарелок, то она будет первой, которую вы потом возьмете. По мере того, как элементы помещаются в стек — стек растет, по мере того, как элементы удаляются со стека – стек уменьшается.
Например, рассмотрим короткую последовательность, показывающую, как работает добавление и удаление в стеке:
Stack: empty
Push 1
Stack: 1
Push 2
Stack: 1 2
Push 3
Stack: 1 2 3
Push 4
Stack: 1 2 3 4
Pop
Stack: 1 2 3
Pop
Stack: 1 2
Pop
Stack: 1
Стопка тарелок – довольно-таки хорошая аналогия работы стека, но есть аналогия и получше. Например, рассмотрим несколько почтовых ящиков, которые расположены друг на друге. Каждый почтовый ящик может содержать только один элемент, и все почтовые ящики изначально пустые. Кроме того, каждый почтовый ящик прибивается гвоздем к почтовому ящику снизу, поэтому количество почтовых ящиков не может быть изменено. Если мы не можем изменить количество почтовых ящиков, то как мы получим поведение, подобное стеку?
Во-первых, мы используем наклейку для обозначения того, где находится самый нижний пустой почтовый ящик. В начале это будет первый почтовый ящик, который находится на полу. Когда мы добавим элемент в наш стек почтовых ящиков, то мы поместим этот элемент в почтовый ящик, на котором будет наклейка (т.е. в самый первый пустой почтовый ящик на полу), и затем переместим наклейку на один почтовый ящик выше. Когда мы вытаскиваем элемент из стека, то мы перемещаем наклейку на один почтовый ящик ниже и удаляем элемент из почтового ящика. Всё, что находится ниже маркера — находится в стеке. Всё, что находится в ящике с наклейкой и выше – не находится в стеке.
Сегмент стека вызовов
Сегмент стека вызовов содержит память, используемую для стека вызовов. При запуске приложения, функция main() помещается в стек вызовов операционной системой. Затем программа начинает своё выполнение.
Когда программа встречает вызов функции, то эта функция помещается в стек вызовов. При завершении выполнения функции, она удаляется из стека вызовов. Таким образом, просматривая функции, добавленные в стек, мы можем видеть все функции, которые были вызваны до текущей точки выполнения.
Наша аналогия с почтовыми ящиками – это действительно то, как работает стек вызовов. Стек вызовов имеет фиксированное количество адресов памяти (фиксированный размер). Почтовые ящики являются адресами памяти, а «элементы», которые мы добавляем и вытягиваем в стеке, называются фреймами (или еще «кадрами ») стека. Кадр стека отслеживает все данные, связанные с одним вызовом функции. «Наклейка» — это регистр (небольшая часть памяти в ЦП), который является указателем стека . Указатель стека отслеживает, где находится вершина стека вызовов.
Единственное отличие фактического стека вызовов от нашего гипотетического стека почтовых ящиков заключается в том, что, когда мы вытягиваем элемент из стека вызовов, то нам не нужно очищать память (т.е. вынимать всё содержимое из почтового ящика). Мы можем просто оставить эту память для следующего элемента, который и перезапишет её. Поскольку указатель стека будет ниже этого адреса памяти, то, как мы уже знаем, эта ячейка памяти не будет находится в стеке.
Стек вызовов на практике
Давайте рассмотрим более подробно, как работает стек вызовов. Ниже приведена последовательность шагов, выполняемых при вызове функции :
Программа сталкивается с вызовом функции.
Фрейм стека создается и помещается в стек, он состоит из:
Адреса инструкции, который находится за вызовом функции (так называемый «обратный адрес »). Так процессор запоминает, куда возвращаться после выполнения функции.
Аргументов функции.
Памяти для локальных переменных.
Сохраненных копий всех регистров, модифицированных функцией, которые необходимо будет восстановить после того, как функция завершит своё выполнение.
Процессор переходит к точке начала выполнения функции.
Инструкции внутри функции начинают выполняться.
После завершения функции, выполняются следующие шаги :
Регистры восстанавливаются из стека вызовов.
Фрейм стека вытягивается из стека. Освобождается память всех локальных переменных и аргументов.
Обрабатывается возвращаемое значение.
ЦП возобновляет выполнение кода (исходя из обратного адреса).
Возвращаемые значения могут обрабатываться разными способами, в зависимости от архитектуры компьютера. Некоторые архитектуры считают возвращаемое значение частью фрейма стека. Другие используют регистры процессора.
Знать все детали работы стека вызовов не так уж и важно. Однако понимание того, что функции при вызове добавляются в стек, а при завершении выполнения – удаляются из стека, даёт основы, необходимые для понимания рекурсии, а также некоторых других концепций, которые полезны при .
Пример стека вызовов
Рассмотрим следующий фрагмент кода:
Стек вызовов этой программы выглядит следующим образом:
boo() (включая параметр b)
main()
Переполнение стека
Стек имеет ограниченный размер и, следовательно, может содержать только ограниченный объем информации. В Windows размер стека по умолчанию составляет 1 МБ. На некоторых других Unix-системах этот размер может достигать и 8 МБ. Если программа пытается поместить слишком много информации в стек, то это приведет к переполнению стека. Переполнение стека (stack overflow) происходит при запросе на память, в то время, когда вся память стека уже выделена — в этом случае все запросы на выделения начнут переливаться (переполняться) в другие разделы памяти.
Переполнение стека является результатом добавления слишком большого числа переменных в стек и/или создания слишком большого количества вложенных вызовов функций (например, где функция A вызывает функцию B, которая в свою очередь вызывает функцию C, а та вызывает функцию D и т.д. и т.п.). Переполнение стека обычно приводит к сбою в программе.
Например:
int main() { int stack; return 0; }
int main () int stack [ 100000000 ] ; return 0 ; |
Эта программа пытается добавить огромный массив в стек вызовов. Поскольку размера стека недостаточно для обработки такого массива, то его добавление переходит и на другие части памяти, которые программа использовать не может. Следовательно, получаем сбой.
Вот еще одна программа, которая вызовет переполнение стека, но уже по другой причине:
void boo() { boo(); } int main() { boo(); return 0; }
При освоении программирования, рано или поздно, возникает вопрос: "Что такое стек?
".
Наиболее наглядным способом объяснения я считаю программу на языке ассемблера (не пугайтесь), которая просто добавляет данные в стек.
Стек - это структура данных присущая всей программируемой технике. Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю. Часто стек называют магазином - по аналогии с магазином в огнестрельном оружии (стрельба начнётся с патрона, заряженного последним).
Зачем все это нужно?
Вы вряд ли сможете написать программу, которая не будет использовать функции (подпрограммы). При вызове функции в стек копируется адрес для возврата после окончания выполнения данной подпрограммы. По окончании её выполнения адрес возвращается из стека в счетчик команд и программа продолжает выполняться с места после функции.
Также в стек необходимо помещать регистры, которые используются в данной подпрограмме (в языках высокого уровня этим занимается компилятор).
Все вышесказанное характерно для так называемого аппаратного стека. Надеюсь вы догадываетесь, что такая структура данных (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 (которое на единицу больше, чем индекс последней ячейки массива).
(англ. last in - first out , «последним пришёл - первым вышел»).
Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.
В некоторых языках (например, Lisp , Python ) стеком можно назвать любой список, так как для них доступны операции pop и push. В языке C++ стандартная библиотека имеет класс с реализованной структурой и методами . И т. д.
Программный стек
Организация в памяти
Зачастую стек реализуется в виде однонаправленного списка (каждый элемент в списке содержит помимо хранимой информации в стеке указатель на следующий элемент стека).
Но также часто стек располагается в одномерном массиве с упорядоченными адресами. Такая организация стека удобна, если элемент информации занимает в памяти фиксированное количество слов, например, 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 ]; } }
Область применения
Программный вид стека используется для обхода структур данных , например, дерево или граф . При использовании рекурсивных функций также будет применяться стек, но аппаратный его вид. Кроме этих назначений, стек используется для организации стековой машины , реализующей вычисления в обратной польской записи .
Для отслеживания точек возврата из подпрограмм используется стек вызовов.
Идея стека используется в стековой машине среди стековых языков программирования .
Применение стека упрощает и ускоряет работу программы, так как идет обращение к нескольким данным по одному адресу.
Аппаратный стек
До использования стека он должен быть инициализирован так, чтобы регистры SS:ESP указывали на адрес головы стека в области физической оперативной памяти, причём под хранение данных в стеке необходимо зарезервировать нужное количество ячеек памяти (очевидно, что стек в ПЗУ , естественно, не может быть организован). Прикладные программы, как правило, от операционной системы получают готовый к употреблению стек. В защищённом режиме работы процессора сегмент состояния задачи содержит четыре селектора сегментов стека (для разных уровней привилегий), но в каждый момент используется только один стек .
Примечания
- Машина Тьюринга: Введение (неопр.) . Проверено 12 февраля 2013.