Что такое куча и стек

Что такое куча

В программировании есть два разных понятия, которые обозначаются одним и тем же словом «куча». Одно про выделение памяти, второе — про организацию данных. Разберём оба и закроем этот вопрос.

Это про данные

Эта статья из цикла про типы данных. Уже было:

Ещё бывают связанные списки, очереди, множества, хеш-таблицы, карты и кучи. Вот сегодня про кучи.

Куча и работа с памятью

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

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

То, как программист распорядится этой памятью и каким образом будет с ней работать, влияет на быстродействие и работоспособность всей программы.

Аналогия со стройплощадкой

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

На стройке: мы выгрузили кирпич на один участок, использовали этот кирпич. Теперь нужно сказать, что этот участок можно снова использовать под стройматериалы. Новый кирпич можно разгрузить сюда же, а не искать новое место на площадке.

В программе: мы выделили память для переменной, использовали переменную, она больше не нужна. Можно сказать «Эта память свободна» и использовать её снова.

На стройке: мы храним определённый вид труб на палете №53. Мы говорим крановщику: «Поднимайте на этаж то, что лежит на палете 53». Если мы ошибёмся с номером, то крановщик поднимет на этаж не те трубы.

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

�� Прямой доступ к памяти есть не во всех языках программирования. Многие компиляторы и интерпретаторы ставят между программистом и памятью своеобразного администратора — диспетчера памяти. Он сам решает, какие переменные нужны, а какие нет; когда чистить память; сколько памяти на что выделить.

С одной стороны, это удобно: программист просто говорит «храни данные». А где они будут храниться и как их получить — это вопрос другой системы.

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

Куча и организация данных

Второй вид кучи в программировании — это организация данных.

Куча — это такой вид дерева, у которого есть одно важное свойство:

если узел A — это родитель узла B, то ключ узла A больше ключа узла B (или равен ему).

Если мы представим какой-то набор данных в виде кучи, он может выглядеть, например, так:

Что такое куча

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

Для чего нужны кучи данных

Так как данные в куче упорядочены заранее понятным образом, то их можно использовать для быстрого нахождения нужного элемента или оптимальной последовательности действий, например:

для пирамидальной сортировки большого количества данных, когда объём требуемой памяти не зависит от размера массива, который мы сортируем;
для нахождения самого быстрого пути из точки A в точку B, когда мы знаем промежуточные расстояния между ними и точками по пути;
для поиска нужного элемента по каким-то критериям за минимальное время;
для вычисления оптимальной последовательности действий, если мы знаем параметры и условия для каждого действия.

Зачем это знать

Если вы просто пишете веб-приложения на JS — в принципе, это знать не нужно. Вы не можете из JS напрямую управлять памятью, а для простых задач вам вряд ли придётся часто обходить деревья и делать сложные сортировки.

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

Основы памяти в Java: Куча и Стек

Узнайте, как устроена память в Java: разбор работы Java-стека и кучи, особенностей управления памятью и роли сборщика мусора в данном процессе.

2 авг. 2023 · 7 минуты на чтение

Мы всё активнее применяем современные языки программирования, обеспечивающие нам возможность писать минимум кода для решения проблем. Возьмём за пример Java: он был разработан с целью максимального упрощения жизни программистов. Вам не приходится заботиться о памяти — ваши мысли целиком направлены на решение бизнес-задач. Однако это облегчение имеет свою цену.

В прошлой статье, мы обсудили общее устройство памяти в компьютере. А в этой статье мы сосредоточимся на том, как язык Java работает с памятью. Это включает в себя обзор стека и кучи в контексте Java, а также их отличия от общего представления. Мы также немного обсудим роль сборщика мусора в управлении памятью.

В данной статье не разбирается JMM. Углубиться в эту тему вы можете ознакомившись с дополнительными материалами в конце статьи.

Спонсор поста

Устройство памяти в программировании

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

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

Стек (Stack)

Стек — это область памяти, где функции хранят свои переменные и информацию для выполнения. Представьте стек как физическую стопку подносов в ресторане: вы можете добавить поднос сверху (push) или взять верхний поднос (pop). Аналогично, когда функция вызывается, ее локальные переменные и информация о вызове кладутся на стек сверху, и забираются сверху (уничтожаются), когда функция завершает работу.

Стек обеспечивает быстрый доступ к данным и автоматическое управление памятью, но имеет ограниченный размер. Если ваша программа использует больше стековой памяти, чем доступно, программа может завершиться с ошибкой переполнения стека.

Куча (Heap)

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

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

Для удобства визуализируем стек и кучу. Серые объекты потеряли свою ссылку из стека, их необходимо удалить, чтобы освободить память для новых объектов.

Объект может содержать методы, и эти методы могут содержать локальные переменные. Эти локальные переменные также хранятся в стеке потоков, даже если объект, которому принадлежит метод, хранится в куче.

Стек

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

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

Синхронизация в Java служит для контроля доступа нескольких потоков к общим ресурсам. Синхронизация может быть реализована с использованием ключевого слова synchronized или специальных классов, таких как ReentrantLock или Semaphore .

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

Заключение

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

В случае с Java, управление памятью становится еще более интересным благодаря сборщику мусора, который автоматически освобождает неиспользуемую память, и разделению памяти на Heap Space и Stack Space. Эти особенности делают язык Java удобным для работы, но также требуют осознанного использования памяти для предотвращения проблем с производительностью.

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

Дополнительные материалы

Habr: Глубокое погружение в Java Memory Model
Habr: Откуда растут ноги у Java Memory Model

11.8 – Стек и куча

Память, которую использует программа, обычно делится на несколько разных областей, называемых сегментами:

Сегмент кода (также называемый текстовым сегментом), в котором скомпилированная программа находится в памяти. Сегмент кода обычно доступен только для чтения.
Сегмент bss («block started by symbol», также называемый сегментом неинициализированных данных), где хранятся глобальные и статические переменные с нулевой инициализацией.
Сегмент данных (также называемый сегментом инициализированных данных), где хранятся инициализированные глобальные и статические переменные.
Куча, где размещаются динамически размещаемые переменные.
Стек вызовов, в котором хранятся параметры функций, локальные переменные и другая информация, относящаяся к функциям.

В этом уроке мы сосредоточимся в первую очередь на куче и стеке, так как именно там происходит большинство интересных вещей.

Сегмент кучи

Сегмент кучи (также известный как «free store», «свободное хранилище») отслеживает память, используемую для динамического распределения памяти. Мы уже говорили немного о куче в уроке «10.13 – Динамическое распределение памяти с помощью new и delete », поэтому это будет резюме.

В C++, когда вы используете оператор new для выделения памяти, эта память выделяется в сегменте кучи приложения.

int *ptr = new int; // ptr присваивается 4 байта в куче int *array = new int[10]; // array присвоено 40 байт в куче

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

int *ptr1 = new int; int *ptr2 = new int; // ptr1 и ptr2 могут не содержать соседних адресов

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

У кучи есть достоинства и недостатки:

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

Стек вызовов

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

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

Структура данных стек

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

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

посмотреть на поверхность верхней тарелки;
снять верхнюю тарелку со стопки (открывая нижнюю, если она есть);
поместить новую тарелку на верх стопки (скрывая нижнюю, если она есть).

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

посмотреть верхний элемент в стеке (обычно это делается с помощью функции top() , но иногда называется peek() );
снять верхний элемент из стека (выполняется с помощью функции pop() );
поместить новый элемент на верх стека (выполняется с помощью функции push() ).

Стек – это структура типа «последним пришел – первым ушел» (LIFO, «last-in, first-out»). Последний элемент, помещенный в стек, будет первым извлеченным элементом. Если вы положите новую тарелку поверх стопки, первая тарелка, удаленная из стопки, будет тарелкой, которую вы только что положили последней. Последней положена, первой снята. По мере того, как элементы помещаются в стек, стек становится больше – по мере того, как элементы извлекаются, стек становится меньше.

Например, вот короткая последовательность, показывающая, как работает стек при вставке (push) и извлечении (pop) данных:

Стек: пустой Вставка 1 Стек: 1 Вставка 2 Стек: 1 2 Вставка 3 Стек: 1 2 3 Извлечение Стек: 1 2 Извлечение Стек: 1

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

Во-первых, мы используем маркер (например, наклейку), чтобы отслеживать, где находится самый нижний пустой почтовый ящик. Вначале это будет самый нижний почтовый ящик (внизу стопки). Когда мы помещаем элемент в наш стек почтовых ящиков, мы помещаем его в отмеченный почтовый ящик (который является первым пустым почтовым ящиком) и перемещаем маркер на один ящик вверх. Когда мы извлекаем элемент из стека, мы перемещаем маркер на один почтовый ящик вниз так, чтобы он указывал на верхний непустой почтовый ящик, и удаляем элемент из этого почтового ящика. Всё, что ниже маркера, считается «в стеке». Всё, что находится на уровне маркера или над ним, – не в стеке.

Сегмент стека вызовов

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

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

Приведенная выше аналогия с почтовыми ящиками в значительной степени похожа на то, как работает стек вызовов. Сам стек представляет собой блок адресов памяти фиксированного размера. Почтовые ящики – это адреса памяти, а «элементы», которые мы помещаем в стек, называются кадрами (фреймами) стека. Кадр стека отслеживает все данные, связанные с одним вызовом функции. Мы поговорим о стековых кадрах чуть позже. «Маркер» – это регистр (небольшой фрагмент памяти в CPU), известный как указатель стека (иногда сокращенно «SP», «stack pointer»). Указатель стека отслеживает текущее положение вершины стека вызовов.

Мы можем сделать еще одну оптимизацию: когда мы извлекаем элемент из стека вызовов, нам нужно только переместить указатель стека вниз – нам не нужно очищать или обнулять память, используемую извлекаемым кадром стека (эквивалент опустошению почтового ящика). Эта память больше не считается «в стеке» (указатель стека будет по этому адресу или ниже), поэтому к ней не будет доступа. Если мы позже поместим новый кадр стека в ту же самую память, он перезапишет старое значение, которое мы никогда не очищали.

Стек вызовов в действии

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

Программа обнаруживает вызов функции.
Кадр стека создается и помещается в стек. Кадр стека состоит из:
- Адрес инструкции, следующей после вызова функции (называемый адресом возврата). Таким образом, CPU запоминает, куда вернуться после выхода из вызываемой функции.
- Все аргументы функции.
- Память для любых локальных переменных.
- Сохраненные копии любых регистров, измененных функцией, которые необходимо восстановить после возврата из функции.
CPU переходит к начальной точке функции.
Инструкции внутри функции начинают выполняться.

Когда функция завершается, происходят следующие шаги:

Регистры восстанавливаются из стека вызовов
Кадр стека извлекается из стека. Это освобождает память для всех локальных переменных и аргументов.
Обрабатывается возвращаемое значение.
CPU возобновляет выполнение по адресу возврата.

Возвращаемые значения могут обрабатываться разными способами в зависимости от архитектуры компьютера. Некоторые архитектуры включают возвращаемое значение как часть кадра стека. Другие используют регистры CPU.

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

Техническое примечание: на некоторых архитектурах стек вызовов при увеличении изменяет адрес памяти в направлении от нуля. На других он при увеличении изменяет адрес в направлении нуля. Как следствие, новые добавленные кадры стека могут иметь более высокий или более низкий адрес памяти, чем предыдущие.

Пример стека вызовов

Рассмотрим следующее простое приложение:

int foo(int x) < // b return x; >// здесь foo извлекается из стека вызовов int main() < // a foo(5); // здесь foo помещается в стек вызовов // c return 0; >

Стек вызовов в отмеченных точках выглядит следующим образом:

main()

foo() (включая параметр x) main()

main()

Переполнение стека

Стек имеет ограниченный размер и, следовательно, может содержать только ограниченный объем информации. В Windows размер стека по умолчанию составляет 1 МБ. На некоторых Unix-машинах он может достигать 8 МБ. Если программа попытается поместить в стек слишком много информации, произойдет переполнение стека. Переполнение стека происходит, когда вся память в стеке была выделена – в этом случае дальнейшие размещения начинают переполняться в другие разделы памяти.

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

Вот пример программы, которая может вызвать переполнение стека. Вы можете запустить его на своей системе и посмотреть, как она завершится со сбоем:

#include int main()

Эта программа пытается разместить в стеке огромный массив (примерно 40 МБ). Поскольку стек недостаточно велик для обработки этого массива, размещение массива переполняется в части памяти, которые программе не разрешено использовать.

В Windows (Visual Studio) эта программа дает следующий результат:

HelloWorld.exe (process 15916) exited with code -1073741571.

-1073741571 – это c0000005 в шестнадцатеричном формате, что представляет собой код ОС Windows для нарушения прав доступа. Обратите внимание, что «hi» никогда не печатается, потому что программа завершается до этого момента.

Вот еще одна программа, которая вызовет переполнение стека, но по другой причине:

void foo() < foo(); >int main()

В приведенной выше программе кадр стека помещается в стек каждый раз, когда вызывается функция foo() . Поскольку foo() вызывает себя бесконечно, в конечном итоге в стеке закончится память и произойдет переполнение.

У стека есть достоинства и недостатки:

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

Урок №105. Стек и Куча

Память, которую используют программы, состоит из нескольких частей — сегментов:

Сегмент кода (или «текстовый сегмент»), где находится скомпилированная программа. Обычно доступен только для чтения.

Сегмент bss (или «неинициализированный сегмент данных»), где хранятся глобальные и статические переменные, инициализированные нулем.

Сегмент данных (или «сегмент инициализированных данных»), где хранятся инициализированные глобальные и статические переменные.

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

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

Куча

Сегмент кучи (или просто «куча») отслеживает память, используемую для динамического выделения. Мы уже немного поговорили о куче на уроке о динамическом выделении памяти в языке С++.

В языке C++ при использовании оператора new динамическая память выделяется из сегмента кучи самой программы:

int * ptr = new int ; // для ptr выделяется 4 байта из кучи
int * array = new int [ 10 ] ; // для 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() помещается в стек вызовов операционной системой. Затем программа начинает свое выполнение.

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

Наша аналогия с почтовыми ящиками — это действительно то, как работает стек вызовов. Стек вызовов имеет фиксированное количество адресов памяти (фиксированный размер). Почтовые ящики являются адресами памяти, а «элементы», которые мы добавляем или вытягиваем из стека, называются фреймами (или «кадрами») стека. Кадр стека отслеживает все данные, связанные с одним вызовом функции. «Наклейка» — это регистр (небольшая часть памяти в ЦП), который является указателем стека. Указатель стека отслеживает вершину стека вызовов.

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

Стек вызовов на практике

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

Программа сталкивается с вызовом функции.

Создается фрейм стека, который помещается в стек. Он состоит из:

адреса инструкции, который находится за вызовом функции (так называемый «обратный адрес»). Так процессор запоминает, куда ему возвращаться после выполнения функции;

памяти для локальных переменных;

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

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

Инструкции внутри функции начинают выполняться.

После завершения функции, выполняются следующие шаги:

Регистры восстанавливаются из стека вызовов.

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

Обрабатывается возвращаемое значение.

ЦП возобновляет выполнение кода (исходя из обратного адреса).

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

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

Пример стека вызовов

Рассмотрим следующий фрагмент кода:

Что такое куча и стек