exam12 2 - stankin/design-part-1 GitHub Wiki
Понятия очереди, стека и кучи в объектно-ориентированном программировании. Назначение и способы реализации.
Реферат к лекции 12 (2). Математические методы в объектно-ориентированном проектировании.
Выполнил: Габдуллин Руслан, группа ИДБ-18-06
Проверил: Мельникова Полина, группа ИДБ-18-06
Объектно-ориентированное программирование – это подход, при котором вся программа рассматривается как набор взаимодействующих друг с другом объектов. При этом важно знать их характеристики[1].
Очередь
Очередью (англ. – queue) называется структура данных, из которой удаляется первым тот элемент, который был первым в очередь добавлен. То есть очередь в программировании соответствует «бытовому» понятию очереди. Очередь также называют структурой типа FIFO (first in, first out — первым пришел, первым ушел) [2].
Назначение
В операционной системе компьютера (и в сети интернет) постоянно работают различные очереди, незаметно исполняющие свои обязанности. Например, в очереди печати — документы ждут освобождения принтера. Данные вводимые с клавиатуры, также хранятся в очереди. Если вы работаете в текстовом редакторе, а компьютер отвлекается на выполнение другой операции, то нажатые будут ждать в очереди, пока у редактора не явится свободное время для их получения.
Способы реализации
Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end.
Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов.
Стек
Стеком (англ. – stack) называется структура данных, в которой элементы хранятся в виде последовательности, при этом работать можно только с одним элементом — который был последним добавлен в стек. Поэтому стек также называют структурой типа LIFO (last in, first out — последним пришел, первым ушел).[3]
Назначение
Стек используют для разных целей:[4]
- организации прерываний, вызовов и возвратов;
- временного хранения данных, когда под них нет смысла выделять фиксированные места в памяти;
- передачи и возвращения параметров при вызовах процедур.
Способы реализации
Существует несколько способов реализации стека:
- с помощью одномерного массива;
- с помощью связанного списка;
- с помощью класса объектно-ориентированного программирования.
Куча
Куча это специализированная структура данных типа дерево, которая удовлетворяет свойству кучи: если B является узлом-потомком узла A, то ключ(A) ≥ ключ(B). Из этого следует, что элемент с наибольшим ключом всегда является корневым узлом кучи, поэтому иногда такие кучи называют max-кучами (в качестве альтернативы, если сравнение перевернуть, то наименьший элемент будет всегда корневым узлом, такие кучи называют min-кучами).[5]
Назначение
Структуры данных типа кучи имеют множество применений.
- Пирамидальная сортировка: один из лучших применяемых методов сортировки, не имеющий квадратичных наихудших сценариев.
- Алгоритмы поиска: при использовании кучи поиск минимума, максимума, того и другого, медианы или k-го наибольшего элемента может быть сделан за линейное время (часто даже за константное время).
- Алгоритмы на графах: Применение кучи в качестве структуры данных для внутреннего обхода даёт сокращение времени выполнения на полиномиальный порядок. Примерами таких проблем являются алгоритм построения минимального остовного дерева Прима и проблема кратчайшего пути Дейкстры.
Способы реализации
- Стандартная библиотека шаблонов языка C++ предоставляет шаблоны функций для управления кучей make_heap, push_heap и pop_heap (обычно реализуются бинарные кучи), которые оперируют с итераторами произвольного доступа. Методы используют итераторы как ссылки на массивы и выполняют преобразование массив-куча.
- Набор шаблонов Java платформы Java 2 (начиная с версии 1.5) предоставляет реализацию бинарной кучи в классе java.util.PriorityQueue.
- Python имеет модуль heapq, который реализует очереди с приоритетами с помощью бинарной кучи.