undefined

Стек, очередь и куча

Harvard CS50
5 уровень , 4 лекция
Открыта

Стек

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

Стек, очередь и куча - 1

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

Стек, очередь и куча - 2

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

Над стеком можно осуществлять две операции: push (занесение данных) и pop (изъятие данных).

Стек, очередь и куча - 3

Пример реализации стека языке С приведен ниже. В этом примере, стек — это просто массив строк, имеет определенную емкость (CAPACITY), и текущий размер (size):

typedef struct {
char * strings [CAPACITY];
int size;
} stack;

Чтобы реализовать операцию push, необходимо сделать проверку, не превышает текущий размер емкость стека, после чего — вставить элемент на позицию size и увеличить size на единицу.

Стек, очередь и куча - 4

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

Стек, очередь и куча - 5

Очередь

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

Стек, очередь и куча - 6

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

Стек, очередь и куча - 7

В примере объявлена очередь, которая, по сути, представляет собой массив строк:

typedef struct {
  int head;
  char * strings [CAPACITY]
  int size;
} queue;

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

Стек, очередь и куча - 8

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

Стек, очередь и куча - 9

Куча и переполнение буфера

Куча (heap) — область памяти, которую контролируют непосредственно программисты. Над которой вы, как программисты, получаете непосредственный контроль. Память здесь выделяется в результате вызова функции malloc.

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

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

Комментарии (11)
Чтобы просмотреть все комментарии или оставить свой,
перейдите в полную версию
25 января 2021
так это язык С или джава ?
Artem 0 уровень
19 ноября 2020
уважаемые коллеги. просветите пожалуйста, когда после typedef struct перед фигурной скобкой пишется имя структуры, а когда нет (в качестве примера см. комментарий MezoneOrange от 19 сентября)? никак я не могу взять в толк.
MezoneOrange 37 уровень, Екатеринбург
19 сентября 2020
Мне кажется, не очень удобно в очереди использовать массив, односвязный список мне больше пришелся по душе. Так расширять количество элементов удобнее. Очередь:

typedef struct
{
    Node *head;
    Node *tail;
    int size;
} Queue;
Звено:

typedef struct Node
{
    int value;
    struct Node *next;
} Node;
Владимир Фадеев 3 уровень, Казань
28 июля 2020
Спасибо за перевод материала! Однако, не совсем понятно, почему автор решил рассказать сразу и про структуры данных (стеки и очереди) и про организацию памяти. Ну, то есть, смотрите: - название "Стек, очередь и куча" - звучит так, будто речь пойдет про абстрактные типы данных (куча - это еще ведь и древовидная структура данных); - нет, начинается все именно с организации памяти; - хорошо, примем, что таким образом перешли от практического примера к теории; - но тогда очереди выбиваются из основного повествования (добавлены, будто, просто для того, чтобы были). Наверное, более логичным было бы все-таки разбить (по классике) на две темы: - стеки, очереди (и деки, возможно) - описание организации памяти. В общем, спасибо большое и на этом, но несколько сумбурно, на мой взгляд! 🤔
Татьяна 8 уровень
9 сентября 2019
https://www.rsdn.org/article/cpp/ObjectsAndPointers.xml
DarkTemplar 9 уровень
7 мая 2019
первый