Деки в языке С++
Что же такое Дек? Дек (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
На этом этапе завершим вводную статью по декам, надеюсь, статья была для вас полезной.
Что такое дек в программировании
Д ек — особый вид очереди. Дек (от англ. deq — double ended queue,т.е очередь с двумя концами) — это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека — дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.
включение элемента справа;
включение элемента слева;
исключение элемента справа;
исключение элемента слева;
Ф изическая структура дека в статической памяти идентична структуре кольцевой очереди. Динамическая реализация является очевидным объединением стека и очереди.
З адачи, требующие структуры дека, встречаются в вычислительной технике и программировании гораздо реже, чем задачи, реализуемые на структуре стека или очереди. Как правило, вся организация дека выполняется программистом без каких-либо специальных средств системной поддержки.
П римером дека может быть, например, некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек.
Что такое дек в программировании
Мега-статья, потому что про очереди я так и не врубался на многочасовых лекциях и примерах, прочитав за 15 минут эту обычную статью все разложилось по полочкам, Большое спасибо!
Магсумова Диана Уровень 108 Expert
14 августа 2022
Прекрасная статья! )))) Благодарю))))
Евгений Т. Уровень 39
19 мая 2022
Ошибка в тексте «И со многими ИХ них «.
Жора Нет Уровень 39
30 апреля 2022
Из лекций ничего нового не почерпнул, кроме определения сложности алгоритмов. Все эти Стэки и Очереди приходилось самому находить и изучать при решении некоторых задач. Так вот в чем суть этих лекций? Я понимаю, если бы углублялись в изучении этих структур. А так получается я уже о них знаю больше, чем мне только что поверхностно рассказали.
Bulkin Уровень 40
10 ноября 2021
откуда столько времени найти такие книги читать?
Anonymous #2491313 Уровень 35
25 апреля 2021
Почему доставание элемента из очереди называется pull, а не pop?
Арман Уровень 37
14 апреля 2021
а на ее основе нередко строятся более сложныХ структуры данных.
5 апреля 2021
Я не понял откуда взялись эти классы и что они делают в примере про стек: game.setDeck(deck); game.setGraveyard(graveyard);
Иван Уровень 41
28 декабря 2020
Дайте несколько задач на очереди!
�� Виктор Уровень 20 Expert
6 ноября 2020
For the Alliance! Спасибо за статью, достаточно доступно, понятно и с хорошими примерами. Можно на эту тему ещё почитать следующие статьи: Стек-трейс Java. Stack Trace и с чем его едят. p.s. Если нужна, упомянутая в статье, книга Роберта Лафоре на русском языке в PDF формате с интерактивным оглавлением, то пишите, поделюсь ; )
Простейшие структуры данных: стек, очередь, дек
Чаще всего данные, с которыми работают программы, хранятся во встроенных в используемый язык программирования массивах, константной или переменной длины. Массив константной длины можно назвать простейшей структурой данных. Но иногда для решения задачи требуется большая эффективность некоторых операций, чем у массива. В таких случаях используются другие структуры данных, часто гораздо более сложные.
По определению, структура данных — способ представления данных в памяти, позволяющий эффективно выполнять с ними определённый набор операций. Например, простой массив лучше всего подходит для частого обращения к элементам по индексам и их изменению. А удаление элемента из середины массива работает за \(O(N)\). Если вам для решения задачи нужно часто удалять элементы, то придётся воспользоваться другой структурой данной. Например, бинарное дерево ( std::set ) позволяет делать это за \(O(\log N)\), но не поддерживает работу с индексами, только поочерёдный обход всех элементов и поиск по значению (тоже за \(O(\log N)\)).
Таким образом, структура данных характеризуется операциями, которые она может выполнять, и скоростью их выполнения.
В качестве примера рассмотрим несколько простейших структур данных, которые не предоставляют выгоды в эффективности, но имеют чётко определённый набор поддерживаемых операций.
Стек
Стек (англ. stack — стопка) — одна из простейших структур данных, представляющая собой скорее ограничение простого массива, чем его расширение. Классический стек поддерживает всего лишь три операции:
- Добавить элемент в стек (Сложность: \(O(1)\))
- Извлечь элемент из стека (Сложность: \(O(1)\))
- Проверить, пуст ли стек (Сложность: \(O(1)\))
Для объяснения принципа работы стека часто используется аналогия со стаканом с печеньем. Представьте, что на дне вашего стакана лежат несколько кусков печенья. Вы можете положить наверх ещё один кусок или достать уже находящийся наверху. Остальные куски закрыты верхним, и вы про них ничего не знаете. Для описания стека часто используется аббревиатура LIFO (Last In, First Out), подчёркивающая, что элемент, попавший в стек последним, первым будет из него извлечён.
Приведём простую реализацию стека на C++. Для простоты максимальный размер нашего стека будет ограничен тысячей элементов:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22struct stack int a[1000]; int head = -1; //Индекс крайнего элемента. void push(int x) head++; a[head] = x; > int pop() if (head != -1) head--; return a[head + 1]; > else //Ошибка, попытка извлечь элемент из пустого стека. > > bool is_empty() return head == -1; > >;Как видите, для реализации стека хватает одного массива и одного указателя, обозначающего крайний элемент.
Очередь
Очередь поддерживает тот же набор операций, что и стек, но имеет противоположную семантику. Для описания очереди используется аббревиатура FIFO (First In, First Out), так как первым из очереди извлекается элемент, раньше всех в неё добавленный. Название этой структуры говорит само за себя: принцип работы совпадает с обычными очередями в магазине или на почте.
Реализация очереди похожа на реализацию стека, но в этот раз нам понадобятся два указателя: для первого элемента очереди (“головы”) и последнего (“хвоста”):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30struct queue int a[1000]; //Для более лаконичной реализации работы, мы будем //хранить указатель не на последний элемент, а //на следующий за ним (несуществующий). //Это, в частности, позволит нам проверять очередь на пустоту //простым условием head == tail int head = 0; //Индекс первого элемента. int tail = 0; //Индекс элемента, следующего за последним. void push(int x) a[tail] = x; tail++; > int pop() if (head != tail) head++; return a[head - 1]; > else //Ошибка, попытка извлечь элемент из пустой очереди. > > bool is_empty() return head == tail; > >;При такой реализации очередь будет постепенно “ползти” вправо по выделенной области памяти (массиву), и достаточно быстро выйдет за её границы. Впрочем, эта реализация иллюстративная, на практике вы просто будете использовать уже готовую реализацию очереди из стандартной библиотеки (об этом ниже). В ней этот дефект отсутствует из-за более сложной работы с памятью.
Дек
Структура, объединяющая стек и очередь, называется дек (англ. deque - сокращение от double-ended queue, очередь с двумя концами). Как можно догадаться, она поддерживает уже знакомый набор операций:
- Добавить элемент в начало дека (Сложность: \(O(1)\))
- Извлечь элемент из начала дека (Сложность: \(O(1)\))
- Добавить элемент в конец дека (Сложность: \(O(1)\))
- Извлечь элемент из конца дека (Сложность: \(O(1)\))
- Проверить, пуст ли дек (Сложность: \(O(1)\))
В принципе мы можем реализовать её таким же способом, как и две предыдущих, но как и в случае с очередью, эта реализация будет далека от оптимальной.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40struct deque int a[2000]; //Используя такие начальные значения индексов, у нас //будет свободная память как слева, так и справа. int head = 1000; //Индекс первого элемента. int tail = 1000; //Индекс элемента, следующего за последним. void push_front(int x) head--; a[head] = x; > void push_back(int x) a[tail] = x; tail++; > int pop_front() if (head != tail) head++; return a[head - 1]; > else //Ошибка, попытка извлечь элемент из пустого дека. > > int pop_back() if (head != tail) tail--; return a[tail]; > else //Ошибка, попытка извлечь элемент из пустого дека. > > bool is_empty() return head == tail; > >;Стек, очередь и дек в стандартной библиотеке C++
Все три структуры данных являются базовыми и относительно часто встречаются в програмировании, поэтому они уже реализованы в стандартной библиотеке в виде трёх шаблонных классов. Пример работы со стеком и очередью:
stackint> s; //создание стека s.push(5); //добавление элемента cout <s.top(); //обращение к верхнему элементу if (!s.empty()) //проверка на пустоту s.pop(); //извлечение элемента (не возвращает значения, //нужно предварительно использовать .top()) > queueint> q; //создание очереди q.push(5); //добавление элемента cout <q.front() <' ' <q.back(); //обращение к первому и последнему элементам if (!q.empty()) //проверка на пустоту q.pop(); //извлечение элемента (не возвращает значения, //нужно предварительно использовать .top()) >С реализацией дека дела обстоят несколько иначе. Стандартный класс std::deque является не классическим деком, а скорее вектором с возможностью вставки и добавления в начало за \(O(1)\). Он поддерживает все операции, поддерживаемые классом std::vector , в том числе обращение к элементу по индексу и итераторы с произвольным доступом. Так что для работы с ним используйте те же методы, что и при работе с вектором.
Более сложные структуры данных
Приведённый выше материал мог вызвать у вас лёгкое недоумение и сомнения в целесообразности всех этих ограничений на обычные массивы. На самом деле, стек, очередь и дек являются лишь простейшими примерами структур данных, не предоставляющими выгоды в скорости выполнения операций. Серьёзным структурам данных посвящены отдельные темы. Стек, очередь и дек призваны проиллюстрировать, что главными характеристиками структуры данных являются набор поддерживаемых операций и скорость их выполнения.
brestprog
Олимпиадное программирование в Бресте и Беларуси