Deque c что это

Deque c что это

Деком (англ. deque, от double-ended queue) называется структура данных, которая позволяет добавлять элементы и в конец, и в начало, а также удалять элементы из конца и из начала. Все эти операции реализованы за O(1), то есть выполняются быстро.

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

Объявляется дек, например, целых чисел так:

Дек поддерживает следущие методы:

Название метода	Описание
size()	Возвращает размер дека
empty()	Возвращает true, если дек пуста, или false, если непуст
clear()	Очищает дек
front()	Возвращает значение первого элемента в деке
back()	Возвращает значение последнего элемента в деке
pop_front()	Удаляет первый элемент из дека, не возвращает значение
pop_back()	Удаляет последний элемент из дека, не возвращает значение
push_front(elem)	Добавляет новый элемент elem в начало дека
push_back(elem)	Добавляет новый элемент elem в конец дека

У дека есть много общего с векторами. Например, к элементам дека можно обращаться по индексу, при помощи [i] или метода at(i). Эти обращения выполняются быстро — реализация дека насколько хитра, что можно быстро добавлять элементы в начало и в конец, а также быстро обращаться к элементу по его номеру. У дека, как и у вектора, есть методы erase, insert и resize, но они работают за линейное время.

Также с объектами класса deque допустимы операции =, ==, !=, , =.

Подробней о контейнере deque можно прочитать в документации.

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

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

#include

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

#include #include // подключаем заголовочный файл деков #include // заголовок итераторов using namespace std; int main() < int dequeSize = 0; cout > dequeSize; deque myDeque(dequeSize); // создаем дек и резервируем для него память cout > myDeque[i]; > cout << "\nВведенный дек: "; if (!myDeque.empty()) < // если дек не пуст // вывод на экран элементов дека copy( myDeque.begin(), myDeque.end(), ostream_iterator(cout," ") ); // вывод на экран элементов дека > return 0; >

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

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

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

CppStudio.com

Введите размер дека: 20 Введите элементы дека: Metallica - I disappear Введенный дек: M e t a l l i c a - I d i s a p p e a r

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

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

#include #include // подключаем заголовочный файл деков #include // заголовок итераторов #include // заголовочный файл для работы со строками типа string using namespace std; int main() < dequemyDeque; // создаем пустой дек типа string myDeque.push_back(string("Winter is")); // добавили в дек один элемент типа string cout << "Количество элементов в деке: " << myDeque.size() << endl; myDeque.push_front("Game of Thrones:"); // добавили в начало дека еще один элемент myDeque.push_back("coming!"); // добавили в конец дека элемент "coming!" cout << "Количество элементов в деке изменилось, теперь оно = " << myDeque.size() << endl; cout << "\nВведенный дек: "; if (!myDeque.empty()) < // если дек не пуст // вывод на экран элементов дека copy( myDeque.begin(), myDeque.end(), ostream_iterator(cout," ") ); // вывод на экран элементов дека > myDeque.pop_front(); // удалили первый элемент myDeque.pop_back(); // удалили второй элемент myDeque.resize(6,"empty"); // увеличиваем размер дека до 6 элементов, новые элементы заполняются словом "empty" cout return 0; >

Итак, начнем со строки 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. Смотрим результат работы программы:

CppStudio.com

Количество элементов в деке: 1 Количество элементов в деке изменилось, теперь оно = 3 Введенный дек: Game of Thrones: Winter is coming! Были удалены первый и последний элементы дека, вот что осталось: Winter is empty empty empty empty empty

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

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

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

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

• добавление элемента в начало;
• добавление элемента в конец;
• удаление первого элемента;
• удаление последнего элемента;
• чтение первого элемента;
• чтение последнего элемента.

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

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

• Creation – обнуляет указатель на конец, так сказать создает дек;
• Full – проверяет дек на наличие элементов;
• AddL – добавляет элемент в начало;
• AddR – добавляет элемент в конец;
• DeleteL – удаляет первый элемент;
• DeleteR – удаляет последний элемент;
• OutputL – выводит первый элемент;
• OutputR – выводит последний элемент;
• Size – выводит количество элементов дека;

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

Программная реализация дека на основе массива:

#include "stdafx.h" #include using namespace std; const int N=5; //размер дека struct Deque < int data[N]; //массив данных int last; //указатель на конец >; void Creation(Deque *D) //создание дека < D->last=0; > bool Full(Deque *D) //проверка дека на пустоту < if (D->last==0) return true; else return false; > void AddL(Deque *D) //добавление элемента в начало < if (D->last==N) < coutint value; cout "; cin>>value; for (int i=D->last; i>0; i--) D->data[i]=D->data[i-1]; D->data[0]=value; D->last++; cout void AddR(Deque *D) //добавление элемента в конец < if (D->last==N) < coutint value; cout "; cin>>value; D->data[D->last++]=value; cout void DeleteL(Deque *D) //удаление первого элемента < for (int i=0; ilast; i++) //смещение элементов D->data[i]=D->data[i+1]; D->last--; > void DeleteR(Deque *D) //удаление последнего элемента < D->last--; > int OutputL(Deque *D) //вывод первого элемента < return D->data[0]; > int OutputR(Deque *D) //вывод последнего элемента < return D->data[D->last-1]; > int Size(Deque *D) //размер дека < return D->last; > //****************************************** int main() //главная функция < setlocale(LC_ALL,"Rus"); Deque D; Creation(&D); char number; do < cout"; cin>>number; switch (number) < case '1': AddL(&D); break; //----------------------------------------------- case '2': AddR(&D); break; //----------------------------------------------- case '3': if (Full(&D)) coutbreak; //----------------------------------------------- case '4': if (Full(&D)) cout break; //----------------------------------------------- case '5': if (Full(&D)) cout > while(number!='0'); system("pause"); >

Двусторонняя очередь, реализованная таким способом, имеет два существенных недостатка: ограниченный размер и линейное время. Последнее касается добавления элемента в начало или извлечения его оттуда, а именно операциям AddL и DeleteL необходимо N перестановок, где N – число элементов в деке.

Стандартная библиотека C++ предоставляет специальные средства работы с двусторонней очередью. Для этого в ней предусмотрен контейнер deque. Он позволяет за O(1) осуществлять вставку и удаление элементов. Методы контейнера deque:

• front – возврат значения первого элемента;
• back – возврат значения последнего элемента;
• push_front – добавление элемента в начало;
• push_back – добавление элемента в конец;
• pop_front – удаление первого элемента;
• pop_back – удаление последнего элемента;
• size – возврат числа элементов дека;
• clear – очистка дека.

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

#include "stdafx.h" #include #include using namespace std; int main() //главная функция < setlocale(LC_ALL,"Rus"); dequeD; //создание дека D размером 5 deque::iterator out; int value; char number; do < cout"; cin>>number; switch (number) < case '1': cout"; cin>>value; D.push_front(value); cout <>value; D.push_back(value); cout break; //----------------------------------------------- case '4': if (D.empty()) cout break; //----------------------------------------------- case '5': if (D.empty()) cout break; //----------------------------------------------- case '6': if (D.empty()) cout break; //----------------------------------------------- case '7': if (D.empty()) cout > while(number!='0'); system("pause"); >

Deque c что это

Deque представляет двухстороннюю очередь. Для использования данного контейнера нужно подключить заголовочный файл deque .

Способы создания двухсторонней очереди:

std::deque deque1; // пустая очередь std::deque deque2(5); // deque2 состоит из 5 чисел, каждый элемент имеет значение по умолчанию std::deque deque(5, 2); // deque3 состоит из 5 чисел, каждое число равно 2 std::deque deque4< 1, 2, 4, 5 >; // deque4 состоит из чисел 1, 2, 4, 5 std::deque deque5 = < 1, 2, 3, 5 >; // deque5 состоит из чисел 1, 2, 3, 5 std::deque deque6(< 1, 2, 3, 4, 5 >); // deque6 состоит из чисел 1, 2, 3, 4, 5 std::deque deque7(deque4); // deque7 - копия очереди deque4 std::deque deque8 = deque7; // deque8 - копия очереди deque7

Получение элементов очереди

Для получения элементов очереди можно использовать операцию [] и ряд функций:

• [index] : получение элемента по индексу
• at(index) : возращает элемент по индексу
• front() : возвращает первый элемент
• back() : возвращает последний элемент

#include #include int main() < std::dequenumbers < 1, 2, 3, 4, 5 >; int first = numbers.front(); // 1 int last = numbers.back(); // 5 int second = numbers[1]; // 2 int third = numbers.at(2); // 3 std::cout 

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

std::deque numbers < 1, 2, 3, 4, 5 >; int eighth = numbers[7];

В этом случае использование функции at() является более предпочтительным, так как при обращении по некорректному индексу она генерирует исключение out_of_range :

#include #include int main() < std::dequenumbers < 1, 2, 3, 4, 5>; try < int n < numbers.at(7) >; std::cout catch (const std::out_of_range&) < std::cout >

Также в цикле или с помощью итераторов можно перебрать элементы контейнера:

#include #include int main() < std::dequenumbers < 1, 2, 3, 4, 5 >; for (int n : numbers) std::cout ; i

Размер очереди

Чтобы узнать размер очереди, можно использовать функцию size() . А функция empty() позволяет узнать, содержит ли очередь элементы. Она возвращает значение true, если в очереди есть элементы:

std::deque numbers < 1, 2, 3, 4, 5 >; if (numbers.empty()) < std::cout else < int n ; std::cout

Функция resize() позволяет изменить размер очереди. Эта функция имеет две формы:

• resize(n) : оставляет в очереди n первых элементов. Если deque содержит больше элементов, то размер контейнера усекается до первых n элементов. Если размер очереди меньше n, то добавляются недостающие элементы и инициализируются значением по умолчанию
• resize(n, value) : также оставляет в очереди n первых элементов. Если размер очереди меньше n, то добавляются недостающие элементы со значением value

std::deque numbers < 1, 2, 3, 4, 5, 6 >; numbers.resize(4); // оставляем первые четыре элемента — numbers = numbers.resize(6, 8); // numbers =

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

Изменение элементов очереди

Функция assign() позволяет заменить все элементы очереди определенным набором. Она имеет следующие формы:

• assign(il) : заменяет содержимое контейнера элементами из списка инициализации il
• assign(n, value) : заменяет содержимое контейнера n элементами, которые имеют значение value
• assign(begin, end) : заменяет содержимое контейнера элементами из диапазона, на начало и конец которого указывают итераторы begin и end

std::deque numbers < 1, 2, 3, 4, 5 >; numbers.assign(< 21, 22, 23, 24, 25 >); // numbers = < 21, 22, 23, 24, 25 >numbers.assign(4, 3); // numbers = std::deque values < 6, 7, 8, 9, 10, 11 >; auto start = values.begin() + 2; // итератор указывает на третий элемент auto end = values.end(); // итератор указывает на последний элемент numbers.assign(start, end); // numbers =

Функция swap() обменивает значениями две очереди:

std::deque deque1 < 1, 2, 3, 4, 5 >; std::deque deque2 < 6, 7, 8, 9>; deque1.swap(deque2); // deque1 = < 6, 7, 8, 9>;

Добавление элементов

Чтобы добавить элементы в очередь deque, можно применять ряд функций:

• push_back(val) : добавляет значение val в конец очереди
• push_front(val) : добавляет значение val в начало очереди
• emplace_back(val) : добавляет значение val в конец очереди
• emplace_front(val) : добавляет значение val в начало очереди
• emplace(pos, val) : вставляет элемент val на позицию, на которую указывает итератор pos. Возвращает итератор на добавленный элемент
• insert(pos, val) : вставляет элемент val на позицию, на которую указывает итератор pos, аналогично функции emplace. Возвращает итератор на добавленный элемент
• insert(pos, n, val) : вставляет n элементов val начиная с позиции, на которую указывает итератор pos. Возвращает итератор на первый добавленный элемент. Если n = 0, то возвращается итератор pos.
• insert(pos, begin, end) : вставляет начиная с позиции, на которую указывает итератор pos, элементы из другого контейнера из диапазона между итераторами begin и end. Возвращает итератор на первый добавленный элемент. Если между итераторами begin и end нет элементов, то возвращается итератор pos.
• insert(pos, values) : вставляет список значений values начиная с позиции, на которую указывает итератор pos. Возвращает итератор на первый добавленный элемент. Если values не содержит элементов, то возвращается итератор pos.

Функции push_back() , push_front() , emplace_back() и emplace_front() :

std::deque numbers < 1, 2, 3, 4, 5 >; numbers.push_back(6); // < 1, 2, 3, 4, 5, 6 >numbers.push_front(0); // < 0, 1, 2, 3, 4, 5, 6 >numbers.emplace_back(7); // < 0, 1, 2, 3, 4, 5, 6, 7 >numbers.emplace_front(-1); //

Добавление в середину списка с помощью функции emplace() :

std::deque numbers < 1, 2, 3, 4, 5 >; auto iter = ++numbers.cbegin(); // итератор указывает на второй элемент numbers.emplace(iter, 8); // добавляем после первого элемента numbers = < 1, 8, 2, 3, 4, 5>;

Добавление в середину списка с помощью функции insert() :

std::deque numbers1 < 1, 2, 3, 4, 5 >; auto iter1 = numbers1.cbegin(); // итератор указывает на второй элемент numbers1.insert(iter1 + 2, 8); // добавляем после второго элемента //numbers1 = < 1, 2, 8, 3, 4, 5>; std::deque numbers2 < 1, 2, 3, 4, 5 >; auto iter2 = numbers2.cbegin(); // итератор указывает на первый элемент numbers2.insert(iter2, 3, 4); // добавляем вначало три четверки //numbers2 = < 4, 4, 4, 1, 2, 3, 4, 5>; std::deque values < 10, 20, 30, 40, 50 >; std::deque numbers3 < 1, 2, 3, 4, 5 >; auto iter3 = numbers3.cbegin(); // итератор указывает на первый элемент // добавляем в начало все элементы из values numbers3.insert(iter3, values.begin(), values.end()); //numbers3 = < 10, 20, 30, 40, 50, 1, 2, 3, 4, 5>; std::deque numbers4 < 1, 2, 3, 4, 5 >; auto iter4 = numbers4.cend(); // итератор указывает на позицию за последним элементом // добавляем после последнего элемента список < 21, 22, 23 >numbers4.insert(iter4, < 21, 22, 23 >); //numbers4 = < 1, 2, 3, 4, 5, 21, 22, 23>;

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

Удаление элементов

Для удаления элементов из контейнера deque используются следующие функции:

• clear(p) : удаляет все элементы
• pop_back() : удаляет последний элемент
• pop_front() : удаляет первый элемент
• erase(p) : удаляет элемент, на который указывает итератор p. Возвращает итератор на элемент, следующий после удаленного, или на конец контейнера, если удален последний элемент
• erase(begin, end) : удаляет элементы из диапазона, на начало и конец которого указывают итераторы begin и end. Возвращает итератор на элемент, следующий после последнего удаленного, или на конец контейнера, если удален последний элемент

std::deque numbers< 1, 2, 3, 4, 5 >; numbers.pop_front(); // numbers = < 2, 3, 4, 5 >numbers.pop_back(); // numbers = < 2, 3, 4 >numbers.clear(); // numbers =<> numbers = < 1, 2, 3, 4, 5 >; auto iter = numbers.cbegin(); // указатель на первый элемент numbers.erase(iter); // удаляем первый элемент // numbers = < 2, 4, 5, 6 >numbers = < 1, 2, 3, 4, 5 >; auto begin = numbers.begin(); // указатель на первый элемент auto end = numbers.end(); // указатель на последний элемент numbers.erase(++begin, —end); // удаляем со второго элемента до последнего //numbers =

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

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