double ended queue c with examples
Задълбочен урок за Deque или двукратна опашка в C ++. Урокът обяснява какво е Deque, основни операции, внедряване на C ++ и Java и приложения:
Двойно завършилата опашка или просто наречена „Deque“ е обобщена версия на Queue.
Разликата между Queue и Deque е, че тя не следва подхода FIFO (First In, First Out). Втората характеристика на Deque е, че можем да вмъкваме и премахваме елементи от предния или задния край.
=> Прочетете серията Easy C ++ Training
Какво ще научите:
- Класификация на двойно завършена опашка
- Основни операции с докосване
- и илюстрация
- и изпълнение
- Приложения
- Заключение
- Препоръчително четене
Класификация на двойно завършена опашка
Deque може да бъде класифициран, както следва:
Въвеждане с ограничено докосване; При ограничено въвеждане изтриването може да се извърши от двата края, но вмъкването може да се извърши само в задния край на опашката.
Deque с ограничен изход: В опашката с ограничен изход, вмъкването може да се извърши от двата края, но изтриването се извършва само в единия край, т.е.предния край на опашката.
Също така можем да реализираме стекове и опашки, използвайки deque.
Основни операции с докосване
По-долу са посочени основните операции, които могат да се извършват върху deque.
- вмъкнете отпред: Поставете или добавете елемент в предната част на deque.
- insertLast: Поставете или добавете елемент в задната част на deque.
- deleteFront: Изтрийте или премахнете елемента от предната страна на опашката.
- последно изтриване: Изтрийте или премахнете елемента от задната страна на опашката.
- getFront: Извлича предния елемент в deque.
- getLast: Извлича последния елемент от опашката.
- празно е: Проверява дали deque е празен.
- е пълен: Проверява дали декът е пълен.
и илюстрация
Празната дека е представена, както следва:
Алгоритъмът на dijkstra, използващ Java приоритетна опашка
След това вмъкваме елемент 1 отпред.
Сега вмъкваме елемент 3 отзад.
След това добавяме елемент 5 отпред и когато увеличаваме предните точки до 4.
След това вмъкваме елементи 7 отзад и 9 отпред. Deque ще изглежда както е показано по-долу.
След това нека премахнем елемент отпред.
По този начин виждаме, че когато елементите са вмъкнати отпред, предното положение се намалява, докато се увеличава при премахване на елемент. За задния край позицията се увеличава за вмъкване и намалява за отстраняване .
и изпълнение
100 ++ touch Внедряване
Можем да приложим deque в C ++, като използваме масиви, както и свързан списък. Отделно от това, стандартната библиотека с шаблони (STL) има клас “deque”, който реализира всички функции за тази структура на данните.
Внедряването на масива на deque е дадено по-долу. Тъй като това е двойна опашка, ние използвахме кръгови масиви за изпълнение.
#include using namespace std; #define MAX_size 10 // Maximum size of array or Dequeue // Deque class class Deque { int array(MAX_size); int front; int rear; int size; public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); int getFront(); int getRear(); // Check if Deque is full bool isFull()front == rear+1); // Check if Deque is empty bool isEmpty(){ return (front == -1); } }; // Insert an element at front of the deque void Deque::insertfront(int key) { if (isFull()) { cout << 'Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (front == 0) // front is first position of queue front = size - 1 ; else // decrement front 1 position front = front-1; array(front) = key ; // insert current element into Deque } // insert element at the rear end of deque void Deque ::insertrear(int key) { if (isFull()) { cout << ' Overflow!!
' << endl; return; } // If queue is initially empty,set front=rear=0; start of deque if (front == -1) { front = 0; rear = 0; } else if (rear == size-1) // rear is at last position of queue rear = 0; else // increment rear by 1 position rear = rear+1; array(rear) = key ; // insert current element into Deque } // Delete element at front of Deque void Deque ::deletefront() { if (isEmpty()) { cout << 'Queue Underflow!!
' << endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // remove current front value from Deque;increment front by 1 front = front+1; } // Delete element at rear end of Deque void Deque::deleterear() { if (isEmpty()) { cout << ' Underflow!!
' << endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1; } // retrieve front element of Deque int Deque::getFront() { if (isEmpty()) { cout << ' Underflow!!
' << endl; return -1 ; } return array(front); } // retrieve rear element of Deque int Deque::getRear() { if(isEmpty() || rear < 0) { cout << ' Underflow!!
' << endl; return -1 ; } return array(rear); } //main program int main() { Deque dq(5); cout << 'Insert element 1 at rear end
'; dq.insertrear(1); cout << 'insert element 3 at rear end
'; 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
'; dq.insertfront(5); cout << 'front element of deque ' << ' ' << dq.getFront() << endl; dq.deletefront(); cout << 'After deletefront, front = ' << dq.getFront() << endl; return 0; } Изход:
Поставете елемент 1 в задния край
поставете елемент 3 отзад
заден елемент на deque 3
След deleterear, задна = 1
вмъкване на елемент 5 в предния край
команда grep в скрипта на черупката на unix
преден елемент на deque 5
След deletefront, front = 1
Преброяване на внедряването на Java
Deque интерфейсът в Java, “java.util.Deque” е получен от интерфейса “java.util.Queue”. Deque може да се използва като опашка (First In, First Out) или стек (Last In, First Out). Тези внедрения работят по-бързо от свързания списък.
По-долу е дадена йерархията за интерфейса Deque в Java.
Трябва да запомним няколко точки за интерфейса Deque в Java:
- Внедряването не е безопасно за нишки, тъй като няма външна синхронизация.
- Deque не поддържа паралелност от множество нишки.
- Реализираните с помощта на масиви Deque не позволяват използването на NULL елементи.
- Масивите могат да растат според изискванията, като капацитетът без ограничения и подменящата се поддръжка на масива са двете най-важни характеристики.
Следват различните методи, поддържани от интерфейса Deque:
пример за тест на junit в java eclipse
| Недей. | Метод | Описание |
|---|---|---|
| 7 | итератор () | Връща итератор за deque. |
| 1 | добавяне (елемент) | Добавя елемент към опашката. |
| две | addFirst (елемент) | Добавя елемент към главата / отпред. |
| 3 | addLast (елемент) | Добавя елемент към опашката / задната част. |
| 4 | оферта (елемент) | Добавя елемент към опашката; връща булева стойност, за да покаже дали вмъкването е било успешно. |
| 5 | offerFirst (елемент) | Добавя елемент към главата; връща булева стойност, за да покаже дали вмъкването е било успешно. |
| 6 | offerLast (елемент) | Добавя елемент към опашката; връща булева стойност, за да покаже дали вмъкването е било успешно. |
| 8 | низходящIterator () | Връща итератор, който има обратния ред за този deque. |
| 9 | тласък (елемент) | Добавя елемент към главата на deque. |
| 10 | поп (елемент) | Премахва елемент от главата на deque и го връща. |
| единадесет | removeFirst () | Премахва елемента в главата на дека. |
| 12 | removeLast () | Премахва елемента в опашката на дека. |
| 13 | анкета () | Извлича и премахва първия елемент на дека (представен от главата на дека); връща NULL, ако deque е празен. |
| 14. | pollFirst () | Извлича и премахва първия елемент от този deque; връща null, ако този deque е празен. |
| петнадесет | pollLast () | Извлича и премахва последния елемент от този deque; връща null, ако този deque е празен. |
| 16. | надниквам () | Извлича главата (първия елемент на deque) на опашката, представена от този deque; връща null, ако този deque е празен. Забележка: Тази операция не премахва елемента. |
| 17 | peekFirst () | Извлича първия елемент от този deque; връща null, ако този deque е празен. Забележка: Тази операция не премахва елемента. |
| 18. | peekLast () | Извлича последния елемент от този deque или връща null, ако този deque е празен. Забележка: Тази операция не премахва елемента. |
Следващата реализация на Java демонстрира различните операции, обсъдени по-горе.
import java.util.*; class Main { public static void main(String() args) { Deque deque = new LinkedList (); // We can add elements to the queue in various ways deque.add(1); // add to tail deque.addFirst(3); deque.addLast(5); deque.push(7); //add to head deque.offer(9); deque.offerFirst(11); deque.offerLast(13); System.out.println('The deque : ' + deque + '
'); // Iterate through the queue elements. System.out.println('Standard Iterator'); Iterator iterator = deque.iterator(); while (iterator.hasNext()) System.out.print(' ' + iterator.next()); // Reverse order iterator Iterator reverse = deque.descendingIterator(); System.out.println('
Reverse Iterator'); while (reverse.hasNext()) System.out.print(' ' + reverse.next()); // Peek returns the head, without deleting // it from the deque System.out.println('
Peek ' + deque.peek()); System.out.println('After peek: ' + deque); // Pop returns the head, and removes it from // the deque System.out.println('
Pop ' + deque.pop()); System.out.println('After pop: ' + deque); // We can check if a specific element exists // in the deque System.out.println('
Contains element 3?: ' + deque.contains(3)); // We can remove the first / last element. deque.removeFirst(); deque.removeLast(); System.out.println('Deque after removing ' + 'first and last elements: ' + deque); } } Изход:
И (11, 7, 3, 1, 5, 9, 13)
Стандартен итератор
11 7 3 1 5 9 13
Обратен итератор
13 9 5 1 3 7 11
Надникнете 11
След надникване: (11, 7, 3, 1, 5, 9, 13)
Поп 11
След изскачане: (7, 3, 1, 5, 9, 13)
Съдържа елемент 3 ?: true
Deque след премахване на първия и последния елемент: (3, 1, 5, 9)
В горната програма използвахме Deque интерфейса на Java и дефинирахме deque на цели числа. След това извършихме различни операции с този deque и изведени резултатите от тези операции се показват.
Приложения
Deque може да се използва в някои от следните приложения.
# 1) Алгоритъм за планиране: Алгоритъм за планиране, „Алгоритъм за планиране на кражба“, реализира планиране на задачи за различни процесори в многопроцесорната система. Тази реализация използва deque и процесорът получава първия елемент от deque за изпълнение.
# 2) Отмяна на списък с дейности: В софтуерните приложения имаме много действия. Едната е „отмяна“. Когато сме извършвали многократно действие за отмяна, всички тези действия се съхраняват в списък. Този списък се поддържа като deque, за да можем лесно да добавяме / премахваме записи от всеки край.
# 3) Премахнете записите след известно време: Приложенията опресняват записите в списъка си, като приложения, които изброяват запасите и т.н. Тези приложения премахват записите след известно време и също така вмъкват нови записи. Това се прави с помощта на deque.
Заключение
Deque е двойна опашка, която ни позволява да добавяме / премахваме елементи от двата края, т.е.пред и отзад, на опашката. Deque може да се приложи с помощта на масиви или свързани списъци. Имаме обаче и клас на стандартна библиотека на шаблони (STL), който изпълнява различните операции на Deque.
В Java имаме интерфейс Deque, който се наследява от интерфейса на опашката за внедряване на Deque. Освен основните стандартни операции на Deque, този интерфейс поддържа различни други операции, които могат да се извършват на Deque.
Deque обикновено се използва за приложения, които изискват добавяне / премахване на елементи от двата края. Също така се използва най-вече при планирането на процесори в многопроцесорни системи.
=> Вижте пълната серия за обучение на C ++
Препоръчително четене
- Приоритетна опашка в STL
- Какво е сравнително тестване (научете с примери)
- Урок за Python DateTime с примери
- Сортиране на черупката в C ++ с примери
- Изрежете командата в Unix с примери
- Синтаксис на командата Unix Cat, Опции с примери
- Използване на курсора в MongoDB с примери
- Ls Command в Unix с примери