Очередь с двойным завершением или просто двухсторонняя очередь “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 спереди:
Теперь мы вставляем элемент 3 сзади:
Затем мы добавляем элемент 5 к передней части:
Затем мы вставляем элементы 7 сзади и 9 спереди. Deque будет выглядеть так, как показано ниже:
Далее давайте удалим элемент спереди:
Таким образом, становиться видно, что когда элементы вставляются спереди, передняя позиция уменьшается, в то время как она увеличивается при удалении элемента. Для задней части позиция увеличивается для вставки и уменьшается для удаления.
Реализация
Мы можем реализовать двухстороннюю очередь в C++, используя массивы, а также связный список. Помимо этого, стандартная библиотека шаблонов (STL) имеет класс “deque”, который реализует все функции для этой структуры данных.
Реализация deque в массиве приведена ниже. Поскольку это двусторонняя очередь, мы использовали циклические массивы для данной реализации:
|
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 |
#include<iostream> using namespace std; #define MAX_size 10 // Максимальный размер массива или удаления из очереди // Класс Deque class Deque { int array[MAX_size]; int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Операции по Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Проверьте, заполнен ли Deque bool isFull(){ return ((front == 0 && rear == size-1)||front == rear+1); } // Проверьте, пуст ли Deque bool isEmpty(){ return (front == -1); } }; // Вставьте элемент в переднюю часть deque void Deque::insertfront(int key) { if (isFull()) { cout << "Overflow!!\n" << endl; return; } // Если очередь изначально пуста, установите front=rear=0; начало deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front - это первая позиция очереди front = size - 1 ; else // уменьшите переднюю часть на 1 позицию front = front-1; array[front] = key ; // вставить текущий элемент в Deque } // вставной элемент на заднем конце deque void Deque ::insertrear(int key) { if (isFull()) { cout << " Overflow!!\n " << endl; return; } // Если очередь изначально пуста, установите front=rear=0; начало deque if (front == -1) { front = 0; rear = 0; } else if (rear == size-1) // задняя часть находится в последней позиции очереди rear = 0; else // увеличьте заднюю часть на 1 позицию rear = rear+1; array[rear] = key ; // вставить текущий элемент в Deque } // Удалить элемент перед Deque void Deque ::deletefront() { if (isEmpty()) { cout << "Queue Underflow!!\n" << endl; return ; } // У Deque есть только один элемент if (front == rear) { front = -1; rear = -1; } else // вернуться в исходное положение if (front == size -1) front = 0; else // удалить текущее начальное значение из Deque; увеличить начальное значение на 1 front = front+1; } // Удалить элемент в задней части Deque void Deque::deleterear() { if (isEmpty()) { cout << " Underflow!!\n" << endl ; return ; } // У Deque есть только один элемент if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // извлеките передний элемент Deque int Deque::getFront() { if (isEmpty()) { cout << " Underflow!!\n" << endl; return -1 ; } return array[front]; } // извлеките задний элемент Deque int Deque::getRear() { if(isEmpty() || rear < 0) { cout << " Underflow!!\n" << endl; return -1 ; } return array[rear]; } //основная программа int main() { Deque dq(5); cout << "Insert element 1 at rear end \n"; dq.insertrear(1); cout << "insert element 3 at rear end \n"; dq.insertrear(3); cout << "rear element of deque " << " " << dq.getRear() << endl; dq.deleterear(); cout << "After deleterear, rear = " << dq.getRear() << endl; cout << "inserting element 5 at front end \n"; dq.insertfront(5); cout << "front element of deque " << " " << dq.getFront() << endl; dq.deletefront(); cout << "After deletefront, front = " << dq.getFront() << endl; return 0; } |
Вывод данных:
| 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 не поддерживает параллелизм с несколькими потоками.
- 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 пустое. (Эта операция не удаляет элемент) |
Следующая реализация программы на Java демонстрирует различные операции, рассмотренные выше:
|
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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
import java.util.*; class Main { public static void main(String[] args) { Deque<Integer>deque = new LinkedList<Integer>(); // Мы можем добавлять элементы в очередь различными способами deque.add(1); // добавить в хвост deque.addFirst(3); deque.addLast(5); deque.push(7); //добавить в заголовок deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println("The deque : " + deque + "\n"); // Выполните итерацию по элементам очереди System.out.println("Standard Iterator"); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(" " + iterator.next()); // Итератор обратного порядка Iterator reverse = deque.descendingIterator(); System.out.println("\nReverse Iterator"); while (reverse.hasNext()) System.out.print(" " + reverse.next()); // Peek возвращает заголовок, не удаляя // его из deque System.out.println("\n\nPeek " + deque.peek()); System.out.println("After peek: " + deque); // Pop возвращает заголовок и удаляет его из // deque System.out.println("\nPop " + deque.pop()); System.out.println("After pop: " + deque); // Мы можем проверить, существует ли определенный элемент // в deque System.out.println("\nContains element 3?: " + deque.contains(3)); // Мы можем удалить первый / последний элемент deque.removeFirst(); deque.removeLast(); System.out.println("Deque after removing " + "first and last elements: " + deque); } } |
Вывод данных:
| The deque : [11, 7, 3, 1, 5, 9, 13]
Standard Iterator Peek 11 Pop 11 Contains element 3?: true |
В приведенной выше программе мы использовали интерфейс Deque Java и определили deque целых элементов. Затем мы выполнили различные операции над этим deque и на выходе отобразились результаты этих операций.
Применения
Двухсторонняя очередь может применяться:
- Алгоритм планирования: реализует планирование задач для различных процессоров в многопроцессорной системе. В этой реализации используется deque, и процессор получает первый элемент из deque для выполнения.
- Отмена списка действий: в программных приложениях есть много действий. Одно из них — “отмена”. Когда мы выполняем действие отмены много раз, все эти действия сохраняются в списке. Этот список работает как deque, так что мы можем легко добавлять / удалять записи с любого конца.
- Обновление записей в приложении, например, приложения, в которых перечислены основные записи и т.д. Эти приложения удаляют записи через некоторое время, а также вставляют новые записи. Это также делается с помощью deque.
Итог
Deque — это двусторонняя очередь, которая позволяет нам добавлять / удалять элементы с обоих концов, то есть спереди и сзади, очереди. Deque может быть реализован с использованием массивов или связных списков. Также есть класс стандартной библиотеки шаблонов (STL), который реализует различные операции Deque.
В Java есть интерфейс Deque, который наследуется от интерфейса queue для реализации Deque. Помимо основных стандартных операций Deque, этот интерфейс поддерживает различные другие операции, которые могут выполняться в Deque.
Deque обычно используется для приложений, которые требуют добавления / удаления элементов с обоих концов. Двухсторонняя очередь также в основном используется при планировании работы процессоров в многопроцессорных системах.
В следующей статье мы с вами поговорим о хеш-таблицах в C++.
С Уважением, МониторБанк