Чет про программирование / 22) Абстрактные типы данных

Абстрактные типы данных

АТД - это тип данных, который предоставляет для работы с элементами этого типа определённый набор функций, а также возможность создавать элементы этого типа при помощи специальных функций. Вся внутренняя структура такого типа спрятана от разработчика программного обеспечения. Абстрактный тип данных определяет набор функций, независимых от конкретной реализации типа, для оперирования его значениями. Конкретные реализации АТД называются структурами данных.

1. Список – АТД с отношением полного порядка (упорядоченный), допускающий следующие функции:

• Insert – вставка в произвольное место

• Delete – удаление произвольного элемента

• Next – переход к следующему элементу

• Get – получение элемента по индексу

Может быть реализован:

• На основе массива (insert (O(1), O(n), O(n)); delete (O(1), O(n), O(n)); get (O(1) всегда))

• На основе указателей (insert (O(1) всегда); delete (O(1) всегда); get (O(1), O(n), O(n))) – запись состоит из данных и указателя на следующий элемент.

• На основе курсоров

2. Стек (last-in-first-out) – АТД с отношением полного порядка и асимптотической сложностью O(1). Имеет следующие функции:

• Push – добавить элемент на вершину стека

• Pop – убрать элемент с вершины стека

• Top – вернуть элемент с вершины стека

3. Очередь (first-in-first-out) – АТД, имеющий следующие функции:

• Push – добавить элемент в конец очереди

• Pop – удаляет элемент из начала очереди

• Front – возвращает первый элемент очереди

4. Дэк – double ended queue; двухсторонняя очередь -  структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец, то есть дисциплинами обслуживания являются одновременно FIFO и LIFO.

• PushBack — добавление в конец очереди.

• PushFront — добавление в начало очереди.

• PopBack — выборка с конца очереди.

• PopFront — выборка с начала очереди.