Двухсторонняя очередь (Deque) в C++

Двухсторонняя очередьОчередь с двойным завершением или просто двухсторонняя очередь “Deque” — это обобщенная версия очереди.

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

Классификация очереди с двойным завершением

  • Deque с ограниченным вводом
  • Deque с ограниченным выходом

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

Мы также можем реализовать с помощью deque стеки и очереди.

Основные операции Deque

Ниже приведены основные операции, которые можно выполнить в deque:

  • insert front: Вставка или добавление элемента в начало deque.
  • insertLast: Вставка или добавление элемента в конце deque.
  • deleteFront: Удаление элемента из начала очереди.
  • delete last: Удаление элемента из конца очереди.
  • getFront: Извлечение первого элемента в deque.
  • getLast: Извлечение последнего элемента в очереди.
  • isEmpty: Проверка, является ли deque пустым.
  • isFull: Проверка, заполнена ли очередь deque.

Демонстрация

Пустая двухсторонняя очередь представлена следующим образом:

Пустая двухсторонняя очередь

Далее мы вставляем элемент 1 спереди:

Элемент 1 спереди

Теперь мы вставляем элемент 3 сзади:

Элемент 3 сзади

Затем мы добавляем элемент 5 к передней части:

Элемент 5 к передней части

Затем мы вставляем элементы 7 сзади и 9 спереди. Deque будет выглядеть так, как показано ниже:

Элементы 7 сзади и 9 спереди

Далее давайте удалим элемент спереди:

Элемент спереди

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

Читать также:  Использование массивов с функциями в C++

Реализация

Мы можем реализовать двухстороннюю очередь в C++, используя массивы, а также связный список. Помимо этого, стандартная библиотека шаблонов (STL) имеет класс “deque”, который реализует все функции для этой структуры данных.

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

Вывод данных:

Insert element 1 at rear end
insert element 3 at rear end
rear element of deque 3
After deleterear, rear = 1
inserting element 5 at the front end
front element of deque 5
After deletefront, front = 1

Реализация той же программы на Java:

Интерфейс двухсторонней очереди в Java, “java.util.Deque” является производным от интерфейса “java.util.Queue”. Deque может использоваться как очередь (первый вход, первый выход) или стек (последний вход, первый выход). Эти реализации работают быстрее, чем связный список.

Ниже приведена иерархия для интерфейса Deque в Java:

Схема интерфейса Deque в Java

Есть несколько моментов об интерфейсе Deque в Java, о которых нужно помнить:

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

Ниже приведены различные методы, поддерживаемые интерфейсом Deque:

Метод Описание
1 add (элемент) Добавляет элемент в хвост.
2 addFirst (элемент) Добавляет элемент в начало.
3 addLast (элемент) Добавляет элемент в хвост.
4 offer (элемент) Добавляет элемент в хвост; возвращает логическое значение, указывающее, была ли вставка успешной.
5 offerFirst (элемент) Добавляет элемент в заголовок; возвращает логическое значение, указывающее, была ли вставка успешной.
6 offerLast (элемент) Добавляет элемент в хвост; возвращает логическое значение, указывающее, была ли вставка успешной.
7 iterator() Возвращает итератор для deque.
8 descendingIterator() Возвращает итератор, который имеет обратный порядок для этого deque.
9 push (элемент) Добавляет элемент в начало deque.
10 pop (элемент) Удаляет элемент из заголовка deque и возвращает его.
11 removeFirst() Удаляет элемент в начале deque.
12 removeLast() Удаляет элемент в конце deque.
13 poll() Извлекает и удаляет первый элемент deque (представленный заголовком deque); возвращает NULL, если deque пуст.
14 pollFirst() Извлекает и удаляет первый элемент этого deque; возвращает null, если это deque пустое.
15 pollLast() Извлекает и удаляет последний элемент этого deque; возвращает null, если это deque пустое.
16 peek() Извлекает заголовок (первый элемент deque) очереди, представленной этим deque; возвращает null, если это deque пустое. (Эта операция не удаляет элемент)
17 peekFirst() Извлекает первый элемент этого deque; возвращает null, если это deque пустое. (Эта операция не удаляет элемент)
18 peekLast() Извлекает последний элемент этого deque или возвращает null, если это deque пустое. (Эта операция не удаляет элемент)

Читать также:  Обработка исключений в C++

Следующая реализация программы на Java демонстрирует различные операции, рассмотренные выше:

Вывод данных:

The deque : [11, 7, 3, 1, 5, 9, 13]

Standard Iterator
11 7 3 1 5 9 13
Reverse Iterator
13 9 5 1 3 7 11

Peek 11
After peek: [11, 7, 3, 1, 5, 9, 13]

Pop 11
After pop: [7, 3, 1, 5, 9, 13]

Contains element 3?: true
Deque after removing first and last elements: [3, 1, 5, 9]

В приведенной выше программе мы использовали интерфейс Deque Java и определили deque целых элементов. Затем мы выполнили различные операции над этим deque и на выходе отобразились результаты этих операций.

Применения

Двухсторонняя очередь может применяться:

  1. Алгоритм планирования: реализует планирование задач для различных процессоров в многопроцессорной системе. В этой реализации используется deque, и процессор получает первый элемент из deque для выполнения.
  2. Отмена списка действий: в программных приложениях есть много действий. Одно из них — “отмена”. Когда мы выполняем действие отмены много раз, все эти действия сохраняются в списке. Этот список работает как deque, так что мы можем легко добавлять / удалять записи с любого конца.
  3. Обновление записей в приложении, например, приложения, в которых перечислены основные записи и т.д. Эти приложения удаляют записи через некоторое время, а также вставляют новые записи. Это также делается с помощью deque.

Читать также:  Ссылки в С++

Итог

Deque — это двусторонняя очередь, которая позволяет нам добавлять / удалять элементы с обоих концов, то есть спереди и сзади, очереди. Deque может быть реализован с использованием массивов или связных списков. Также есть класс стандартной библиотеки шаблонов (STL), который реализует различные операции Deque.

В Java есть интерфейс Deque, который наследуется от интерфейса queue для реализации Deque. Помимо основных стандартных операций Deque, этот интерфейс поддерживает различные другие операции, которые могут выполняться в Deque.

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

В следующей статье мы с вами поговорим о хеш-таблицах в C++.

С Уважением, МониторБанк

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