Стек
Стек - самая популярная и, пожалуй, самая важная структура данных в программировании. Стек представляет собой запоминающее устройство, из которого элементы извлекаются в порядке, обратном их добавлению. Это как бы неправильная очередь, в которой первым обслуживают того, кто встал в нее последним. В программистской литературе общепринятыми являются аббревиатуры, обозначающие дисциплину работы очереди и стека. Дисциплина работы очереди обозначается 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 уже вводит стековую память, устраняя недостатки ранних версий языка.
Память, которую используют программы, состоит из нескольких частей — сегментов :
сегмент кода (или «текстовый сегмент»), где находится скомпилированная программа. Сегмент кода обычно доступен только для чтения;
сегмент 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; }
Очередь
Очередь как структура данных понятна даже людям, не знакомым с программированием. Очередь содержит элементы, как бы выстроенные друг за другом в цепочку. У очереди есть начало и конец. Добавлять новые элементы можно только в конец очереди, забирать элементы можно только из начала. В отличие от обычной очереди, которую всегда можно при желании покинуть, из середины программистской очереди удалять элементы нельзя.
Очередь можно представить в виде трубки. В один конец трубки можно добавлять шарики - элементы очереди, из другого конца они извлекаются. Элементы в середине очереди, т.е. шарики внутри трубки, недоступны. Конец трубки, в который добавляются шарики, соответствует концу очереди, конец, из которого они извлекаются - началу очереди. Таким образом, концы трубки не симметричны, шарики внутри трубки движутся только в одном направлении.
В принципе, можно было бы разрешить добавлять элементы в оба конца очереди и забирать их также из обоих концов. Такая структура данных в программировании тоже существует, ее название - " дек ", от англ. 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 (которое на единицу больше, чем индекс последней ячейки массива).
Стек является общей структурой данных для представления данных, которые должны обрабатываться в определенном порядке. Например, когда функция вызывает другую функцию, которая, в свою очередь, вызывает третью функцию, важно, чтобы третья функция вернулась на вторую функцию, а не первую.
Один из способов реализации такого порядка обработки данных — это организовать своего рода очередь вызовов функций. Последняя добавленная в стек функция, будет завершена первой и наоборот, первая добавленная в стек функция будет завершена последней. Таким образом, сама структура данных обеспечивает надлежащий порядок вызовов.
Концептуально, структура данных — стек очень проста: она позволяет добавлять или удалять элементы в определенном порядке. Каждый раз, когда добавляется элемент, он попадает на вершину стека, единственный элемент, который может быть удален из стека — элемент, который находится на вершине стека. Таким образом, стек, как принято говорить, «первым пришел, последним ушел — FILO» или «последним пришел, первым ушел — LIFO». Первый элемент, добавленный в стек будет удален из него в последнюю очередь.
Так в чем же дело? Зачем нам нужны стеки? Как мы уже говорили, стеки — удобный способ организации вызовов функций. В самом деле, «стек вызовов» это термин, который часто используют для обозначения списка функций, которые сейчас либо выполняются, либо находятся в режиме ожидания возвращаемого значения других функций.
В некотором смысле, стеки являются частью фундаментального языка информатики. Когда вы хотите реализовать очередь типа — «первый пришел, последним ушел», то имеет смысл говорить о стеках с использованием общей терминологии. Кроме того, такие очереди участвуют во многих процессах, начиная от теоретических компьютерных наук, например функции push-down и многое другое.
Стеки имеют некоторые ассоциируемые методы:
- Push — добавить элемент в стек;
- Pop — удалить элемент из стека;
- Peek — просмотреть элементы стека;
- LIFO — поведение стека,
- FILO Equivalent to LIFO
Этот стек был реализован с шаблонами, чтобы его можно было использовать практически для любых типов данных. Причем размер стека определяется динамически, во время выполнения программы. В стек добавлена также дополнительная функция: peek() , которая показывает n-й элемент от вершины стека.
#ifndef STACK_H #define STACK_H #includeШаблон класса Stack реализован в отдельном *.h файле, да, именно реализован, я не ошибся. Все дело в том, что и интерфейс шаблона класса и реализация должны находиться в одном файле, иначе вы увидите список ошибок похожего содержания:
ошибка undefined reference to «метод шаблона класса»
Интерфейс шаблона класса объявлен с 9 по 28 строки. Все методы класса содержат комментарии и, на мой взгляд, описывать их работу отдельно не имеет смысла. Обратите внимание на то, что все методы шаблона класса Стек объявлены как . Это сделано для того, чтобы ускорить работу класса. Так как встроенные функции класса работают быстрее, чем внешние.
Сразу после интерфейса шаблона идет реализация методов класса Стек, строки 32 — 117. В реализации методов класса ничего сложного нет, если знать как устроен стек, шаблоны и . Заметьте, в классе есть два конструктора, первый объявлен в строках 32-33, — это конструктор по умолчанию. А вот конструктор в строках 41-5, — это конструктор копирования. Он нужен для того, чтобы скопировать один объект в другой. Метод Peek , строки 80 — 88 предоставляет возможность просматривать элементы стека. Необходимо просто ввести номер элемента, отсчет идет от вершины стека. Остальные функции являются служебными, то есть предназначены для использования внутри класса, конечно же кроме функции printStack() , она вывод элементы стека на экран.
Теперь посмотрим на драйвер для нашего стека, под драйвером я подразумеваю программу в которой тестируется работа класса. Как всегда это main функция, в которой мы и будем тестировать наш шаблон класса Stack . Смотрим код ниже:
#include
Создали объект стека, строка 9, размер стека при этом равен 5, то есть стек может поместить не более 5 элементов. Заполняем стек в , строки 13 — 17. В строке 21 выводим стек на экран, после удаляем один элемент из стека, строка 24 и снова выводим содержимое стека, поверьте оно изменилось, ровно на один элемент. Смотрим результат работы программы:
LOTR! | ! | R | T | O | L Удалим элемент из стека | R | T | O | L Сработал конструктор копирования! | R | T | O | L Второй в очереди элемент: T
В строке 28 мы воспользовались конструктором копирования, о том самом, о котором я писал выше. Не забудем про функцию peek() , давайте посмотри на второй элемент стека, строка 33.
На этом все! Стек у нас получился и исправно работает, попробуйте его протестировать, например на типе данных int . Я уверен, что все останется исправно работать.
(англ. 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.