Что такое дек в программировании
Перейти к содержимому

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

  • автор:

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

Дек (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) .

Дек в C#

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

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

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

Д ек — особый вид очереди. Дек (от англ. deq — double ended queue,т.е очередь с двумя концами) — это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека — дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.

включение элемента справа;

включение элемента слева;

исключение элемента справа;

исключение элемента слева;

Ф изическая структура дека в статической памяти идентична структуре кольцевой очереди. Динамическая реализация является очевидным объединением стека и очереди.

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

П римером дека может быть, например, некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек.

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

Дек (от англ. 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()

Амортизированная стоимость операции в таком деке — [math]O(1)[/math] .

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

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

См. также

Источники информации

  • Википедия — Дек
  • Wikipedia — Deque
  • Open Data Structures — Building a Deque from Two Stacks

Добавить комментарий

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