Что такое дек в программировании
Дек (двусторонняя очередь).
Дек (deque — double ended queue, «двусторонняя очередь») – структура данных типа «список», функционирующая одновременно по двум принцам организации данных: FIFO и LIFO. Определить дек можно как очередь с двумя сторонами, так и стек, имеющий два конца. То есть данный подвид списка характерен двухсторонним доступом: выполнение поэлементной операции, определенной над деком, предполагает возможность выбора одной из его сторон в качестве активной.
Число основных операций, выполняемых над стеком и очередью, как помнит читатель, равнялось трем: добавление элемента, удаление элемента, чтение элемента. При этом не указывалось место структуры данных, активное в момент их выполнения, поскольку ранее оно однозначно определялось свойствами (определением) самой структуры. Теперь, ввиду дека как обобщенного случая, для приведенных операций следует указать эту область. Разделив каждую из операций на две: одну применительно к «голове» дека, другую – его «хвосту», получим набор из шести операций:
На практике этот список может быть дополнен проверкой дека на пустоту, получением его размера и некоторыми другими операциями.
В плане реализации двусторонняя очередь очень близка к стеку и обычной очереди: в качестве ее базиса приемлемо использовать как массив, так и список. Далее мы напишем интерфейс обработки дека, представленного обычным индексным массивом. Программа будет состоять из основной части и девяти функций:
Помимо самого массива потребуется указатель на последний элемент, назовем его last. Указатель на первый элемент не потребуется, поскольку дек будет представлять собой смещающуюся структуру, т. е. при добавлении нового элемента в начало, каждый из старых элементов сместиться на одну позицию вправо, уступив тем самым первому элементу ячейку с индексом 0 (в C++), следовательно, адрес первого элемента – константа.
Алгоритмы и структуры данных для начинающих: стеки и очереди
Авторизуйтесь
Алгоритмы и структуры данных для начинающих: стеки и очереди
В предыдущих частях мы рассматривали базовые структуры данных, которые, по сути, являлись надстройками над массивом. В этой статье мы добавим к коллекциям простые операции и посмотрим, как это повлияет на их возможности.
Стек — это коллекция, элементы которой получают по принципу «последний вошел, первый вышел» (Last-In-First-Out или LIFO). Это значит, что мы будем иметь доступ только к последнему добавленному элементу.
Наиболее часто встречающаяся аналогия для объяснения стека — стопка тарелок. Вне зависимости от того, сколько тарелок в стопке, мы всегда можем снять верхнюю. Чистые тарелки точно так же кладутся на верх стопки, и мы всегда будем первой брать ту тарелку, которая была положена последней.
Если мы положим, например, красную тарелку, затем синюю, а затем зеленую, то сначала надо будет снять зеленую, потом синюю, и, наконец, красную. Главное, что надо запомнить — тарелки всегда ставятся и на верх стопки. Когда кто-то берет тарелку, он также снимает ее сверху. Получается, что тарелки разбираются в порядке, обратном тому, в котором ставились.
Теперь, когда мы понимаем, как работает стек, введем несколько терминов. Операция добавления элемента на стек называется «push», удаления — «pop». Последний добавленный элемент называется верхушкой стека, или «top», и его можно посмотреть с помощью операции «peek». Давайте теперь посмотрим на заготовку класса, реализующего стек.
Класс Stack
Метод Push
Поскольку мы используем связный список для хранения элементов, можно просто добавить новый в конец списка.
Метод Pop
Push добавляет элементы в конец списка, поэтому забирать их будет также с конца. В случае, если список пуст, будет выбрасываться исключение.
Метод Peek
Метод Count
Зачем нам знать, сколько элементов находится в стеке, если мы все равно не имеем к ним доступа? С помощью этого поля мы можем проверить, есть ли элементы на стеке или он пуст. Это очень полезно, учитывая, что метод Pop кидает исключение.
Пример: калькулятор в обратной польской записи
Классический пример использования стека — калькулятор в обратной польской, или постфиксной, записи. В ней оператор записывается после своих операндов. То есть, мы пишем:
Другими словами, вместо «4 + 2» мы запишем «4 2 +». Если вам интересно происхождение обратной польской записи и ее названия, вы можете узнать об этом на Википедии или в поисковике.
То, как вычисляется обратная польская запись и почему стек так полезен при ее использовании, хорошо видно из следующего алгоритма:
То есть, для выражения «4 2 +» действия будут следующие:
В конце на стеке окажется одно значение — 6.
Очередь
Очереди очень похожи на стеки. Они также не дают доступа к произвольному элементу, но, в отличие от стека, элементы кладутся (enqueue) и забираются (dequeue) с разных концов. Такой метод называется «первый вошел, первый вышел» (First-In-First-Out или FIFO). То есть забирать элементы из очереди мы будем в том же порядке, что и клали. Как реальная очередь или конвейер.
Очереди часто используются в программах для реализации буфера, в который можно положить элемент для последующей обработки, сохраняя порядок поступления. Например, если база данных поддерживает только одно соединение, можно использовать очередь потоков, которые будут, как ни странно, ждать своей очереди на доступ к БД.
Класс Queue
Метод Enqueue
Новые элементы очереди можно добавлять как в начало списка, так и в конец. Важно только, чтобы элементы доставались с противоположного края. В данной реализации мы будем добавлять новые элементы в начало внутреннего списка.
Метод Dequeue
Поскольку мы вставляем элементы в начало списка, убирать мы их будем с конца. Если список пуст, кидается исключение.
Метод Peek
Метод Count
Двусторонняя очередь
Двусторонняя очередь (Double-ended queue), или дек (Deque), расширяет поведение очереди. В дек можно добавлять или удалять элементы как с начала, так и с конца очереди. Такое поведение полезно во многих задачах, например, планирование выполнения потоков или реализация других структур данных. Позже мы рассмотрим вариант реализации стека с помощью двусторонней очереди.
Класс Deque
Метод EnqueueFirst
Метод EnqueueLast
Метод DequeueFirst
Метод DequeueLast
Метод PeekFirst
Метод PeekLast
Метод Count
Пример: реализация стека
Двусторонняя очередь часто используется для реализации других структур данных. Давайте посмотрим на пример реализации стека с ее помощью.
У вас, возможно, возник вопрос, зачем реализовывать стек на основе очереди вместо связного списка. Причины две: производительность и повторное использование кода. У связного списка есть накладные расходы на создание узлов и нет гарантии локальности данных: элементы могут быть расположены в любом месте памяти, что вызывает большое количество промахов и падение производительности на уровне процессоров. Более производительная реализация двусторонней очереди требует массива для хранения элементов.
Тем не менее, реализация стека или очереди с помощью массива — непростая задача, но такая реализация двусторонней очереди и использование ее в качестве основы для других структур данных даст нам серьезный плюс к производительности и позволит повторно использовать код. Это снижает стоимость поддержки.
Позже мы посмотрим на вариант очереди с использованием массива, но сначала давайте взглянем на класс стека с использованием двусторонней очереди:
Хранение элементов в массиве
Как уже было упомянуто, у реализации очереди с использованием массива есть свои преимущества. Она выглядит простой, но на самом деле есть ряд нюансов, которые надо учесть.
Давайте посмотрим на проблемы, которые могут возникнуть, и на их решение. Кроме того, нам понадобится информация об увеличении внутреннего массива из прошлой статьи о динамических массивах.
При создании очереди у нее внутри создается массив нулевой длины. Красные буквы «h» и «t» означают указатели _head и _tail соответственно.
Добавляем элемент в начало
Добавляем элемент в конец
Добавляем еще один элемент в начало
Обратите внимание: индекс «головы» очереди перескочил в начало списка. Теперь первый элемент, который будет возвращен при вызове метода DequeueFirst — 0 (индекс 3).
И еще один в конец
Массив заполнен, поэтому при добавлении элемента произойдет следующее:
Добавляем значение в конец расширенного массива
Теперь посмотрим, что происходит при удалении элемента:
Удаляем элемент из начала
Удаляем элемент с конца
Ключевой момент: вне зависимости от вместимости или заполненности внутреннего массива, логически, содержимое очереди — элементы от «головы» до «хвоста» с учетом «закольцованности». Такое поведение также называется «кольцевым буфером».
Теперь давайте посмотрим на реализацию.
Класс Deque (с использованием массива)
Интерфейс очереди на основе массива такой же, как и в случае реализации через связный список. Мы не будем его повторять. Однако, поскольку список был заменен на массив, у нас добавились новые поля — сам массив, его размер и указатели на «хвост» и «голову» очереди.
Алгоритм роста
Когда свободное место во внутреннем массиве заканчивается, его необходимо увеличить, скопировать элементы и обновить указатели на «хвост» и «голову». Эта операция производится при необходимости во время добавления элемента. Параметр startingIndex используется, чтобы показать, сколько полей в начале необходимо оставить пустыми (в случае добавления в начало).
Обратите внимание на то, как извлекаются данные, когда приходится переходить в начало массива при проходе от «головы» к «хвосту».
Метод EnqueueFirst
Метод EnqueueLast
Метод DequeueFirst
Метод DequeueLast
Метод PeekFirst
Метод PeekLast
Метод Count
Продолжение следует
Вот мы и закончили четвертую часть нашего цикла статей. В ней мы рассмотрели стеки и очереди. В следующий раз мы перейдем к бинарным деревьям поиска.
Простейшие структуры данных: стек, очередь, дек
Понятие структуры данных
Чаще всего данные, с которыми работают программы, хранятся во встроенных в используемый язык программирования массивах, константной или переменной длины. Массив константной длины можно назвать простейшей структурой данных. Но иногда для решения задачи требуется большая эффективность некоторых операций, чем у массива. В таких случаях используются другие структуры данных, часто гораздо более сложные.
Таким образом, структура данных характеризуется операциями, которые она может выполнять, и скоростью их выполнения.
В качестве примера рассмотрим несколько простейших структур данных, которые не предоставляют выгоды в эффективности, но имеют чётко определённый набор поддерживаемых операций.
Для объяснения принципа работы стека часто используется аналогия со стаканом с печеньем. Представьте, что на дне вашего стакана лежат несколько кусков печенья. Вы можете положить наверх ещё один кусок или достать уже находящийся наверху. Остальные куски закрыты верхним, и вы про них ничего не знаете. Для описания стека часто используется аббревиатура LIFO (Last In, First Out), подчёркивающая, что элемент, попавший в стек последним, первым будет из него извлечён.
Приведём простую реализацию стека на C++. Для простоты максимальный размер нашего стека будет ограничен тысячей элементов:
Как видите, для реализации стека хватает одного массива и одного указателя, обозначающего крайний элемент.
Очередь
Очередь поддерживает тот же набор операций, что и стек, но имеет противоположную семантику. Для описания очереди используется аббревиатура FIFO (First In, First Out), так как первым из очереди извлекается элемент, раньше всех в неё добавленный. Название этой структуры говорит само за себя: принцип работы совпадает с обычными очередями в магазине или на почте.
Реализация очереди похожа на реализацию стека, но в этот раз нам понадобятся два указателя: для первого элемента очереди (“головы”) и последнего (“хвоста”):
При такой реализации очередь будет постепенно “ползти” вправо по выделенной области памяти (массиву), и достаточно быстро выйдет за её границы. Впрочем, эта реализация иллюстративная, на практике вы просто будете использовать уже готовую реализацию очереди из стандартной библиотеки (об этом ниже). В ней этот дефект отсутствует из-за более сложной работы с памятью.
В принципе мы можем реализовать её таким же способом, как и две предыдущих, но как и в случае с очередью, эта реализация будет далека от оптимальной.
Стек, очередь и дек в стандартной библиотеке C++
Все три структуры данных являются базовыми и относительно часто встречаются в програмировании, поэтому они уже реализованы в стандартной библиотеке в виде трёх шаблонных классов. Пример работы со стеком и очередью:
Более сложные структуры данных
Приведённый выше материал мог вызвать у вас лёгкое недоумение и сомнения в целесообразности всех этих ограничений на обычные массивы. На самом деле, стек, очередь и дек являются лишь простейшими примерами структур данных, не предоставляющими выгоды в скорости выполнения операций. Серьёзным структурам данных посвящены отдельные темы. Стек, очередь и дек призваны проиллюстрировать, что главными характеристиками структуры данных являются набор поддерживаемых операций и скорость их выполнения.
brestprog
Олимпиадное программирование в Бресте и Беларуси
Зона кода
Дек или двухсторонняя очередь — это структура данных, которую можно представить себе в виде некоторого хранилища объектов произвольного типа, которые мы будем называть элементами. Набор всех элементов, содержащихся в хранилище, упорядочен. К деку можно применять 4 основных операции. К ним относятся:
Как мы видим, начало и конец дека совершенно равноправны. Начало дека часто называют головой, а конец — хвостом. При этом первый и последний элементы называют головным и хвостовым соответственно.
Помимо перечисленных операций, иногда к деку применяются и другие, например, операции получения крайних в наборе элементов без удаления их из дека.
Принципиальное отличие двухсторонней очереди от односторонней заключается в том, что во втором случае вставка элемента возможна только в конец очереди, а удаление возможно только из начала, а в первом, помимо этого, вставлять элементы можно ещё и в начало, а удалять — ещё и из конца.
Кстати, двухстороннюю очередь с таким же успехом можно называть и двухсторонним стеком. Очевидно, что дек можно использовать как в качестве стека, так и в качестве очереди.
В данной статье мы рассмотрим реализацию дека на языке C99 на основе массива. Статья адресована, в первую очередь, новичкам в программировании.
Основная идея
Поскольку мы, наряду с деком, будем обсуждать и массивы, мы столкнёмся с необходимостью различать 2 вида элементов: элементы дека и элементы массива. Чтобы не было путаницы, будем всегда оговаривать, о какого рода элементах идёт речь, за исключением случаев, когда информация о виде однозначно следует из контекста. Например, говоря о головных и хвостовых элементах, всегда будем иметь в виду элементы дека. И ещё. Иногда мы будем говорить об индексах элементов дека, понимая под ними индексы элементов массива, в которых они содержатся.
Итак, элементы нашего дека будут храниться в массиве.
Давайте разберёмся с тем, как они будут в нём расположены.
Очевидное решение — располагать элементы дека так, чтобы их индексы всегда возрастали по направлению от головы к хвосту. Но в этом случае возникает проблема. Как быть, если нужно добавить элемент в голову дека, но элемент массива с индексом 0 уже занят, хотя при этом свободны элементы массива, располагающиеся «за хвостом»? Один из вариантов — сдвинуть все элементы дека в сторону хвоста, чтобы освободить один или несколько элементов массива в его начале (разумеется, места может не оказаться не в начале массива, а в конце, тогда сдвигать элементы дека придётся в сторону головы).
Но этот вариант не лучшим образом скажется на производительности, особенно, если к обоим концам дека постоянно применяются операции вставки и удаления.
Гораздо более разумным представляется решение «закольцевать» массив.
Что такое «закольцованный» массив? Это массив, для которого введены следующим образом термины «предыдущий элемент» и «следующий элемент». Если индекс одного элемента на единицу превышает индекс другого, то первый элемент по отношению ко второму называется «следующим», а второй по отношению к первому — «предыдущим». Помимо этого, элемент с нулевым индексом называется «следующим» по отношению к элементу с максимальным индексом, а последний называется «предшествующим» по отношению к элементу с нулевым индексом.
Таким образом, у каждого без исключения элемента закольцованного массива имеется как предыдущий элемент, так и следующий.
А принцип добавления элементов дека в массив будет таким. При вставке в хвост мы помещаем элемент дека в элемент массива, следующий за элементом, в котором содержится «старый» хвостовой элемент. А при вставке в голову помещаем элемент дека в элемент массива, предшествующий элементу, в котором хранится «старый» головной элемент.
Таким образом, если элемент массива с нулевым (максимальным) индексом занят, то при вставке в голову (в хвост) элемент дека помещается в элемент массива с максимальным (нулевым) индексом. Такой подход гарантирует, что всегда, когда в массиве имеются свободные элементы, допустимы операции вставки как в голову, так и в хвост.
Заметим, что индекс элемента массива, содержащего головной элемент дека, может превосходить индекс элемента массива, содержащего хвостовой элемент дека (и наоборот). Индексы могут и совпадать; этот случай соответствует наличию в деке ровно одного элемента.
Что ж, информации из этого раздела вполне хватит для того, чтобы приступить к написанию программы. Приступим!
Структура программы
Программа будет состоять из трёх файлов. Сам дек будет реализован в файлах deq.h и deq.c. В третьем файле test.c будут располагаться функции, предназначенные для тестирования дека.
В файле deq.h будут описаны типы, необходимые для работы дека, и прототипы функций, реализующих операции, применяемые к деку. Реализации функций будут содержаться в файле deq.c. Таким образом. эти 2 файла будут составлять библиотеку для работы с деком.
К файлу deq.c будет подключён единственный заголовочный файл:
Типы el_type и deq
elements — это массив, в котором будут храниться элементы дека. Как мы видим, его размер неизвестен на этапе компиляции (об этом свидетельствуют пустые квадратные скобки). Размер будет задаваться непосредственно в ходе создания дека. Использование такого поля принуждает нас к динамическому созданию объектов типа deq и управлению ими через указатели (при автоматическом создании экземпляров этой структуры память для массива elements выделена не будет).
size — это размер массива elements ; его можно рассматривать как ёмкость или размер нашего дека.
count — количество элементов, хранящихся в деке.
Создание дека
Функция принимает в качестве параметра размер дека и, в случае, если размер отличен от нуля, пытается динамически создать дек заданного размера. Если размер равен нулю или память динамически выделить не удалось, функция возвращает нулевой адрес. В противном случае поля созданного дека инициализируются начальными значениями, поле чего адрес дека возвращается в вызывающую функцию.
Операции вставки элементов в дек
Функция принимает в качестве параметров адрес дека и значение вставляемого элемента. Она вставляет элемент в конец дека и возвращает адрес дека, т. е. значение 1-го параметра. Обратите внимание на то, что если в момент вызова функции дек пуст, то новый элемент помещается в нулевой элемент массива elements (см. стр. 9-10). В противном случае добавление элемента происходит в соответствии с принципом, описанном в разделе «Основная идея» (см. стр. 4-8 и 11).
Операции удаления элементов из дека
Итак, все обязательные операции реализованы. Но для комфортной работы с деком могут понадобиться и другие операции — необязательные. Мы их тоже рассмотрим.
Получение информации о состоянии дека
Получение крайних элементов без удаления их из дека
Следующие 2 функции принимают в качестве параметра адрес дека и возвращают хвостовой и головной элементы дека соответственно. При этом сами элементы из дека не удаляются.
Перебор элементов дека с помощью итератора
Предположим, что мы хотим распечатать содержимое дека, не удаляя из него элементы. Как быть?
Один из возможных способов — написать специальную функцию, перебирающую элементы дека и выводящую каждый из них на печать. Однако, поскольку наш дек универсален (чтобы перейти от одного типа элементов, хранящихся в деке, к другому, нужно лишь изменить этот тип в заголовочном файле), мы не можем помещать в библиотеку для работы с деком функции, выводящие на печать элементы конкретных типов. Значит, функция печати элемента должна быть создана вне библиотеки, а указатель на неё должен быть передан функции, печатающий содержимое всего дека.
Итератор — это объект, обращаясь к которому с помощью соответствующих функций, можно перебирать элементы некоторой коллекции, за которой этот итератор «закреплён» (используют даже словосочетание «итератор коллекции»). Дек как раз и является частным случаем коллекции элементов.
Поле deq итератора будет содержать адрес дека, за которым данный итератор закреплён. В поле index должен храниться индекс элемента массива, в котором находится некоторый элемент дека, который мы назовём «текущим».
Функция get_iterator() возвращает значение созданного итератора.
Функция next() принимает адрес итератора и возвращает элемент дека, связанного с этим итератором, который на момент вызова функции был для итератора текущим. Но перед возвратом значения функция делает текущим следующий элемент дека. Другими словами, функция заменяет значение поля index итератора индексом элемента массива, который следует за тем элементом, чей индекс содержался в поле до этого (стр. 7-9). Разумеется, мы говорим о массиве, в котором содержатся элементы дека. Принцип получения индекса следующего элемента был описан в разделе «Основная идея».
А вот код функции prev() :
Метод перебора коллекции с помощью итератора более гибок чем тот метод, который рассматривался в начале раздела. Благодаря первому мы получаем доступ ко всем элементам коллекции, поэтому можем обрабатывать любые из них произвольным образом. Всё, что мы можем сделать с помощью второго метода — это лишь вывести стазу все элементы (в прямом или обратном порядке) на печать.
Важное замечание
Никаких проверок значений фактических аргументов в упомянутых функциях не предусмотрено, поэтому корректность данных значений должна контролироваться вызывающими функциями. Такой подход позволяет немного сэкономить время работы функций, предназначенных для работы с деком.
Тестирование построенных функций
Для тестирования созданных нами функций будем использовать файл test.c. Подключим к нему заголовочные файлы, один из которых — созданный файл deq.h:
Теперь добавим в файл тестирующую функцию test1() :
В функции test1() задействованы все функции, созданные нами ранее.
Сначала динамически создаём дек, рассчитанный на 10 элементов (стр. 3). Далее вставляем в дек элементы, до тех пор, пока он не окажется заполненным (стр. 4-18). Вставляемые создаются генератором псевдослучайных чисел, причём нечётные числа добавляются в хвост дека, а чётные — в голову.
Далее с помощью итератора перебираем и печатаем все элементы дека в прямом направлении (от головы к хвосту) (стр. 19-22), а затем — в обратном (стр. 24-26).
Выводим на печать сначала головной элемент (стр. 28), а затем — хвостовой (стр. 29). Далее удаляем все элементы из дека и выводим их на печать (стр. 30-37). Выбор части дека, из которой удаляется очередной элемент (хвост или голова) происходит псевдослучайным образом.
Заметим, что строка 30 семантически эквивалентна следующей строке:
По окончании работы функции удаляем дек (стр. 38).
Запуск программы может привести, например, к следующему консольному выводу:
Изменение размера дека
В ходе работы с деком может возникнуть ситуация, при которой дек уже полон, но требуется добавить в него элементы. А может случиться так, что в деке очень много свободных мест и необходимо уменьшить его размер, чтобы освободить память.
Функция resize() принимает в качестве первого параметра адрес дека, а в качестве второго — желаемый размер дека. Если последний совпадает с размером дека, то функция возвращает его адрес. Если второй параметр не является положительным, то функция возвращает нулевой адрес. В остальных случаях функция пытается создать новый дек желаемого размера.
В случае удачи функция копирует в новый дек наибольшее возможное число элементов старого дека (если количество элементов старого дека превышает размер нового, то в новый дек попадают только первые элементы старого; другими словами, от старого «отрезается» хвост). Затем старый дек уничтожается, а адрес нового возвращается в вызывающую функцию. А в случае неудачи функция возвращает нулевой адрес.
В строках 4-7 обрабатываются ситуации, не требующие создания нового дека. В строке 8 пытаемся создать новый дек; в случае неудачи возвращаем нулевой адрес (стр. 9-10). А в случае удачи заполняем поля созданного объекта (см. стр. 11-14).
Обратите внимание на то, что головной элемент теперь будет храниться в элементе массива с индексом 0 (стр. 13). А также на то, что количество элементов, содержащихся в новом деке вычисляется как наименьшее из двух чисел. Первое из них — это количество элементов, находящихся в старом деке, а второе — это размер нового дека (стр. 12).
В противном случае перебор элементов дека, подлежащих копированию, в направлении от головы к хвосту уже не будет соответствовать плавному возрастанию их индексов (оно нарушится при переходе от элемента дека с наибольшем индексом к элементу с нулевым индексом). На этот раз копируем элементы в 2 приёма: часть из них из конца массива старого дека (стр. 20), а часть — из начала (стр. 21).
Однако в обоих случаях скопированные элементы дека будут располагаться в новом массиве так, что головной будет иметь нулевой индекс, а каждый следующий элемент будет иметь индекс, на единицу превышающий индекс предыдущего.
Итак, новый дек сформирован. Остаётся удалить старый (стр. 23) и вернуть индекс нового (стр. 24).
Тестирование функции resize()
Создаём дек на 7 элементов (стр. 3), заполняем его элементами (стр. 4-5) и выводим его содержимое на печать (стр. 6-9). Затем увеличиваем размер дека до 14 (стр. 11), вставляем в дек ещё 7 элементов (стр. 12-13) и снова печатаем содержимое (стр. 14-17). Далее уменьшаем размер дека до 10 (стр. 19) и распечатываем его (стр. 20-23). Наконец, снова уменьшаем размер дека, на этот раз, до 5 (стр. 25) и выводим все его элементы на печать (стр. 27-29). Не забываем в конце удалить дек (стр. 30).
Для вызова функции test2() изменим немного функцию main() :
Запуск программы приводит к следующему выводу на консоль:
Как мы видим, программа работает корректно.
Содержимое файла deq.h
Мы приводили ранее различные фрагменты файла deq.h, но так и не опубликовали находящиеся в нём прототипы библиотечных функций. Ниже содержимое этого файла приведено полностью.
Несложно подсчитать количество библиотечных функций, предназначенных для работы с деком. Их 13.
Заключение
Итак, мы построили библиотеку для работы с деком. В неё входят функции, реализующие как обязательные операции, так и ряд необязательных, но весьма полезных операций. Что можно улучшить?
Можно сделать библиотеку более «интеллектуальной», если предусмотреть возможность автоматического регулирования размера дека. В рамках данного подхода функции вставки, в случае попытки добавления элементов в заполненный дек, «сами» увеличивают размер дека (разумеется, с запасом). Функции удаления элементов, напротив, уменьшают размер дека, если в нём обнаруживается большое количество свободных мест.