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

Дек (двусторонняя очередь).

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

Число основных операций, выполняемых над стеком и очередью, как помнит читатель, равнялось трем: добавление элемента, удаление элемента, чтение элемента. При этом не указывалось место структуры данных, активное в момент их выполнения, поскольку ранее оно однозначно определялось свойствами (определением) самой структуры. Теперь, ввиду дека как обобщенного случая, для приведенных операций следует указать эту область. Разделив каждую из операций на две: одну применительно к «голове» дека, другую – его «хвосту», получим набор из шести операций:

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

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

Помимо самого массива потребуется указатель на последний элемент, назовем его last. Указатель на первый элемент не потребуется, поскольку дек будет представлять собой смещающуюся структуру, т. е. при добавлении нового элемента в начало, каждый из старых элементов сместиться на одну позицию вправо, уступив тем самым первому элементу ячейку с индексом 0 (в C++), следовательно, адрес первого элемента – константа.

Источник

Класс deque

Упорядочивает элементы заданного типа в линейном порядке и, подобно векторам, обеспечивает быстрый произвольный доступ к любому элементу и эффективную вставку и удаление в конце контейнера. Однако в отличие от объекта vector класс deque также поддерживает эффективную вставку и удаление в передней части контейнера.

Синтаксис

Параметры

Тип
Тип данных элементов, сохраняемых в объекте deque.

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

Комментарии

Выбор типа контейнера должен в общем случае производиться на основе типа поиска и вставки, который требуется приложению. Векторы должны быть предпочтительными контейнерами для управления последовательностью, когда произвольный доступ к любому элементу имеет уровень Premium, а вставки или удаления элементов требуются только в конце последовательности. Производительность контейнера list выше, если эффективные вставки и удаления (в константном времени) в любом расположении в последовательности имеют больший приоритет. Таким операциям в середине последовательности требуются копии элементов и присвоения, пропорциональные количеству элементов в последовательности (линейное время).

Перераспределение объекта deque происходит, когда функция-член должна вставить или удалить элементы последовательности:

Если элемент вставляется в пустую последовательность или элемент удаляется, чтобы оставить после себя пустую последовательность, то итераторы, ранее возвращенные begin и end, становятся недействительными.

Если элемент вставляется в первую позицию deque, то все итераторы, но не ссылки, которые определяют существующие элементы, становятся недействительными.

Если элемент вставляется в последнюю позицию очереди, то end и все итераторы, но не ссылки, которые определяют существующие элементы, становятся недействительными.

Если элемент удаляется в передней части объекта deque, только этот итератор и ссылки на удаленный элемент становятся недействительными.

Если последний элемент удаляется из конца объекта deque, только этот итератор последнего элемента и ссылки на удаленный элемент становятся недействительными.

В противном случае вставка или удаление элемента делает недействительными все итераторы и ссылки.

Члены

Конструкторы

Определения типов

Функции

Операторы

allocator_type

Тип, представляющий класс allocator для объекта deque.

Комментарии

Пример

assign

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

Параметры

Первая
Положение первого элемента в диапазоне элементов, копируемых из очереди аргументов.

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

Количество
Количество копий элемента, вставляемых в очередь.

Val
Значение элемента, вставляемого в очередь.

IList
Объект initializer_list, вставляемый в очередь.

Комментарии

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

Пример

Возвращает ссылку на элемент в заданном положении в очереди.

Параметры

pos
Нижний индекс (или номер позиции) элемента, на который включается ссылка в очереди.

Возвращаемое значение

Если значение POS превышает размер deque, вызывается исключение.

Комментарии

Пример

Назад

Возвращает ссылку на последний элемент очереди.

Возвращаемое значение

Последний элемент очереди. Если очередь пуста, возвращаемое значение не определено.

Комментарии

При компиляции с помощью _ITERATOR_DEBUG_LEVEL, для которого задано значение 1 или 2, возникнет ошибка времени выполнения при попытке доступа к элементу в пустой очереди. Дополнительные сведения см. в разделе Проверяемые итераторы.

Пример

begin

Возвращает итератор, адресующий первый элемент в очереди.

Возвращаемое значение

Итератор произвольного доступа, адресующий первый элемент в очереди или расположение после пустой очереди.

Комментарии

Пример

cbegin

Возвращаемое значение

Комментарии

Возвращаемое значение

Итератор произвольного доступа, который указывает на место сразу после конца диапазона.

Комментарии

cend используется для проверки того, прошел ли итератор конец диапазона.

clear

Стирает все элементы в очереди.

Пример

const_iterator

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

Комментарии

Тип const_iterator нельзя использовать для изменения значения элемента.

Пример

const_pointer

Предоставляет указатель на элемент const в очереди.

Комментарии

Тип const_pointer нельзя использовать для изменения значения элемента. Для доступа к элементу очереди чаще используется iterator.

const_reference

Тип, предоставляющий ссылку на const элемент, хранящийся в deque для чтения и выполнения const операций.

Комментарии

Тип const_reference нельзя использовать для изменения значения элемента.

Пример

const_reverse_iterator

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

Комментарии

Тип const_reverse_iterator не может изменять значение элемента и используется для последовательного прохождения через очередь в обратную сторону.

Пример

См. пример объявления и использования итератора в разделе rbegin.

crbegin

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

Возвращаемое значение

Константный обратный итератор произвольного доступа, указывающий на первый элемент в обращенном объекте deque или на элемент, который был последним в до обращения.

Комментарии

Пример

crend

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

Возвращаемое значение

Константный обратный итератор произвольного доступа, адресующий расположение после последнего элемента в обращенном объекте deque (расположение перед первым элементом в необращенной очереди).

Комментарии

Если возвращается значение crend (уменьшенное соответствующим образом), объект deque изменить нельзя.

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

Пример

deque

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

Параметры

Al
Класс распределителя для использования с данным объектом.

Количество
Количество элементов в создаваемой очереди.

Val
Значение элементов в создаваемой очереди.

Right
Очередь, для которой создаваемая очередь станет копией.

Первая
Положение первого элемента в диапазоне копируемых элементов.

Последняя
Положение первого элемента за пределами диапазона копируемых элементов.

IList
Копируемый initializer_list.

Комментарии

Все конструкторы хранят объект распределителя (Al) и инициализируют deque.

Первые два конструктора указывают пустую начальную deque; второй также указывает тип распределителя ( _Al ) для использования.

Шестой конструктор задает копию правогоdeque.

Седьмой и восьмой конструкторы копируют диапазон [First, Last) очереди.

Седьмой конструктор перемещает правоdeque.

Восьмой конструктор копирует содержимое initializer_list.

Ни один из конструкторов не выполняет промежуточные перераспределения.

Пример

difference_type

Тип, предоставляющий разницу между двумя итераторами, ссылающимися на элементы в одной и той же очереди.

Комментарии

difference_type также можно описать как число элементов между двумя указателями.

Пример

emplace

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

Параметры

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

Возвращаемое значение

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

Комментарии

Пример

emplace_back

Добавляет элемент, созданный на месте, в конец очереди.

Параметры

Val
Элемент, добавляемый в конец объекта deque.

Пример

emplace_front

Добавляет элемент, созданный на месте, в конец очереди.

Параметры

Val
Элемент, добавляемый в начало deque.

Пример

empty

Проверяет, пуста ли очередь.

Возвращаемое значение

true значение, если deque пусто; false Если deque не является пустым.

Пример

Возвращает итератор, адресующий расположение за последним элементом в очереди.

Возвращаемое значение

Возвращает итератор произвольного доступа, адресующий расположение за последним элементом в очереди. Если очередь пуста, то deque::end == deque::begin.

Комментарии

end используется для проверки того, достиг ли итератор конца его deque.

Пример

erase

Удаляет элемент или диапазон элементов с указанных позиций в очереди.

Параметры

_Where
Положение элемента, удаляемого из очереди.

first
Положение первого элемента, удаленного из очереди.

last
Положение после последнего элемента, удаленного из очереди.

Возвращаемое значение

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

Комментарии

erase никогда не создает исключений.

Пример

лицевая камера

Возвращает ссылку на первый элемент в очереди.

Возвращаемое значение

Если очередь пуста, возвращаемое значение не определено.

Комментарии

При компиляции с помощью _ITERATOR_DEBUG_LEVEL, для которого задано значение 1 или 2, возникнет ошибка времени выполнения при попытке доступа к элементу в пустой очереди. Дополнительные сведения см. в разделе Проверяемые итераторы.

Пример

get_allocator

Возвращает копию объекта распределителя, использованного для создания очереди.

Возвращаемое значение

Распределитель, используемый очередью.

Комментарии

Распределители для класса очереди определяют, как этот класс управляет хранилищем. Распределителей по умолчанию в классах контейнеров стандартной библиотеки C++ достаточно для большинства задач программирования. Написание и использование собственного класса распределителя требует расширенных навыков работы с C++.

Пример

insert

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

Параметры

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

Val
Значение элемента, вставляемого в очередь.

Количество
Количество элементов, вставляемых в очередь.

Первая
Положение первого элемента в диапазоне элементов в копируемой очереди аргументов.

Последняя
Положение первого элемента за пределами диапазона элементов в копируемой очереди аргументов.

IList
Объект initializer_list, содержащий вставляемые элементы.

Возвращаемое значение

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

Комментарии

Любая операция вставки может быть ресурсоемкой.

iterator

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

Комментарии

Тип iterator можно использовать для изменения значения элемента.

Пример

max_size

Возвращает максимальную длину очереди.

Возвращаемое значение

Максимально возможная длина очереди.

Пример

operator[]

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

Параметры

pos
Положение элемента очереди, на который должна быть ссылка.

Возвращаемое значение

Ссылка на элемент, позиция которого указана в аргументе. Если заданная позиция больше размера очереди, результат не определен.

Комментарии

При компиляции с помощью _ITERATOR_DEBUG_LEVEL, для которого задано значение 1 или 2, возникнет ошибка времени выполнения при попытке доступа к элементу за пределами очереди. Дополнительные сведения см. в разделе Проверяемые итераторы.

Пример

operator=

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

Параметры

Правильно
Очередь, предоставляющая новое содержимое.

Комментарии

Первое переопределение копирует элементы в этот deque с правогокрая, источника назначения. Второе переопределение перемещает элементы в deque из right.

Элементы, содержащиеся в этой очереди перед выполнением оператора, удаляются.

Пример

указатель

Предоставляет указатель на элемент в объекте deque.

Комментарии

Тип pointer можно использовать для изменения значения элемента. Для доступа к элементу очереди чаще используется iterator.

pop_back

Удаляет элемент в конце очереди.

Комментарии

Последний элемент не должен быть пустым. pop_back никогда не создает исключений.

Пример

pop_front

Удаляет элемент в начале очереди.

Комментарии

Первый элемент не должен быть пустым. pop_front никогда не создает исключений.

Пример

push_back

Добавляет элемент в конец очереди.

Параметры

Val
Элемент, добавляемый в конец очереди.

Комментарии

При создании исключения очередь не изменяется, а исключение создается снова.

push_front

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

Параметры

Val
Элемент, добавляемый в начало очереди.

Комментарии

При создании исключения очередь не изменяется, а исключение создается снова.

Пример

rbegin

Возвращает итератор, указывающий на первый элемент в обращенной очереди.

Возвращаемое значение

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

Комментарии

rbegin используется с обращенной очередью точно так же, как rbegin используется с очередью.

rbegin можно использовать для последовательного прохождения по очереди в обратную сторону.

Пример

reference

Тип, предоставляющий ссылку на элемент, хранящийся в очереди.

Пример

Возвращает итератор, адресующий расположение после последнего элемента в обращенной очереди.

Возвращаемое значение

Обратный итератор произвольного доступа, адресующий расположение после последнего элемента в обращенной очереди (расположение перед первым элементом в необращенной очереди).

Комментарии

rend используется с обращенной очередью точно так же, как rend используется с очередью.

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

Пример

изменить размер

Указывает новый размер очереди.

Параметры

_Newsize
Новый размер очереди.

Val
Значение новых элементов, добавляемых в очередь, если новый размер больше исходного. Если значение не задано, новым элементам назначается значение по умолчанию для класса.

Комментарии

Если размер deque меньше запрошенного размера, _Newsizeэлементы добавляются в deque до тех пор, пока не достигнет запрошенного размера.

Если размер deque больше запрошенного размера, элементы, ближайшие к концу deque, удаляются до тех пор, пока deque не достигнет размера _Newsize.

Если текущий размер очереди совпадает с запрошенным, никакие действия не выполняются.

size — это текущий размер очереди.

Пример

reverse_iterator

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

Комментарии

Тип reverse_iterator используется для итерации по очереди.

Пример

См. пример для rbegin.

shrink_to_fit

Удаляет лишнюю емкость.

Комментарии

Пример

Возвращает число элементов в очереди.

Возвращаемое значение

Текущая длина очереди.

Пример

size_type

Тип, который подсчитывает количество элементов в очереди.

Пример

Меняет местами элементы двух объектов deque.

Параметры

слева
Объект deque, элементы которого должны быть заменены элементами deque right.

Пример

value_type

Тип, представляющий тип данных, хранящихся в очереди.

Комментарии

Источник

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

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

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

27–29 декабря, Онлайн, Беcплатно

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

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

Теперь, когда мы понимаем, как работает стек, введем несколько терминов. Операция добавления элемента на стек называется «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

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

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

Источник