Стек – это вот:
Серьезно.
А теперь в подробностях. Когда я писал о том, что функция вызывается, или данные передаются в функцию, то умышленно упускал из виду один момент.
Например, когда вызывается функция, то процессор перепрыгивает с текущего адреса, на которым он находится, на адрес функции. И выполнение программы продолжается с того адреса. После того, как функция закончила работу, процессор возвращается на тот адрес, откуда он ушел. А тут надо было пояснить – а откуда процессор знает, куда ему возвращаться? Ведь функцию можно вызвать из любого места, и возврат, стало быть, должен происходить именно в то место, откуда вызвали.
Второй момент: когда в функцию передаются параметры, то они записываются в специальную область памяти, где их может найти функция. Где находится эта область памяти? И откуда функция знает, к какому адресу в этой области обращаться? Допустим, мы записали 2 параметра по адресам 100 и 102, и вызвали функцию. Допустим, она знает, что нужно искать параметры по адресам 100 и 100. Но если она вызовет другую функцию и тоже передаст ей параметры, то куда должна смотреть другая? А если та другая снова вызовет первую? Параметры, которые мы передаем, перезапишутся поверх адресов 100 и 102, или что с ними произойдет?
Все эти вопросы решаются с помощью стека. Стек – это действительно просто некая область памяти. Где она находится – неважно, потому что она, как правило, выделяется операционной системой. Но чтобы ею пользоваться, нам (а точнее процессору) доступен указатель на эту область памяти.
Так как это просто память, а не механическое устройство (как на картинке выше), то доступ к ней произволен: можно записывать и читать любые данные со смещением относительно начала стека. Однако стеком так не пользуются. Если им так пользоваться, то он перестанет быть стеком и станет просто памятью.
Стеком его делают две операции: push (запихнуть) и pop (выпихнуть). Стек происходит от слова stack, то есть "складывать в стопку". Посмотрите еще раз на картинку.
Указатель стека всегда показывает на самый верхний элемент в стопке, то есть на тот, который был запихнут последним. Если запихнуть сверху еще один элемент, то указатель стека сдвинется и будет показывать на него.
Если вы начнете выпихивать элементы из стека, то первым будет выпихнут тот, который находится на самом верху. Указатель сместится и начнет показывать на тот элемент, который был ниже. Вы не можете выпихнуть из стека любой элемент. Вы должны сначала выпихнуть все элементы, которые находятся выше него.
Этот принцип называется LIFO (Last In, First Out), или "последним зашел – первым вышел".
Что же нам даёт стек? А вот что:
Когда происходит вызов функции, то процессор запихивает текущий адрес в стек и идет на адрес функции. Когда нужно вернуться из функции, процессор выпихивает адрес из стека и продолжает выполнение с него. Таким образом, функцию можно вызвать из любого места программы, и потом вернуться в это же место. Проблема решена.
Также обратите внимание, что если функция №1 вызовет внутри себя функцию №2, то текущий адрес опять будет запихнут в стек, и будет совершен переход на функцию №2. Но мы все ещё не вернулись из функции №1. Теперь в стеке будут лежать два адреса. Когда произойдет возврат из функции №2, из стека выпихнется последний сохраненный адрес и функция №1 продолжит выполнение.
Вы можете сколько угодно вызывать функции внутри функций (пока хватит размера стека), и каждый раз текущий адрес будет сохраняться в стек, чтобы потом продолжить с этого адреса. Сохраненные адреса не путаются между собой. Во-первых, их будет ровно столько, сколько было вызвано функций. Во-вторых, возврат по этим адресам будет осуществляться в обратном порядке, то есть где был самый последний вызов – на тот адрес первым и возвращаемся.
Теперь насчет передачи параметров в функцию. Они также передаются через стек. Нужно вам, скажем передать параметры x0, y0, x1, y1 в функцию drawRectangle(), вы просто пишете:
drawRectangle(x0, y0, x1, y1);
А что происходит на самом деле:
push y1
push x1
push y0
push x0
call drawRectangle
То есть всё, что записано в скобках, запихивается в стек, это 4 числа: x0, y0, x1, y1, плюс текущий адрес, на который надо вернуться.
(* см. комментарии от HardDev) Обратите внимание, что в стек параметры x0, x1, y0, y1 попали в обратном порядке. Почему? Да потому что "последним зашел – первым вышел".
Когда мы попадаем в функцию drawRectangle(), она уже в курсе, что в стеке лежат параметры, которые ей нужны.
Но она не может просто выпихнуть их, потому что последним в стеке лежит адрес, на который надо вернуться, и его трогать нельзя. Поэтому она пользуется указателем стека как указателем на обычную память. Допустим, адрес возврата имеет длину 4 байта, а x0, y0, x1, y1 по 2 байта. Значит всего они занимают в стеке 12 байт. Если sp это указатель стека, то непосредственно в sp лежит адрес возврата, в sp-4 лежит x0, в sp-6 лежит y0 и т.д.
Поделав свои дела, функция выполняет команду return. Эта команда автоматически выпихивает адрес возврата из стека и передает его в процессор, чтобы тот продолжал выполнение с этого адреса. Но у нас в стеке все ещё лежат параметры x0, y0, x1, y1, которые были туда запихнуты, но никто их не выпихнул.
Чтобы привести стек в порядок после вызова функции, существуют машинные инструкции, которые не просто выпихивают адрес возврата из стека, но заодно с ним выпихивают еще и нужное количество байт. Транслятор сам генерирует такие инструкции, чтобы после возврата из функции все сошлось и в стеке не осталось забытых параметров.
Как видим, в стеке хранятся и адреса возврата, и параметры функций, и все это лежит вперемешку, нет ли здесь опасности что-то перепутать? При нормальном выполнении программы – нет. Все вызовы и возвраты происходят в правильном порядке, и поэтому все данные всегда совпадают. Но вы наверно слышали о хакерской атаке "переполнение стека". Именно манипуляцией данными в стеке взломщикам удается добиться того, что возврат произойдет не на тот адрес.
Можно ли сделать стек вручную?
Конечно. Это всего лишь область памяти (например, можете завести массив) и указатель (смещение), который нужно сдвигать при добавлении и удалении элементов. Во многих объектно-ориентированных языках массивы и так уже имеют методы push() и pop(), то есть это уже готовые стеки. Но вручную сделанный стек не будет участвовать в исполнении вашей программы, потому что настоящий указатель стека есть только у процессора (и у вас, если вы пишете на ассемблере). А ваш стек вы можете использовать только для своих нужд, скажем, для правильной организации рекурсии.