Стек

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

Последний добавленный в стек объект представляет верхушку стека (top of stack или tos). И если нам надо взять из стека данные, то сначала мы берем их из верхушки стека.

Для управления стеком обычно выделается отдельный регистр, который еще называется указателем стека. В архитектуре Intel x86-64 в качестве такого регистра выступает RSP, на ARM - регистр SP

Когда программа начинает выполняться, программе выделяется стек в виде области в оперативной памяти обычно в несколько мегабайт. При этом операционная система инициализирует регистр RSP/SP адресом непосредственно перед началом области стека. В последствии указатель стека RSP/SP указывает на верхушку стека - адрес последнего добавленного значения.

Стек растет от больших адресов к меньшим, то есть при добавлении в стек данных, адрес добавляемых данных будет уменьшаться на размер добавляемых данных. А при получении данных, адрес, наоборот, увеличивается на размер полученных данных. Например, определим следующую программу на языке Python:

sp = 8            # указатель стека
stack = [0]*sp      # условный стек

# функция лобавления в стек
def push(data):
    global sp
    if sp==0: 
        raise Exception("Переполнение стека")
    sp = sp - 1         # уменьшаем указатель стека. стек указывает на следующее свободное место
    stack[sp] = data   # помещаем в стек данные
    print("stack:", stack, "\tsp: ", sp)
    
# функция извлечения из стека
def pop():
    global sp
    if(sp >= len(stack)): raise Exception("Stack is empty")  # если стек пуст
    data = stack[sp]    # получаем данные
    sp = sp + 1         # увеличиваем адрес в стеке
    print("stack:", stack, "\tsp: ", sp)
    return data

# помещаем в стек данные
push(1)
push(2)
push(3)

# получаем данные. tos - top of the stack - верхушка стека
tos = pop()
print("tos:", tos)
tos = pop()
print("tos:", tos)
tos = pop()
print("tos:", tos)

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

sp = 8            # указатель стека
stack = [0]*sp      # условный стек

Для определения стека используем список из 8 элементов. В начале программы указатель стека указывает на условный адрес после последней ячейки в стеке. То есть у нас ячейки в стеке имеют условные адреса 0, 1, 2, ...7. Соответственно указатель стека равен 8.

В функции push через параметр получаем данные, уменьшаем указатель стека и по адресу, на который он ссылается, помещаем переданные данные:

sp = sp - 1         # уменьшаем указатель стека. стек указывает на следующее свободное место
stack[sp] = data   # помещаем в стек данные

Если стек уже заполнен, генерируем исключение.

В функции pop получаем данные и увеличиваем адрес в указателе стека:

data = stack[sp]    # получаем данные
sp = sp + 1         # увеличиваем адрес в стеке

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

Для теста в программе помещаем в стек 3 числа и потом их извлекаем.

# помещаем в стек данные
push(1)
push(2)
push(3)

# получаем данные
tos = pop()
print("tos:", tos)
tos = pop()
print("tos:", tos)
tos = pop()
print("tos:", tos)

После добавления числа числа 3 стек приобретет следующий вид

Адрес	Значение
0x0000	0
0x0001	0
0x0002	0
0x0003	0
0x0004	0
0x0005	3	SP=5
0x0006	2
0x0007	1

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

stack: [0, 0, 0, 0, 0, 0, 0, 1] 	sp:  7
stack: [0, 0, 0, 0, 0, 0, 2, 1] 	sp:  6
stack: [0, 0, 0, 0, 0, 3, 2, 1] 	sp:  5
stack: [0, 0, 0, 0, 0, 3, 2, 1] 	sp:  6
tos: 3
stack: [0, 0, 0, 0, 0, 3, 2, 1] 	sp:  7
tos: 2
stack: [0, 0, 0, 0, 0, 3, 2, 1] 	sp:  8
tos: 1

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

push(1)
print("tos:", pop())     # tos: 1
push(22)
print("tos:", pop())     # tos: 22

Результат программы:

stack: [0, 0, 0, 0, 0, 0, 0, 1] 	sp:  7
stack: [0, 0, 0, 0, 0, 0, 0, 1] 	sp:  8
tos: 1
stack: [0, 0, 0, 0, 0, 0, 0, 22] 	sp:  7
stack: [0, 0, 0, 0, 0, 0, 0, 22] 	sp:  8
tos: 22