Стек
На рисунке вы можете видеть обобщенную модель организации памяти компьютера.

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

Но важнее даже не это, а то, что стек — это структура данных, которая работает по принципу «последним пришел — первым ушел» (last in first out, LIFO). На лекции Дэвид предложил представление стека, как стопки подносов в столовой. Поднос, который попал в стопку последним, новый клиент столовой возьмет в первую очередь.
Над стеком можно осуществлять две операции: push
(занесение данных) и pop
(изъятие данных).

Пример реализации стека языке С приведен ниже. В этом примере, стек — это просто массив строк, имеет определенную емкость (CAPACITY), и текущий размер (size):
char * strings [CAPACITY];
int size;
} stack;
Чтобы реализовать операцию push
, необходимо сделать проверку, не превышает текущий размер емкость стека, после чего — вставить элемент на позицию size
и увеличить size
на единицу.

Для реализации операции pop, необходимо проверить, не пустой стек, уменьшить текущий размер на единицу и вернуть элемент.

Очередь
Очередь (queue) — это структура данных, которая напоминает обычную очередь. То есть, в отличие от стека, она работает по принципу «первым пришел — первым ушел» (first in first out, FIFO).

Для очереди определены две операции: добавление элемента в конец очереди (enqueue) и изъятие элемента с начала очереди (dequeue).

В примере объявлена очередь, которая, по сути, представляет собой массив строк:
typedef struct {
int head;
char * strings [CAPACITY]
int size;
} queue;
Чтобы реализовать операцию enqueue, необходимо убедиться, что очередь, не переполнена, добавить элемент в конец очереди и увеличить текущий размер на единицу.

Чтобы реализовать операцию dequeue, надо убедиться, что очередь не пуста, увеличить head на единицу, уменьшить текущий размер и вернуть первый элемент очереди.

Куча и переполнение буфера
Куча (heap) — область памяти, которую контролируют непосредственно программисты. Над которой вы, как программисты, получаете непосредственный контроль. Память здесь выделяется в результате вызова функции malloc.
Более глубокие знания о стеке и куче вам пока не понадобятся. Вы их получите позже, если захотите изучать программирование и компьютерные науки глубже.
Буфер — это массив определенной длины, расположенный в памяти. Переполнение буфера (buffer overflow) возникает, если мы пытаемся записать в него больше данных, чем предусмотрено размером этого массива. С помощью переполнения буфера злоумышленник может записать опасный код в память компьютера.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ