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

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

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

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

public class DoublyNode  < public DoublyNode(T data) < Data = data; >public T Data < get; set; >public DoublyNode Previous < get; set; >public DoublyNode Next < get; set; >>

Класс дека будет следующим:

using System; using System.Collections; using System.Collections.Generic; namespace SimpleAlgorithmsApp < public class Deque: IEnumerable // двусвязный список < DoublyNodehead; // головной/первый элемент DoublyNode tail; // последний/хвостовой элемент int count; // количество элементов в списке // добавление элемента public void AddLast(T data) < DoublyNodenode = new DoublyNode(data); if (head == null) head = node; else < tail.Next = node; node.Previous = tail; >tail = node; count++; > public void AddFirst(T data) < DoublyNodenode = new DoublyNode(data); DoublyNode temp = head; node.Next = temp; head = node; if (count == 0) tail = head; else temp.Previous = node; count++; > public T RemoveFirst() < if (count == 0) throw new InvalidOperationException(); T output = head.Data; if(count==1) < head = tail = null; >else < head = head.Next; head.Previous = null; >count--; return output; > public T RemoveLast() < if (count == 0) throw new InvalidOperationException(); T output = tail.Data; if (count == 1) < head = tail = null; >else < tail = tail.Previous; tail.Next = null; >count--; return output; > public T First < get < if (IsEmpty) throw new InvalidOperationException(); return head.Data; >> public T Last < get < if (IsEmpty) throw new InvalidOperationException(); return tail.Data; >> public int Count < get < return count; >> public bool IsEmpty < get < return count == 0; >> public void Clear() < head = null; tail = null; count = 0; >public bool Contains(T data) < DoublyNodecurrent = head; while (current != null) < if (current.Data.Equals(data)) return true; current = current.Next; >return false; > IEnumerator IEnumerable.GetEnumerator() < return ((IEnumerable)this).GetEnumerator(); >IEnumerator IEnumerable.GetEnumerator() < DoublyNodecurrent = head; while (current != null) < yield return current.Data; current = current.Next; >> > >

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

Для добавления в начало очереди переустанавливаем ссылку на переменную head:

public void AddFirst(T data) < DoublyNodenode = new DoublyNode(data); DoublyNode temp = head; node.Next = temp; head = node; if (count == 0) tail = head; else temp.Previous = node; count++; >

Добавление элемента в конец дека вызывает аналогичную переустановку переменной tail:

public void AddLast(T data) < DoublyNodenode = new DoublyNode(data); if (head == null) head = node; else < tail.Next = node; node.Previous = tail; >tail = node; count++; >

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

public T RemoveFirst() < if (count == 0) throw new InvalidOperationException(); T output = head.Data; if(count==1) < head = tail = null; >else < head = head.Next; head.Previous = null; >count--; return output; >

При удалении последнего элемента переустанавливается переменная tail на предпоследний элемент:

public T RemoveLast() < if (count == 0) throw new InvalidOperationException(); T output = tail.Data; if (count == 1) < head = tail = null; >else < tail = tail.Previous; tail.Next = null; >count--; return output; >

Сложность алгоритмов всех методов добавления и удаления из дека составляет O(1) .

Deque usersDeck = new Deque(); usersDeck.AddFirst("Alice"); usersDeck.AddLast("Kate"); usersDeck.AddLast("Tom"); foreach(string s in usersDeck) Console.WriteLine(s); string removedItem = usersDeck.RemoveFirst(); Console.WriteLine("\n Удален: \n", removedItem); foreach (string s in usersDeck) Console.WriteLine(s);

Alice Kate Tom Удален: Alice Kate Tom

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

Что же такое Дек? Дек (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

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

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

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

push Добавить (положить) в конец стека новый элемент
pop Извлечь из стека последний элемент
back Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в стеке
clear Очистить стек (удалить из него все элементы)

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

Объявим структуру данных типа stack .

const int MAX_SIZE=1000;

struct stack int m_size; // Количество элементов в стеке
int m_elems[MAX_SIZE]; // Массив для хранения элементов

stack(); // Конструктор
~stack(); // Деструктор
void push(int d); // Добавить в стек новый элемент
int pop(); // Удалить из стека последний элемент
// и вернуть его значение
int back(); // Вернуть значение последнего элемента
int size(); // Вернуть количество элементов в стеке
void clear(); // Очистить стек
>;

Объявленная здесь структура данных stack реализует стек целых чисел. Поле структуры m_size хранит количество элементов в стеке в настоящее время, сами элементы хранятся в элементах массива m_elems с индексами 0.. m_size-1 . Элементы, добавленные позже, получают большие номера.

Упражнение A — простой стек

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

push n Добавить в стек число n (значение n задается после команды). Программа должна вывести ok .
pop Удалить из стека последний элемент. Программа должна вывести его значение.
back Программа должна вывести значение последнего элемента, не удаляя его из стека.
size Программа должна вывести количество элементов в стеке.
clear Программа должна очистить стек и вывести ok .
exit Программа должна вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop_back и back корректны, то есть при их исполнении в стеке содержится хотя бы один элемент.

Пример протокола работы программы

Ввод Вывод

push 2 ok
push 3 ok
push 5 ok
back 5
size 3
pop 5
size 2
push 7 ok
pop 7
clear ok
size 0
exit bye

Упражнение B — стек с обработкой ошибок

Аналогично предыдущему заданию, только снимается ограничение на корректность вызовов методов back и pop . Данные операции должны перед исполнением проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop , при этом стек пуст, то программа должна вместо числового значения вывести строку error .

При этом должна быть реализована двойная защита: вызов методов forward и pop для пустого стека не должен приводить к обращению к несуществующим элементам массива m_elems , а функция main должна выводить сообщение error , при считывании некорректной операции.

Пример протокола работы программы

Ввод Вывод

push 2 ok
back 2
pop 2
size 0
pop error
push 1 ok
size 1
exit bye

Упражнение C — стек без ограничения на размер

Реализуйте стек динамического размера, то есть ограниченный только объемом свободной оперативной памяти. Для этого используйте указатели и динамически распределяемую память. Если для полностью заполненного стека вызывается метод push размер динамического массива, отведенного для хранения стека, должен увеличиваться.

Очередь

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

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

Описание структуры очередь:

const int MAX_SIZE=1000;

struct queue int m_size; // Количество элементов в очереди
int m_start; // Номер элемента, с которого начинается очередь
int m_elems[MAX_SIZE]; // Массив для хранения элементов

queue(); // Конструктор
~queue(); // Деструктор
void push(int d); // Добавить в очередь новый элемент
int pop(); // Удалить из очереди первый элемент
// и вернуть его значение
int front(); // Вернуть значение первого элемента
int size(); // Вернуть количество элементов в очереди
void clear(); // Очистить очередь
>;

Упражнение D — простая очередь

Реализуйте простейшую очередь, размер которой не превосходит 100 элементов. Очередь поддерживает те же операции, что и стек, за исключением операции back , которая заменена операцией front . Операции front и pop всегда корректны.

Упражнение E — очередь с обработкой ошибок

Аналогично заданию B, но для очереди. Операции front и pop могут быть некорректными, в этом случае необходимо вывести error .

Программа должна содержать «двойную защиту» от некорректных операций: как в функции main , так и в самих методах pop и front .

Упражнение F — очередь без ограничений на размер

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

Дек

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

push_front Добавить (положить) в начало дека новый элемент
push_back Добавить (положить) в конец дека новый элемент
pop_front Извлечь из дека первый элемент
pop_back Извлечь из дека последний элемент
front Узнать значение первого элемента (не удаляя его)
back Узнать значение последнего элемента (не удаляя его)
size Узнать количество элементов в деке
clear Очистить дек (удалить из него все элементы)

Упражнение G — простой дек

Аналогично заданиям A и D, но для дека. Количество элементов в деке в любой момент не превосходит 100. Все операции pop_front , pop_back , front , back всегда корректны.

Упражнение H — дек с обработкой ошибок

Аналогично заданиям B и E, но для дека. Количество элементов в деке в любой момент не превосходит 100. При выполнении некорректных операций необходимо вывести error .

Упражнение I — дек неограниченного размера

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

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

Дек (от англ. 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 [/math] может вместить в себя все добавленные элементы.

boolean empty(): return head == tail

function pushBack(x : T): d[tail++] = x

T popBack(): if (empty()) return error "underflow" return d[--tail]

function pushFront(x : T): d[--head] = x

T popFront(): if (empty()) return error "underflow" return d[head++]

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

Во всех циклических реализациях изначально присвоены следующие значения [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] .

function pushBack(x : T): if (head == (tail + 1) % n) return error "overflow" d[tail] = x tail = (tail + 1) % n

T popBack(): if (empty()) return error "underflow" tail = (tail - 1 + n) % n return d[tail]

function pushFront(x : T): if (head == (tail + 1) % n) return error "overflow" head = (head - 1 + n) % n d[head] = x

T popFront(): if (empty()) return error "underflow" T ret = d[head] head = (head + 1) % n return ret

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

• [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] получение текущего размера дека.

int size() if tail > head return n - head + tail else return tail - head

function pushBack(x : T): if (head == (tail + 1) % n) T newDeque[n * 2] for i = 0 to n - 2 newDeque[i] = d[head] head = (head + 1) % n d = newDeque head = 0 tail = n - 1 n *= 2 d[tail] = x tail = (tail + 1) % n

T popBack(): if (empty()) return error "underflow" if (size() < n / 4) T newDeque[n / 2] int dequeSize = size() for i = 0 to dequeSize - 1 newDeque[i] = d[head] head = (head + 1) % n d = newDeque head = 0 tail = dequeSize n /= 2 tail = (tail - 1 + n) % n return d[tail]

function pushFront(x : T): if (head == (tail + 1) % n) T newDeque[n * 2] for i = 0 to n - 2 newDeque[i] = d[head] head = (head + 1) % n d = newDeque head = 0 tail = n - 1 n *= 2 head = (head - 1 + n) % n d[head] = x

T popFront(): if (empty()) return error "underflow" if (size() < n / 4) T newDeque[n / 2] int dequeSize = size() for i = 0 to dequeSize - 1 newDeque[i] = d[head] head = (head + 1) % n d = newDeque head = 0 tail = dequeSize n /= 2 T ret = d[head] head = (head + 1) % n return ret

На списке

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

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

function initialize(): head = ListItem(null, null, null) tail = ListItem(null, null, head) head.next = tail

function pushBack(x : T): head = ListItem(x, head, null) head.next.prev = head

T popBack(): data = head.data head = head.next return data

function pushFront(x : T): tail = ListItem(x, null, tail) tail.prev.next = tail

T popFront(): data = tail.data tail = tail.prev return data

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

• [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] .

function pushBack(x : T): leftStack.push(x)

T popBack(): if not leftStack.empty() return leftStack.pop() else int size = rightStack.size() Stack local for i = 0 to size / 2 local.push(rightStack.pop()) while not rightStack.empty() leftStack.push(rightStack.pop()) while not local.empty() rightStack.push(local.pop()) return leftStack.pop()

function pushFront(x : T): rightStack.push(x)

T popFront(): if not rightStack.empty() return rightStack.pop() else int size = leftStack.size() Stack local for i = 0 to size / 2 local.push(leftStack.pop()) while not leftStack.empty() rightStack.push(leftStack.pop()) while not local.empty() leftStack.push(local.pop()) return rightStack.pop()