Реализация ADT с использованием массивов.
Введено| English | Значение |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | переполнение |
| underflow/ˌʌndəˈfləʊ/ | переполнение снизу |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | циклический массив |
| free list/friː lɪst/ | список свободных ячеек |
В памяти не существует такого понятия, как стек
- Откройте компьютер и поищите стек. Вы его не найдете. Память представляет собой один огромный массив пронумерованных ячеек, и больше ничего нет.
- Каждый стек, каждая очередь, каждый связный список — это тот же массив плюс две или три целочисленные переменные, которые помнят, где находятся данные. Push — это «прибавить единицу к числу и сохранить»; dequeue — это «прочитать ячейку и прибавить единицу к другому числу».
- Весь этот урок посвящен учету: какие указатели, какие проверки и что происходит на границах.
- На экзамене вас просят описать объявления, пройти по указателям через несколько операций и объяснить, зачем нужны проверки.
Стек в массиве
- Храните элементы в
Stack[1:MaxSize]с целочисленнымTop, равным 0, когда стек пуст. - Вставка(x): если
Top = MaxSizeстек переполнен, происходит переполнение; иначе выполняетсяTop ← Top + 1иStack[Top] ← x. - Pop(): если
Top = 0стек пуст, происходит переполнение снизу; иначе вернитеStack[Top]иTop ← Top − 1.

Массив никогда не двигается; движется только Top
Добавление элемента в уже заполненный стек вызывает переполнение стека ______.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Overflow = push при Top = MaxSize; извлечение из пустого стека (Top = 0) — это underflow.
Соотнесите каждое условие стека на массиве с его значением.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Top считает элементы: 0 = пусто, MaxSize = полно; два случая ошибок — это underflow и overflow.
Разобранный пример: объявление и инициализация стека
- Опишите объявления и инициализацию, необходимые для реализации стека до 50 целых чисел с использованием массива. [5]
- Массив из 50 элементов типа
INTEGER, обозначаемыйDECLARE Stack : ARRAY[1:50] OF INTEGER, для хранения элементов. - Константа или переменная
MaxSize, установленная на 50, чтобы push мог проверить состояние полноты. - Указатель вершины стека
INTEGER, обозначенный какTop, инициализируется значением 0 для указания на пустой стек; операция извлечения проверяет его на переполнение снизу (underflow), а операция вставки сравнивает его со значениемMaxSizeдля проверки переполнения.
Что должно входить в объявление и инициализацию стека на массиве? Выберите все подходящие варианты.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Стеку нужен один указатель Top. Указатель front принадлежит очереди.
Очередь в обычном массиве
- Два указателя:
Frontдля следующего элемента, подлежащего удалению,Rearдля следующего свободного места. Enqueue сохраняет элемент вRearи перемещает указатель вперед; dequeue читает элемент изFrontи перемещает указатель вперед. - Оба указателя могут двигаться только вперед, поэтому после нескольких операций они уходят за конец массива, в то время как ячейки в начале остаются пустыми и недоступными.
- Решение: позволить указателям перескакивать (wrap around).
Круговой массив
- Круговой массив возвращает указатель к первой ячейке, когда он проходит последнюю: с индексацией от 1, формула
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x): проверка отсутствия полноты;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue(): проверка отсутствия пустоты; вернутьQueue[Front];Front ← (Front MOD MaxSize) + 1. - Храните отдельное счетчик: когда очередь полностью заполнена и когда она пуста, два указателя занимают одинаковое относительное положение, поэтому одних только указателей недостаточно, чтобы различить эти два состояния.

После последней ячейки следует первая ячейка
Реализация ADT с помощью массивов.
FIFO.
Очередь работает по принципу FIFO — enqueue сзади, dequeue с фронта.
Зачем использовать циклический массив для очереди?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Линейная очередь тратит ячейки в начале по мере продвижения Front; зацикливание с помощью MOD переиспользует их.
Циклическая очередь использует MOD, чтобы указатели front/rear зацикливались и переиспользовали ячейки, освобожденные в начале массива.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
(pointer MOD MaxSize) + 1 возвращает индекс к первой ячейке, поэтому линейная очередь больше не тратит ячейки, которые passed указатель Front.
Разобранный пример: движение по указателям
- С
MaxSize = 6: еслиRear = 5, то(5 MOD 6) + 1 = 6, поэтому следующий элемент помещается в ячейку 6. ЕслиRear = 6, то(6 MOD 6) + 1 = 1: указатель перескакивает на ячейку 1. - Циклическая очередь хранится в массиве размером 5, с индексами от 0 до 4, где находятся элементы
Front = 3,Rear = 3и один дополнительный элемент. Добавляются два элемента, затем удаляются два. При использовании индексации от 0 каждое перемещение вычисляется по формуле(pointer + 1) MOD 5. - Двойное добавление сдвигает
Rear: 3 → 4, затем 4 → 0, поскольку (4 + 1) MOD 5 = 0. Двойное удаление сдвигаетFront: 3 → 4 → 0. Остается один элемент на индексе 0, а очередь повторно использует ячейки, освобожденные в начале массива.
Циклическая очередь использует ячейки с 1 по 6, и Rear = 6. После операции Rear ← (Rear MOD 6) + 1, куда попадет следующий элемент?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
6 MOD 6 = 0, плюс 1 дает 1. Указатель возвращается к началу массива.
Разобранный пример: алгоритм добавления элемента словами
- Опишите алгоритм добавления элемента в круговую очередь. [4]
- Если счетчик равен размеру, сообщите, что очередь полна, и остановитесь.
- Иначе увеличьте указатель хвоста на единицу; если он вышел за пределы последнего индекса, установите его на первый индекс.
- Сохраните элемент по указателю хвоста и увеличьте счетчик на единицу.
Расставьте шаги добавления в циклическую очередь по порядку.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Проверка, перемещение, зацикливание, сохранение, счетчик. Именно зацикливание делает массив циклическим.
Связный список в массиве
- Используйте массив записей узлов, каждая из которых содержит
NextIndexиндекс;-1обозначает конец.Headиндекс указывает на первый узел,-1если список пуст. - Невоспользованные слоты соединены в список свободных ячеек из
FreeListHead, точно так же, как список данных связывает используемые.
TYPE TNode
DECLARE Value : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // -1 when empty
DECLARE FreeListHead : INTEGER // first unused slot
- Вставка: возьмите слот на позиции
FreeListHead, установите егоValueиNextIndex, затем переподключитеNextIndexилиHeadпредыдущего узла. Удаление: разорвите связь узла и верните его слот в начало списка свободных ячеек.

Два списка делят один массив: список данных и список свободных ячеек
В связном списке на основе массива свободный список:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Свободный список связывает резервные ячейки, поэтому при вставке можно захватить одну, а при удалении — вернуть; это похоже на второй связный список пустых ячеек.
Разобранный пример: вставка в удерживаемый массивом список
- Массивы
DataиPointerсодержат список 1 → 3 → 4, сStart = 1; индекс 1 содержитD40, индекс 3 содержитD32, индекс 4 содержитD11с нулевым указателем. Список свободных ячеек начинается с индекса 2 и продолжается 2 → 5. ВставьтеD6междуD32иD11. - Берётся первый свободный узел с индексом 2, и его указатель
FreeStartустанавливается на значение 5. ЗначениеD6записывается в ячейкуData[2]. - Set
Pointer[2]to the valuePointer[3]held, which is 4. Then setPointer[3]to 2. - Теперь список выглядит как 1 → 3 → 2 → 4, а список свободных ячеек: 5 → null. Реализация, если требуется: массив для данных, параллельный массив (или поле записи) для указателей, указатель начала и указатель списка свободных ячеек.
В разобранном примере после вставки D6 свободный список начинается с индекса ____.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Индекс 2 был взят из свободного списка, поэтому FreeStart перемещается туда, куда указывал индекс 2, то есть на 5.
При вставке в список указатель предыдущего узла следует изменить до установки указателя нового узла.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Сначала установите указатель нового узла на старый следующий узел. Если сначала перепровести предыдущий узел, адрес остальной части списка будет утерян.
Потерянные баллы
- Проверки выполняются первыми: проверка на переполнение перед push или enqueue, проверка на пустоту перед pop или dequeue. Опишите их; это баллы.
- Формула обёртки зависит от индексов:
(Rear MOD MaxSize) + 1для базированной на 1,(Rear + 1) MOD Sizeдля базированной на 0. Сопоставьте границы вопроса. - Счетчик — это то, что отличает полную круговую очередь от пустой. Одних только указателей недостаточно.
- Set the new node's
NextIndexbefore rewiring the previous node, and return a deleted node's slot to the free list, or the array slowly fills with unreachable cells.
Вы поняли
- стек в массиве:
Stack[1:MaxSize]и указательTop, начинающийся с 0;Top = MaxSize— переполнение,Top = 0— недополнение - круговая очередь:
FrontиRearобходятся с помощьюMOD; отдельный счетчик отличает полную очередь от пустой - linked list in an array: node records with a
NextIndexindex, aHead, and a free list chaining the spare slots - каждая операция: сначала проверка, затем арифметика указателей, затем запись или чтение; поведение ADT не меняется от способа хранения