JavaRush /Курсы /Harvard CS50 /Стек, очередь и куча

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

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) возникает, если мы пытаемся записать в него больше данных, чем предусмотрено размером этого массива. С помощью переполнения буфера злоумышленник может записать опасный код в память компьютера.

Комментарии (13)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
25 января 2021
так это язык С или джава ?
Andrey Kachur Уровень 3
5 апреля 2024
C
Artem Уровень 0
19 ноября 2020
уважаемые коллеги. просветите пожалуйста, когда после typedef struct перед фигурной скобкой пишется имя структуры, а когда нет (в качестве примера см. комментарий MezoneOrange от 19 сентября)? никак я не могу взять в толк.
Александр # Уровень 0
25 апреля 2021
Артем, тоже пытался это понять, и в итоге долгих скитаний, наткнулся на этот ответ, который показался наиболее полным: Stackoverflow.com: What is the real difference between struct and typedef struct in C? Гугловский перевод на русский на coderoad.ru: В чем реальная разница между struct и typedef struct в C?
MezoneOrange Уровень 37
19 сентября 2020
Мне кажется, не очень удобно в очереди использовать массив, односвязный список мне больше пришелся по душе. Так расширять количество элементов удобнее. Очередь:

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

typedef struct Node
{
    int value;
    struct Node *next;
} Node;
28 июля 2020
Спасибо за перевод материала! Однако, не совсем понятно, почему автор решил рассказать сразу и про структуры данных (стеки и очереди) и про организацию памяти. Ну, то есть, смотрите: - название "Стек, очередь и куча" - звучит так, будто речь пойдет про абстрактные типы данных (куча - это еще ведь и древовидная структура данных); - нет, начинается все именно с организации памяти; - хорошо, примем, что таким образом перешли от практического примера к теории; - но тогда очереди выбиваются из основного повествования (добавлены, будто, просто для того, чтобы были). Наверное, более логичным было бы все-таки разбить (по классике) на две темы: - стеки, очереди (и деки, возможно) - описание организации памяти. В общем, спасибо большое и на этом, но несколько сумбурно, на мой взгляд! 🤔
Anonymous #2532889 Уровень 35
7 марта 2021
Вдруг но рассказал про структуру памяти, чтобы студенты не забывали проверки ставить и не выходить за пределы массива. Кто знает что потом пойдёт не так.
Татьяна Уровень 8
9 сентября 2019
https://www.rsdn.org/article/cpp/ObjectsAndPointers.xml
24 сентября 2019
Отличная статья! Кто то плюсует идиотский комментарий "первый", а не отмечает такой хороший материал.
Юрий Уровень 0
20 ноября 2019
Если, как и я, плавали в вопросах кучи и стека - в чем их разница, как ими пользоваться на конкретном примере и т.д., статья очень поможет разрешить все свои противоречия :).
Kirill Уровень 0
23 июля 2020
Спасибо вам, добрый человек! Благодаря вашей статье понял тему.
FeatHonnar Уровень 16
28 октября 2022
Статья просто божественная. С этими, по крайней мере, текстовыми лекциями даже в сравнение не идет
DarkTemplar Уровень 9
7 мая 2019
первый