double ended queue c with examples
Detaljni vodič o Deque ili dvostrukom redu u C ++-u. Vodič objašnjava što je Deque, osnovne operacije, implementacija C ++ i Java i aplikacije:
Dvostruko završeni red ili jednostavno nazvan 'Deque' generalizirana je verzija reda.
Razlika između Queue i Deque je u tome što ne slijedi FIFO (First In, First Out) pristup. Druga značajka Dequea je da možemo umetnuti i ukloniti elemente s prednjeg ili stražnjeg kraja.
=> Pročitajte jednostavnu seriju C ++ treninga
Što ćete naučiti:
- Klasifikacija dvostruko završenog reda
- Osnovne operacije dodira
- i Ilustracija
- i Provedba
- Prijave
- Zaključak
- Preporučena literatura
Klasifikacija dvostruko završenog reda
Deque se može klasificirati na sljedeći način:
Ulaz s ograničenim dodirom; U ograničenom ulazu, brisanje se može obaviti s oba kraja, ali umetanje može biti samo na stražnjem kraju reda.
Izlazno ograničeni Deque: U izlazno ograničenom redu, umetanje se može obaviti s oba kraja, ali brisanje se vrši samo na jednom kraju, tj. Prednjem kraju reda.
Također možemo implementirati hrpe i redove koristeći deque.
Osnovne operacije dodira
Slijede osnovne operacije koje se mogu izvoditi na dequeu.
- umetni prednji dio: Umetnite ili dodajte predmet na prednjoj strani deque.
- insertLast: Umetnite ili dodajte predmet na stražnjoj strani rupe.
- deleteFront: Izbrišite ili uklonite stavku s prednje strane reda.
- izbriši posljednje: Izbrišite ili uklonite stavku sa stražnje strane reda.
- getFront: Dohvaća prednju stavku u dequeu.
- getLast: Dohvaća zadnju stavku u redu čekanja.
- prazno je: Provjerava je li deque prazan.
- puno je: Provjerava je li deque pun.
i Ilustracija
Prazni deque predstavljen je na sljedeći način:
kako deklarirati povezani popis u javi -
Dalje, umetnemo element 1 sprijeda.
Sada ubacujemo element 3 straga.
Dalje, dodajemo element 5 sprijeda i kada se prednje točke povećavaju na 4.
Zatim umetnemo elemente 7 straga i 9 sprijeda. Deque će izgledati kako je prikazano u nastavku.
Dalje, uklonimo element s prednje strane.
Dakle, vidimo da kada se elementi umetnu sprijeda, prednji se položaj smanjuje, dok se povećava kada se element uklanja. Za stražnji kraj, položaj se povećava za umetanje i smanjuje za uklanjanje .
i Provedba
Implementacija 100 ++ touch
Možemo implementirati deque u C ++ pomoću polja kao i povezanog popisa. Osim toga, Standard Template Library (STL) ima klasu “deque” koja implementira sve funkcije za ovu strukturu podataka.
Implementacija niza deque-a data je u nastavku. Kako se radi o dvostrukom redu, za implementaciju smo koristili kružne nizove.
#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; } Izlaz:
Umetnite element 1 na stražnji kraj
umetnite element 3 na stražnjem kraju
stražnji element šupljine 3
Nakon deletereara, straga = 1
umetanje elementa 5 na prednjem kraju
prednji element šupljine 5
Nakon deletefront, front = 1
Prebrojavanje implementacije Jave
Deque sučelje u Javi, 'java.util.Deque' izvedeno je iz sučelja 'java.util.Queue'. Deque se može koristiti kao red (prvi ulaz, prvi izlaz) ili skup (zadnji ulaz, prvi izlaz). Te implementacije rade brže od povezanog popisa.
što je shockwave flash datoteka
Dolje je data hijerarhija za Deque sučelje u Javi.
Moramo se sjetiti nekoliko točaka o sučelju Deque u Javi:
- Implementacija nije sigurna u niti jer nema vanjske sinkronizacije.
- Deque ne podržava istodobnost u više niti.
- Dequeovi implementirani pomoću polja ne dopuštaju upotrebu NULL elemenata.
- Nizovima je dopušteno rasti prema zahtjevima, pri čemu su dvije najvažnije značajke kapacitet bez ograničenja i podrška za promjenjivi niz.
Slijede razne metode koje podržava sučelje Deque:
najbolji program za otvaranje xml datoteka
| Nemoj. | Metoda | Opis |
|---|---|---|
| 7 | iterator () | Vraća iterator za deque. |
| 1 | dodaj (element) | Dodaje element u rep. |
| dva | addFirst (element) | Dodaje element u glavu / sprijeda. |
| 3 | addLast (element) | Dodaje element u rep / stražnji dio. |
| 4 | ponuda (element) | Dodaje element u rep; vraća logičku vrijednost da naznači je li umetanje uspješno. |
| 5 | offerFirst (element) | Dodaje element u glavu; vraća logičku vrijednost da naznači je li umetanje uspješno. |
| 6 | offerLast (element) | Dodaje element u rep; vraća logičku vrijednost da naznači je li umetanje uspješno. |
| 8 | silazniIterator () | Vraća iterator koji ima obrnuti redoslijed za ovaj deque. |
| 9 | potisak (element) | Dodaje element u glavu deque. |
| 10 | pop (element) | Uklanja element s glave deque-a i vraća ga. |
| jedanaest | removeFirst () | Uklanja element na čelu šupljine. |
| 12 | removeLast () | Uklanja element na repu deque-a. |
| 13 | anketa() | Dohvaća i uklanja prvi element deque-a (predstavljen glavom deque-a); vraća NULL ako je deque prazan. |
| 14 | anketaPrvo () | Dohvaća i uklanja prvi element ove deque; vraća null ako je ovaj deque prazan. |
| petnaest | pollLast () | Dohvaća i uklanja posljednji element ove rupe; vraća null ako je ovaj deque prazan. |
| 16 | zaviriti () | Dohvaća glavu (prvi element deque-a) reda koji je predstavljen ovom deque-om; vraća null ako je ovaj deque prazan. Napomena: Ova operacija ne uklanja element. |
| 17 | peekFirst () | Dohvaća prvi element ove deque; vraća null ako je ovaj deque prazan. Napomena: Ova operacija ne uklanja element. |
| 18 | peekLast () | Dohvaća zadnji element ove deque ili vraća null ako je ova deque prazna. Napomena: Ova operacija ne uklanja element. |
Sljedeća implementacija Jave prikazuje razne gore spomenute operacije.
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); } } Izlaz:
I (11, 7, 3, 1, 5, 9, 13)
Standardni iterator
11 7 3 1 5 9 13
Obrnuti iterator
13 9 5 1 3 7 11
Zavirite 11
Nakon zavirenja: (11, 7, 3, 1, 5, 9, 13)
Pop 11
Nakon pop-a: (7, 3, 1, 5, 9, 13)
Sadrži element 3 ?: true
Deque nakon uklanjanja prvih i posljednjih elemenata: (3, 1, 5, 9)
U gore navedenom programu koristili smo Deque sučelje Java i definirali smo deque cjelobrojnih elemenata. Zatim smo izvršili razne operacije na ovom dequeu i prikazali rezultate tih operacija.
Prijave
Deque se može koristiti u nekim od sljedećih aplikacija.
# 1) Algoritam zakazivanja: Algoritam raspoređivanja, 'A-ukrasti algoritam raspoređivanja', implementira zakazivanje zadataka za različite procesore u višeprocesorskom sustavu. Ova implementacija koristi deque, a procesor dobiva prvi element iz dequea za izvršenje.
# 2) Poništavanje popisa aktivnosti: U softverskim aplikacijama imamo mnogo radnji. Jedno je 'poništi'. Kad smo više puta izvršili akciju poništavanja, sve se te radnje spremaju na popis. Ovaj se popis održava kao deque tako da možemo lako dodavati / uklanjati unose s bilo kojeg kraja.
# 3) Uklonite unose nakon nekog vremena: Aplikacije osvježavaju unose na svom popisu, poput aplikacija koje navode unose dionica itd. Ove aplikacije uklanjaju unose nakon nekog vremena i ubacuju nove unose. To se radi pomoću deque-a.
Zaključak
Deque je dvostruki red koji nam omogućuje dodavanje / uklanjanje elemenata s oba kraja, tj. Sprijeda i straga, reda. Deque se može implementirati pomoću polja ili povezanih popisa. Međutim, imamo i klasu Standard Template Library (STL) koja implementira razne operacije Dequea.
U Javi imamo Deque sučelje koje se nasljeđuje od sučelja reda za implementaciju Dequea. Osim osnovnih standardnih operacija Dequea, ovo sučelje podržava i razne druge operacije koje se mogu izvoditi na Dequeu.
Deque se obično koristi za aplikacije koje zahtijevaju dodavanje / uklanjanje elemenata s oba kraja. Također se uglavnom koristi za raspoređivanje procesora u višeprocesorskim sustavima.
=> Pogledajte kompletnu seriju C ++ treninga
Preporučena literatura
- Redoslijed prioriteta u STL-u
- Što je usporedno testiranje (naučite na primjerima)
- Python DateTime Vodič s primjerima
- Razvrstavanje ljuske na C ++ s primjerima
- Izreži naredbu u Unixu s primjerima
- Sintaksa naredbe Unix Cat, mogućnosti s primjerima
- Primjena pokazivača u MongoDB-u s primjerima
- Ls naredba u Unixu s primjerima