Skip to content
Полина edited this page Dec 16, 2021 · 5 revisions

Понятия очереди, стека и кучи в объектно-ориентированном программировании. Назначение и способы реализации.

Выполнил: Габдуллин Руслан, группа ИДБ-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, который реализует очереди с приоритетами с помощью бинарной кучи.

Список литературы:

  1. Объектно-ориентированное программирование простым языком
  2. Очередь
  3. Стек
  4. Для чего нужна куча?
  5. Куча (структура данных)
Clone this wiki locally