Абстрактные типы данных — стек, очередь, связный список
Введено
17:31
Типы данных и структуры
Каждое значение, которое хранит программа, требует типа данных — и выбор правильного имеет значение. Допустим, вы сохраняете, есть ли товар в наличии. Вы могли бы записать слово yes…
Озвучивание на английском · переключаемые субтитры на английском и китайском языках
In this lesson
| English | Значение |
|---|---|
| queue/kjuː/ | очередь |
| push/pʊʃ/ | поместить в стек |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | абстрактный тип данных |
| stack/stæk/ | Стек |
| linked list/lɪŋkt lɪst/ | связный список |
| LIFO/ˈlaɪfəʊ/ | LIFO (последним вошёл — первым вышел) |
| pop/pɒp/ | извлечь из стека |
| pointer/ˈpɔɪntə/ | указатель |
| FIFO/ˈfaɪfəʊ/ | FIFO (первым вошёл — первым вышел) |
| enqueue/enˈkjuː/ | поместить в очередь |
| dequeue/diːˈkjuː/ | извлечь из очереди |
| node/nəʊd/ | узел |
| traverse/trəˈvɜːs/ | обход |
Кнопка «Назад» и очередь принтера
- Каждая посещаемая вами страница помещается в стопку; кнопка «Назад» снимает верхнюю страницу. Страница, которую вы покинули последней, будет первой возвращённой.
- В коридоре принтер обрабатывает задания в порядке их поступления. Документ, отправленный первым, печатается первым, независимо от того, какие документы стоят позади него.
- Две структуры, противоположные правила, и вы используете обе до перерыва. Ни одна из них не говорит, как именно они хранятся; каждая описывает лишь то, что делают их операции.
- Это абстрактный тип данных. Этот урок охватывает три типа, названных в программе курса, операции для каждого из них и способы обоснования выбора одного из них для конкретной ситуации.
Что такое АТД
- Абстрактный тип данных (АТД) — это совокупность данных вместе с набором операций над этими данными. Одно предложение — это определение на один балл.
- Он определяется тем, что делают операции, а не тем, как хранятся данные. Реализация скрыта, поэтому она может изменяться без влияния на код, использующий её.
- Стек, очередь, связный список, бинарное дерево и массив — всё это АТД.
Абстрактный тип данных (ADT) определяется:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
ADT определяет операции (интерфейс); реализация скрыта и может изменяться произвольно.
Стек
- Стек — это список, в котором элементы добавляются и удаляются с одного и того же конца, вершины, так что последний добавленный элемент является первым удалённым: LIFO (Last In First Out — последним пришёл, первым вышел).
- Операции: push добавляет сверху, pop удаляет сверху, peek смотрит на верхний элемент, а также проверки на пустоту и переполнение.
- Применение: история отмены, кнопка «Назад», адреса возврата вызовов функций, проверка скобок, обратный поиск.

Всё происходит на вершине
В каком порядке работает стек?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Стек работает по принципу LIFO: последний добавленный элемент является первым извлечённым.
Разобранное решение: прослеживание стека
- Стек хранит снизу
'P' 'N' 'Z' 'X' 'Y' 'W'; верхний указатель находится на'W'. Выполняются операцииPOP,POP,PUSH 'A',PUSH 'B',POP. Что хранит стек и где находится указатель? - Два извлечения удаляют
'W', затем'Y'. Операции вставки помещают на их место сначала'A', затем'B'. Последнее извлечение удаляет'B'. - Стек содержит
'P' 'N' 'Z' 'X' 'A', указатель находится на позиции'A'. Элемент с наибольшим индексом в стеке — нижний элемент,'P'; возможно ещё пять операций pop, а шестая вызовет ошибку, поэтому перед выполнением pop всегда проверяется пустота стека.
Стек содержит P N Z X Y W (верхний элемент — W). После операций POP, POP, PUSH 'A', PUSH 'B', POP какой элемент находится сверху?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Извлечены W и Y, затем добавлены A и B, после чего B удалён. Сверху находится A над X.
Очередь
- Очередь — это список, в котором элементы добавляются в конец и удаляются с начала, так что первый добавленный элемент является первым удалённым: FIFO (First In First Out — первым пришёл, первым вышел).
- Операции: enqueue добавляет в конец, dequeue удаляет с начала, а также проверки на пустоту и переполнение.
- Применение: спутинг печати (buffer printing), буферы клавиатуры, планирование, клиенты в магазине, поиск в ширину.

Вход сзади, выход спереди
Стеки, очереди и связные списки
LIFO против FIFO
Стек работает по принципу LIFO (последним пришёл — первым ушёл); операции PUSH и POP выполняются с одного конца (сверху).
Очередь работает по принципу FIFO: элементы извлекаются из ______ и добавляются сзади.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
FIFO: dequeue с фронта, enqueue сзади — как очередь людей.
Разобранное решение: описание добавления и удаления из очереди
- Добавление: проверьте, что очередь не переполнена; сохраните элемент в позицию, указанную указателем конца; переместите указатель конца вперед (и увеличьте счетчик на единицу).
- Удаление: проверьте, что очередь не пуста; прочитайте элемент у указателя начала; переместите указатель начала вперед (и уменьшите счетчик на единицу).
- Укажите используемую конвенцию: если указатель конца обозначает следующее свободное место, сначала сохраните, затем переместите; если он обозначает последний элемент, сначала переместите, затем сохраните. Оба варианта засчитываются, если вы последовательны.
Расставьте шаги добавления элемента в очередь по порядку (указатель rear указывает на следующее свободное место).
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Проверка выполняется первой; затем сохранение, затем перемещение, при таком порядке следования. Укажите используемую вами конвенцию.
Связный список
- Связный список — это список, в котором каждый узел содержит элемент данных и указатель на следующий узел, а также начальный указатель на первый узел. Указатель последнего узла является маркером-пустышкой, таким как
NULL. - Операции: вставка, удаление, поиск и обход, следование указателям от головы для посещения каждого узла по порядку.
- Преимущество перед массивом: вставка или удаление обходятся дешево — нужно лишь перенаправить указатели, а список растет по мере необходимости. Недостаток: нет случайного доступа; чтобы добраться до десятого узла, приходится проходить через девять указателей.

Значение и стрелка, повторяющиеся
Связный список: узлы соединены указателями.
Каждый узел хранит значение и указатель на следующий узел. Вставка или удаление только перенаправляют указатели — элементы не сдвигаются, в отличие от массива.
Каждый узел связного списка содержит:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Узел хранит свое значение плюс указатель (ссылку) на следующий узел; head обозначает начало, NULL — конец.
Связный список обеспечивает дешевую вставку/удаление (просто перенаправить указатели), но медленный случайный доступ (необходимо следовать указателям от head).
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Это компромисс между массивом и списком: массивы обеспечивают доступ по индексу O(1); списки обеспечивают дешевую вставку/удаление.
Разобранный пример: добавление узла по порядку
- Опишите, как новое значение вставляется в связный список, который поддерживается в порядке возрастания. [4]
- Пройдите по списку от головы, следуя указателям, пока не будет найден узел перед позицией: последний узел, значение которого меньше нового.
- Возьмите свободный узел и сохраните в нем новое значение. Установите указатель нового узла на адрес, на который сейчас указывает предыдущий узел.
- Затем установите указатель предыдущего узла на новый узел. Если новое значение должно стоять в начале, изменяется указатель головы.
Расставьте шаги вставки значения в упорядоченный связный список по порядку.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Найти, заполнить, направить новый узел вперед, затем перенаправить предыдущий узел. Изменение порядка последних двух шагов приведет к потере остальной части списка.
Обоснование выбора
- Элементы должны обрабатываться в том порядке, в котором они поступили (печать документов, нажатия клавиш, клиенты): это очередь, так как работает принцип «первый пришел — первый ушел».
- Самый свежий элемент должен обрабатываться первым (отмена действий, возврат назад, вложенные вызовы): это стек, так как работает принцип «последний пришел — первый ушел».
- Элементы часто вставляются или удаляются в середине упорядоченной коллекции, размер которой неизвестен: это связный список, так как меняются только указатели, а элементы не сдвигаются.
- Назовите структуру, назовите её правило, свяжите правило с ситуацией.
Соотнесите каждый ADT с его правилом и типичным использованием.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Стек = LIFO; очередь = FIFO; связный список цепляет узлы с помощью указателей.
Задания на печать должны быть выполнены в порядке их поступления. Какой ADT и почему?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Порядок поступления соответствует правилу FIFO. Стек напечатал бы самое последнее задание первым.
АБД против реализации
- АБД — это поведение: push и pop, enqueue и dequeue, вставка и обход.
- Реализация — это хранилище: в этом курсе — массив плюс несколько переменных-указателей (на следующем уроке).
- Вопрос о АБД требует операций и правил; вопрос о реализации требует массивов, указателей и проверок.
Потерянные баллы
- Push и enqueue сначала проверяют состояние полноты; pop и dequeue сначала проверяют состояние пустоты. Запишите проверку в описание.
- Вставка в связный список: установите указатель нового узла до изменения указателя предыдущего узла, иначе остальная часть списка будет потеряна.
- Стек изменяется на одном конце, очередь — на обоих. Ответ «удалить сверху очереди» относится к стеку.
- Раскройте аббревиатуры один раз: LIFO (last in first out); FIFO (first in first out).
Вы поняли
- АБД (абстрактный тип данных) — это совокупность данных вместе с набором операций над ними; поведение, а не хранилище.
- Стек: добавление и удаление сверху, LIFO, push и pop · Очередь: добавление сзади, удаление спереди, FIFO, enqueue и dequeue
- Связный список: узлы значения + указателя от указателя головы; дешевая вставка и удаление, медленный случайный доступ; обход путем следования указателям
- Обоснование по правилу: порядок поступления → очередь; самый свежий первым → стек; частая вставка в середину → связный список