Что такое дек в программировании

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

Структура данных — тип организации данных, позволяющий использовать эффективный доступ к модификации данных. Например, массив с константным размером является простейшей структурой данных. В данной статье мы рассмотрим несколько простейших структур данных: стек, очередь и дек.

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

В стандартной библиотеке С++ определен класс stack. Ниже приведен код, который реализует некоторые методы данного класса.

Очередь

Очередь (queue) — это структура данных, которая построена по принципу LILO (last in — last out: последним пришел — последним вышел). В C++ уже есть готовый STL контейнер — queue. В очереди, если вы добавите элемент, который вошел самый первый, то он выйдет тоже самым первым. Получается, если вы добавите 4 элемента, то первый добавленный элемент выйдет первым. Для того, чтобы лучше понять принцип очереди, можно представить себе очередь в магазине. Чтобы вас обслужили, требуется, чтобы обслужили всех человек, которые находятся впереди вас. Важное замечание — в очереди невозможно обратиться к определенному элементу.

Дек (deque) — это сокращенная фраза «double-ended-queue», что, в переводе с английского, означает — двусторонняя очередь. Контейнер дек похож на vector, разница состоит лишь в том, что в деках динамический массив открыт с двух сторон. Это и позволяет очень быстро добавлять новые элементы как в конец, так и в начало контейнера. В векторах элементы можно добавлять лишь в конец массива.

В приведенном выше коде мы создаем дек d и добавляем число 5 в конец, а число 1 — в начало. Затем мы удаляем последний элемент. Вывод очевиден — это число 1.

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

Деки в языке С++

Что же такое Дек? Дек (deque) — это сокращенная фраза «double-ended-queue», что, в переводе с английского, означает — двусторонняя очередь. Контейнер Дек очень похож на контейнер — Вектор, также как и Вектора, Деки являются динамическими массивами. Разница между Вектором и Деком состоит лишь в том, что в деках динамический массив открыт с двух сторон. Это и позволяет очень быстро добавлять новые элементы как в конец так и в начало контейнера. В векторах элементы можно добавлять лишь в конец массива.
Итак, чтобы использовать дек, необходимо подключить заголовочный файл — <deque> :

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

Как я и говорил, чтобы использовать деки, нужно подключить специальный заголовочный файл, это сделано в строке 2. Кроме того, у нас подключен заголовок итераторов — <iterator> в строке 3. В статье о векторах, я говорил, что он нужен, для вывода элементов контейнера на экран, в строке 23. В 12-й строке мы объявили дек, размер которого указывает пользователь. Строки 16-18 должны быть нам понятны, тут мы просто инициализируем элементы дека.

В строке 21, у нас есть проверка, которая выполняется с использованием функции empty() , то есть тут проверяется пустой ли контейнер или нет. Если — нет, то элементы дека выводятся на экран, в противном случае не выводятся на экран. Эта проверка по большому счету тут и не нужна, так как при такой организации логики программы, дек не будет пустым. Просто показал вам, что есть такой метод, если есть необходимость — обязательно пользуйтесь им.

В строке 23 выполняется вывод элементов контейнера на экран, первый и второй параметры — это итераторы нашего дека, которые указывают на начало и конец контейнера. То есть нам же нужно вывести все элементы, поэтому итераторы захватывают все элементы. Третий параметр — это итератор потока вывода, нужен для того, чтобы направить элементы контейнера в поток вывода. Так как элементы дека имеют тип данных char , то и в итераторе потока вывода, строка 23, также надо указывать char . Смотрим результат работы программы:

Обратите внимание на то, что в выводе все элементы дека разделены символом пробела, так как именно пробел был указан в качестве разделителя при выводе элементов дека в строке 23. В остальном, думаю, тут все предельно ясно!

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

Итак, начнем со строки 9, мы объявили пустой дек, он пустой потому, что мы даже не выделяли для него памяти, мы не задавали его размер. В строке 10 мы воспользовались методом push_back() чтобы в конец дека добавить новый элемент типа string . В строке 11 мы воспользовались функцией size() и узнали сколько элементов содержится внутри дека. Чем интересны строки 13-14? Вот как раз в этих строках реализована отличительная характеристика деков от векторов. Давайте по порядку, в строке 13 мы воспользовались методом push_front() , чтобы добавить в начало дека новый элемент, в векторах такое делать нельзя. Ну и в строке 14 мы вызвали известный уже нам метод push_back() .

Обратите внимание на то, что после выполнения операций добавления новых элементов в начало и в конец дека, размер дека увеличился, но это и не удивительно. Посмотрите на строки 23-24, мы воспользовались методами pop_front() и pop_back() , которые удаляют первый и последний элементы дека соответственно. После удаления элементов, размер дека тоже уменьшается.

Еще одна интересная функция — resize() , которая может изменять размер дека. Запомните, что resize() может только увеличивать размер, но не уменьшать. В программе, в строке 25, видно, что мы увеличили размер дека до шести элементов, и все новые элементы заполнили словом — empty . Причем стоит обратить внимание на то, что те элементы дека, которые находились в нем до изменения размера абсолютно не были затронуты, это можно увидеть в результате работы программы.

Хотел еще просто вам напомнить, что не обязательно использовать вывод элементов контейнера как в строке 20, если вам этот способ не удобен, можете использовать способ свойственный для обычных массивов, строки 28-30. Смотрим результат работы программы:

На этом этапе завершим вводную статью по декам, надеюсь, статья была для вас полезной.

Что такое дек в программировании

Дек (от англ. deque — double ended queue) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Эта структура поддерживает как FIFO, так и LIFO, поэтому на ней можно реализовать как стек, так и очередь. В первом случае нужно использовать только методы головы или хвоста, во втором — методы push и pop двух разных концов. Дек можно воспринимать как двустороннюю очередь. Он имеет следующие операции:

• [math] \mathtt [/math] — проверка на наличие элементов,
• [math] \mathtt [/math] (запись в конец) — операция вставки нового элемента в конец,
• [math] \mathtt [/math] (снятие с конца) — операция удаления конечного элемента,
• [math] \mathtt [/math] (запись в начало) — операция вставки нового элемента в начало,
• [math] \mathtt [/math] (снятие с начала) — операция удаления начального элемента.

Реализации

Дек расходует только [math]O(n)[/math] памяти, на хранение самих элементов.

Простая реализация

В данной реализации изначально [math] \mathtt [/math] и [math] \mathtt [/math] . Ключевые поля:

• [math]\mathtt[/math] — массив, с помощью которого реализуется дек, способный вместить не более [math]n[/math] элементов,
• [math]\mathtt[/math] — индекс головы дека,
• [math]\mathtt[/math] — индекс хвоста.

Дек состоит из элементов [math]\mathtt [/math] . Если происходит максимум [math]\mathtt [/math] добавлений, то массив длины [math]\mathtt <2 \times n>[/math] может вместить в себя все добавленные элементы.

Циклический дек на массиве константной длины

Во всех циклических реализациях изначально присвоены следующие значения [math] \mathtt [/math] и [math] \mathtt [/math] . Ключевые поля:

• [math]\mathtt[/math] — массив, с помощью которого реализуется дек, способный вместить не более [math]n[/math] элементов,
• [math]\mathtt[/math] — индекс головы дека,
• [math]\mathtt[/math] — индекс хвоста.

Дек состоит из элементов [math]\mathtt [/math] или [math]\mathtt [/math] и [math]\mathtt [/math] . Всего он способен вместить не более [math]n[/math] элементов. В данной реализации учитывается переполнение и правильно обрабатывается изъятие из пустого дека. Недостатком является константная длина массива, хранящего элементы. Все операции выполняются за [math]O(1)[/math] .

Циклический дек на динамическом массиве

• [math]\mathtt[/math] — размер массива,
• [math]\mathtt[/math] — массив, в котором хранится дек,
• [math]\mathtt[/math] — временный массив, где хранятся элементы после перекопирования,
• [math]\mathtt[/math] — индекс головы дека,
• [math]\mathtt[/math] — индекс хвоста.

Дек состоит из элементов [math]\mathtt [/math] или [math]\mathtt [/math] и [math]\mathtt [/math] . Если реализовывать дек на динамическом массиве, то мы можем избежать ошибки переполнения. При выполнении операций [math]\mathtt[/math] и [math]\mathtt[/math] происходит проверка на переполнение и, если нужно, выделяется большее количество памяти под массив. Также происходит проверка на избыточность памяти, выделенной под дек при выполнении операций [math]\mathtt[/math] и [math]\mathtt[/math] . Если памяти под дек выделено в четыре раза больше размера дека, то массив сокращается в два раза. Для удобства выделим в отдельную функцию [math]\mathtt[/math] получение текущего размера дека.

На списке

• ListItem(data : T, next : ListItem, prev : ListItem) — конструктор,
• [math]\mathtt[/math] — ссылка на хвост,
• [math]\mathtt[/math] — ссылка на голову.

Дек очень просто реализуется на двусвязном списке. Он состоит из элементов [math]\mathtt [/math] . Элементы всегда добавляются либо в [math]\mathtt[/math] , либо в [math]\mathtt[/math] . В данной реализации не учитывается изъятие из пустого дека.

На двух стеках

• [math]\mathtt[/math] — ссылка на хвост,
• [math]\mathtt[/math] — ссылка на голову.

Храним два стека — [math]\mathtt[/math] и [math]\mathtt[/math] . Левый стек используем для операций [math]\mathtt[/math] и [math]\mathtt[/math] , правый — для [math]\mathtt[/math] и [math]\mathtt[/math] . Если мы хотим работать с левым стеком и при этом он оказывается пустым, то достаем нижнюю половину элементов из правого и кладем в левый, воспользовавшись при этом локальным стеком. Аналогично с правым стеком. Худшее время работы — [math]O(n)[/math] .

Воспользуемся методом предоплаты для доказательства. Достаточно доказать, что между двумя балансировками происходит достаточно амортизирующих их операций.

Вначале в обоих стеках пусто, поэтому они сбалансированы. Рассмотрим дек после очередной балансировки, будем использовать две монеты для операций [math]\mathtt[/math] и [math]\mathtt[/math] — одну для самой операции, а другую — в качестве резерва.

Алгоритмы и структуры данных для начинающих: стеки и очереди

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

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

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

Наиболее часто встречающаяся аналогия для объяснения стека — стопка тарелок. Вне зависимости от того, сколько тарелок в стопке, мы всегда можем снять верхнюю. Чистые тарелки точно так же кладутся на верх стопки, и мы всегда будем первой брать ту тарелку, которая была положена последней.

Если мы положим, например, красную тарелку, затем синюю, а затем зеленую, то сначала надо будет снять зеленую, потом синюю, и, наконец, красную. Главное, что надо запомнить — тарелки всегда ставятся и на верх стопки. Когда кто-то берет тарелку, он также снимает ее сверху. Получается, что тарелки разбираются в порядке, обратном тому, в котором ставились.

Теперь, когда мы понимаем, как работает стек, введем несколько терминов. Операция добавления элемента на стек называется «push», удаления — «pop». Последний добавленный элемент называется верхушкой стека, или «top», и его можно посмотреть с помощью операции «peek». Давайте теперь посмотрим на заготовку класса, реализующего стек.

Класс Stack

Класс Stack определяет методы Push , Pop , Peek для доступа к элементам и поле Count . В реализации мы будем использовать LinkedList<T> для хранения элементов.

Метод Push

• Поведение: Добавляет элемент на вершину стека.
• Сложность: O(1).

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

Метод Pop

• Поведение: Удаляет элемент с вершины стека и возвращает его. Если стек пустой, кидает InvalidOperationException .
• Сложность: O(1).

Push добавляет элементы в конец списка, поэтому забирать их будет также с конца. В случае, если список пуст, будет выбрасываться исключение.

Метод Peek

• Поведение: Возвращает верхний элемент стека, но не удаляет его. Если стек пустой, кидает InvalidOperationException .
• Сложность: O(1).

Метод Count

• Поведение: Возвращает количество элементов в стеке.
• Сложность: O(1).

Зачем нам знать, сколько элементов находится в стеке, если мы все равно не имеем к ним доступа? С помощью этого поля мы можем проверить, есть ли элементы на стеке или он пуст. Это очень полезно, учитывая, что метод Pop кидает исключение.

Пример: калькулятор в обратной польской записи

Классический пример использования стека — калькулятор в обратной польской, или постфиксной, записи. В ней оператор записывается после своих операндов. То есть, мы пишем:

Другими словами, вместо «4 + 2» мы запишем «4 2 +». Если вам интересно происхождение обратной польской записи и ее названия, вы можете узнать об этом на Википедии или в поисковике.

То, как вычисляется обратная польская запись и почему стек так полезен при ее использовании, хорошо видно из следующего алгоритма:

То есть, для выражения «4 2 +» действия будут следующие:

В конце на стеке окажется одно значение — 6.

Далее приводится полный код простого калькулятора, который считывает выражение (например, 4 2 + ) из консоли, разбивает входные данные по пробелам ( [«4», «2», «+»] ) и выполняет алгоритм вычисления. Вычисление продолжается до тех пор, пока не будет встречено слово quit .

Очередь

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

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

Класс Queue

Класс Queue , как и стек, будет реализован с помощью связного списка. Он будет предоставлять методы Enqueue для добавления элемента, Dequeue для удаления, Peek и Count . Как и класс Stack , он не будет реализовывать интерфейс ICollection<T> , поскольку это коллекции специального назначения.

Метод Enqueue

• Поведение: Добавляет элемент в очередь.
• Сложность: O(1).

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

Метод Dequeue

• Поведение: Удаляет первый помещенный элемент из очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Поскольку мы вставляем элементы в начало списка, убирать мы их будем с конца. Если список пуст, кидается исключение.

Метод Peek

• Поведение: Возвращает элемент, который вернет следующий вызов метода Dequeue . Очередь остается без изменений. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

Двусторонняя очередь

Двусторонняя очередь (Double-ended queue), или дек (Deque), расширяет поведение очереди. В дек можно добавлять или удалять элементы как с начала, так и с конца очереди. Такое поведение полезно во многих задачах, например, планирование выполнения потоков или реализация других структур данных. Позже мы рассмотрим вариант реализации стека с помощью двусторонней очереди.

Класс Deque

Класс Deque проще всего реализовать с помощью двусвязного списка. Он позволяет просматривать, удалять и добавлять элементы в начало и в конец списка. Основное отличие двусторонней очереди от обычной — методы Enqueue , Dequeue , и Peek разделены на пары для работы с обоими концами списка.

Метод EnqueueFirst

• Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst .
• Сложность: O(1).

Метод EnqueueLast

• Поведение: Добавляет элемент в конец очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueLast .
• Сложность: O(1).

Метод DequeueFirst

• Поведение: Удаляет элемент из начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод DequeueLast

• Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод PeekFirst

• Поведение: Возвращает элемент из начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод PeekLast

• Поведение: Возвращает элемент с конца очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

Пример: реализация стека

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

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

Тем не менее, реализация стека или очереди с помощью массива — непростая задача, но такая реализация двусторонней очереди и использование ее в качестве основы для других структур данных даст нам серьезный плюс к производительности и позволит повторно использовать код. Это снижает стоимость поддержки.

Позже мы посмотрим на вариант очереди с использованием массива, но сначала давайте взглянем на класс стека с использованием двусторонней очереди:

Заметьте, что вся обработка ошибок теперь лежит на классе Deque , и, кроме того, любая оптимизация очереди также отразится на стеке. Реализация обычной очереди на основе двусторонней настолько проста, что мы оставим ее читателю в качестве упражнения.

Хранение элементов в массиве

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

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

При создании очереди у нее внутри создается массив нулевой длины. Красные буквы «h» и «t» означают указатели _head и _tail соответственно.

Добавляем элемент в начало

Добавляем элемент в конец

Добавляем еще один элемент в начало

Обратите внимание: индекс «головы» очереди перескочил в начало списка. Теперь первый элемент, который будет возвращен при вызове метода DequeueFirst — 0 (индекс 3).

И еще один в конец

Массив заполнен, поэтому при добавлении элемента произойдет следующее:

• Алгорим роста определит размер нового массива.
• Элементы скопируются в новый массив с «головы» до «хвоста».
• Добавится новый элемент.

Добавляем значение в конец расширенного массива

Теперь посмотрим, что происходит при удалении элемента:

Удаляем элемент из начала

Удаляем элемент с конца

Ключевой момент: вне зависимости от вместимости или заполненности внутреннего массива, логически, содержимое очереди — элементы от «головы» до «хвоста» с учетом «закольцованности». Такое поведение также называется «кольцевым буфером».

Теперь давайте посмотрим на реализацию.

Класс Deque (с использованием массива)

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

Алгоритм роста

Когда свободное место во внутреннем массиве заканчивается, его необходимо увеличить, скопировать элементы и обновить указатели на «хвост» и «голову». Эта операция производится при необходимости во время добавления элемента. Параметр startingIndex используется, чтобы показать, сколько полей в начале необходимо оставить пустыми (в случае добавления в начало).

Обратите внимание на то, как извлекаются данные, когда приходится переходить в начало массива при проходе от «головы» к «хвосту».

Метод EnqueueFirst

• Поведение: Добавляет элемент в начало очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueFirst .
• Сложность: O(1) в большинстве случаев; O(n), когда нужно расширение массива.

Метод EnqueueLast

• Поведение: Добавляет элемент в конец очереди. Этот элемент будет взят из очереди следующим при вызове метода DequeueLast .
• Сложность: O(1) в большинстве случаев; O(n), когда нужно расширение массива.

Метод DequeueFirst

• Поведение: Удаляет элемент с начала очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод DequeueLast

• Поведение: Удаляет элемент с конца очереди и возвращает его. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод PeekFirst

• Поведение: Возвращает элемент с начала очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод PeekLast

• Поведение: Возвращает элемент с конца очереди, не изменяя ее. Если очередь пустая, кидает InvalidOperationException .
• Сложность: O(1).

Метод Count

• Поведение: Возвращает количество элементов в очереди или 0, если очередь пустая.
• Сложность: O(1).

Продолжение следует

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