Структура данных дек

Каракотов Тимур Романович 02262-ДБ

Лекция 5. Дек

Конспект лекции

1. Структура данных дек

• Операции над деком и требования к ним.

Дек - структура данных с произвольным доступом к элементам за O(1). Доступ к элементам производится по ключу - целому числу в диапазоне [0; n - 1], где n - количество элементов в деке. Кроме того, дек способен выполнять вставку и удаление элементов из головы и из хвоста последовательности за O(1).

• Дек в C++.

Для работы с деком требуется подключить заголовочный файл deque. У шаблонного класса deque два параметра: тип хранимых элементов и аллокатор. Второй параметр не является обязательным. Доступ к элементам осуществляется при помощи оператора []. Для доступа к первому и к последнему элементу, кроме того, можно применять методы класса front() и back() соответственно. Основные методы класса для вставки и удаления элементов: push_front(), push_back(), pop_front(), pop_back().

• Дек в Python.

Различные структуры данных, в том числе дек, размещены в модуле collections. Конструктор дека называется deque. Доступ к элементам осуществляется при помощи оператора []. Основные методы класса для вставки и удаления элементов: append(), appendleft (), pop(), popleft (). Для добавления итерируемой последовательности справа или слева можно использовать методы extend и extendleft.

1. Способы реализации дека

• Динамический массив с резервированием памяти с двух сторон. Плюсы и минусы метода.

Элементы дека располагаются в середине выделенной области памяти. Память под резервные элементы выделяется как слева, так и справа. При исчерпании резерва с одной из сторон происходит реаллокация элементов. Плюсы метода: все элементы занимают непрерывный участок памяти, в качестве итераторов можно использовать указатели. Минусы метода: иметь резерв элементов с обеих сторон массива еще более затратно по памяти, чем в случае с вектором, часто деки используются в качестве очереди, когда элементы добавляются с одного конца, а извлекаются с другого, в этом случае слева от элементов образуется большая неиспользуемая область памяти.

• Динамический массив с кольцевым порядком элементов. Плюсы и минусы метода.

Массив мыслится нами как кольцо, в котором после последнего элемента идет первый. Каждый следующий элемент расположен справа. Поле reserved хранит количество элементов в выделенной области памяти. Поле size хранит количество элементов в деке. Поле offset хранит смещение от начала выделенной памяти первого элемента дека. Для доступа к элементу с номером i можно использовать вычисления в кольце по модулю reserved по формуле (offset+i)%reserved. Плюсы метода: простая реализация, при использовании дека как очереди с постоянным числом элементов память расходуется достаточно экономно. Минусы метода: дек при такой реализации не умеет освобождать память после использования, есть сложности с реализацией итераторов, в частности, операций сравнения двух итераторов при реализации итераторов через указатели.

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

Память под указатели содержит резерв как слева, так и справа. Если резервные указателей исчерпывается, то может быть выполнена их реаллокация. После нее существующие указатели размещаются в середине выделенной области памяти. Если резерв с одной стороны исчерпан, а с другой еще достаточно большой, то указатели могут быть перемещены в середину без выделения новой области памяти. Плюсы метода: экономное расходование памяти во всех случаях, быстрая вставка и удаление новых элементов, хорошо подходит для реализации очередей. Минусы метода: более сложная реализация основных операций с итераторами замедляет использование дека в качестве динамического массива.