90.Типы adt-контейнеров шаблонов.

Библиотеку класса контейнера можно разделить на две категории: фундаментальные структуры данных FDS (Fundamental Data Structures) и абстрактные типы данных ADT (Abstract Data Types)

типы ADT обычно используются в конструкциях обработки данных. Каждый тип ADT имеет соответствующие методы, например, контейнеры стека - функции-элементы Push и Pop.

Абстра́ктный тип да́нных (АТД)(анг ADT) — это тип данных, который предоставляет для работы с элементами этого типа определённый набор функций, а также возможность создавать элементы этого типа при помощи специальных функций. Абстрактный тип данных определяет набор независимых от конкретной реализации типа функций для оперирования его значениями.

Различие между абстрактными типами данных и структурами данных, которые реализуют абстрактные типы, можно пояснить на следующем примере. Абстрактный тип данных список может быть реализован при помощи массива или линейного списка, с использованием различных техник динамического выделения памяти. Однако каждая реализация определяет один и тот же набор функций, который должен работать одинаково (по результату, а не по скорости) для всех реализации.

Абстрактные типы данных позволяют достичь модульности программных продуктов и иметь несколько альтернативных взаимозаменяемых реализаций отдельного модуля.

Примеры АТД

Список

Стек

Очередь

Ассоциативный массив

Очередь с приоритетом

Спи́сок — конечное, возможно пустое множество данных (элементов) различной природы, имеющее определённый смысл для решаемой задачи. В качестве элементов множества (списка) могут выступать любые другие элементы данных, в том числе и сами списки.

Стек (англ. stack — стопка) — структура данных с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришел — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно снять верхнюю.

О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.

уществует несколько способов реализации очереди на языках программирования.

Массив

Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end.

Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдёт новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив и значение переменной становится равным n. Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.

Недостатки: максимальное количество элементов в очереди ограничено размером массива. При его переполнении требуется перевыделение памяти и копирование всех элементов в новый массив.

Связный список

Второй способ основан на работе с динамической памятью. Очередь представляется в качестве линейного списка, в котором добавление/удаление элементов идет строго с соответствующих его концов.

Преимущества данного метода: размер очереди ограничен лишь объёмом памяти.

Недостатки: сложнее в разработке; требуется больше памяти; при работе с такой очередью память сильнее фрагментируется; работа с очередью несколько медленнее.

Ассоциативный массив (словарь) — абстрактный тип данных (интерфейс к хранилищу данных), позволяющий хранить пары (ключ, значение) и поддерживающий операции добавления пары, а также поиска и удаления пары по ключу:

INSERT(ключ, значение)

FIND(ключ)

REMOVE(ключ)

Предполагается, что ассоциативный массив не может хранить две пары с одинаковыми ключами. В паре (k,v) значение v называется значением, ассоциированным с ключом k.

Операция FIND(ключ) возвращает значение, ассоциированное с заданным ключом, или некоторый специальный объект UNDEF, означающий, что значения, ассоциированного с заданным ключом, нет. Две другие операции ничего не возвращают (за исключением, возможно, успешности выполнения данной операции).

Ассоциативный массив с точки зрения интерфейса удобно рассматривать как обычный массив, в котором в качестве индексов можно использовать не только целые числа, но и значения других типов, например, строки.

Поддержка ассоциативных массивов есть во многих интерпретируемых языках программирования высокого уровня, таких как Perl, PHP, Python, Ruby, Tcl, JavaScript и др.

Очередь с приоритетом (priority queue) — абстрактный тип данных в программировании поддерживающий три операции:

InsertWithPriority: добавить в очередь элемент с нaзначенным приоритетом GetNext: извлечь из очереди и вернуть элемент с наивысшим приоритетом (другие названия "PopElement(Off)" или "GetMinimum") PeekAtNext (необязательная операция): просмотреть элемент с наивысшим приоритетом без извлечения. Говоря другим языком, очередь с приоритетом позволяет хранить пары (ключ, значение) и поддерживает операции добавления пары, поиска пары с минимальным ключом и извлечения пары с минимальным ключом:

INSERT(ключ, значение) — добавляет пару (k,v) в хранилище;

MIN — возвращает пару (k,v) с минимальным значением ключа k.

EXTRACT_MIN — возвращает пару (k,v) с минимальным значением ключа, удаляя её из хранилища.

Очередь с приоритетом может хранить несколько пар с одинаковыми ключами.

Если очередь пуста, то можно считать, что операции MIN и EXTRACT_MIN возвращают некоторую специальную константу UNDEF.

.