double ended queue c with examples
Poglobljena vadnica o čakalni vrsti Deque ali dvojnikih v jeziku C ++. Vadnica pojasnjuje, kaj je Deque, osnovne operacije, implementacija C ++ in Java in aplikacije:
Dvostranska vrsta ali preprosto imenovana »Deque« je splošna različica Čakalne vrste.
Razlika med Queue in Deque je v tem, da ne sledi pristopu FIFO (First In, First Out). Druga značilnost Deque je, da lahko vstavljamo in odstranjujemo elemente s sprednjih ali zadnjih koncev.
=> Preberite serijo Easy C ++ Training Series
Kaj se boste naučili:
- Klasifikacija dvojne čakalne vrste
- Osnovne operacije na dotik
- in ilustracija
- in izvajanje
- Aplikacije
- Zaključek
- Priporočeno branje
Klasifikacija dvojne čakalne vrste
Deke lahko razvrstimo na naslednji način:
Vnos z omejenim dotikom; Pri omejitvi vnosa je mogoče izbrisati z obeh koncev, vstavljanje pa je mogoče le na zadnjem koncu čakalne vrste.
Izhodno omejena Deque: V čakalno vrsto, omejeno z izhodom, je mogoče vstaviti z obeh koncev, brisanje pa samo na enem koncu, tj. Na sprednjem koncu čakalne vrste.
Lahko tudi implementiramo sklade in čakalne vrste z uporabo deque.
Osnovne operacije na dotik
Sledijo osnovne operacije, ki jih je mogoče izvajati na deque.
- vstavite spredaj: Vstavite ali dodajte element na sprednji strani okna.
- insertLast: Vstavite ali dodajte element na zadnji strani okna.
- deleteFront: Izbrišite ali odstranite element s sprednje strani čakalne vrste.
- izbriši zadnji: Izbrišite ali odstranite element s hrbtne strani čakalne vrste.
- getFront: Pridobi sprednji element v oknu.
- getLast: Pridobi zadnji element v čakalni vrsti.
- je prazno: Preveri, ali je deque prazen.
- je polna: Preveri, ali je deque poln.
in ilustracija
Prazna deka je predstavljena na naslednji način:
orodje za popravilo programske opreme windows 10
Nato spredaj vstavimo element 1.
Zdaj vstavimo element 3 zadaj.
Nato na sprednji strani dodamo element 5 in ko povečamo sprednje točke na 4.
Nato vstavimo elemente 7 zadaj in 9 spredaj. Deque bo videti, kot je prikazano spodaj.
Nato odstranimo element s sprednje strani.
Tako vidimo, da ko se elementi vstavijo spredaj, se sprednji položaj zmanjša, medtem ko se poveča, ko se element odstrani. Za zadnji del se položaj poveča za vstavljanje in zmanjša za odstranitev .
in izvajanje
Izvedba 100 ++ touch
V C ++ lahko izvedemo deque z uporabo nizov in povezanega seznama. Poleg tega ima standardna knjižnica predlog (STL) razred 'deque', ki izvaja vse funkcije za to strukturo podatkov.
Izvedba zaporedja nizov je podana spodaj. Ker gre za dvojno vrsto, smo za izvedbo uporabili krožne nize.
#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; } Izhod:
Vstavite element 1 na zadnji del
vzorec preskusnega načrta za spletno aplikacijo
vstavite element 3 na zadnji del
3. zadnji element v ohišju 3
Po deleterearju zadaj = 1
vstavite element 5 na sprednji konec
5. sprednji element deque 5
Po izbrisu spredaj spredaj = 1
Ponovno štetje implementacije Jave
Deque vmesnik v Javi, 'java.util.Deque' izhaja iz vmesnika 'java.util.Queue'. Deque se lahko uporablja kot čakalna vrsta (First In, First Out) ali kot sklad (Last In, First Out). Te izvedbe delujejo hitreje kot povezani seznam.
Spodaj je prikazana hierarhija vmesnika Deque v Javi.
Zapomniti si moramo nekaj točk o vmesniku Deque v Javi:
- Izvedba ni varna pred nitmi, ker ni zunanje sinhronizacije.
- Deque ne podpira sočasnosti več niti.
- Dequeove izvedbe, ki uporabljajo matrike, ne dovoljujejo uporabe elementov NULL.
- Nizom je dovoljeno, da rastejo v skladu z zahtevami, pri čemer sta najpomembnejši lastnosti zmogljivosti brez omejitev in podpore spremenljivega niza.
Sledijo različne metode, ki jih podpira vmesnik Deque:
Vprašanja in odgovori na razgovore za razvijalce sql pdf
| Ne. | Metoda | Opis |
|---|---|---|
| 7. | iterator () | Vrne iterator za deque. |
| 1. | dodaj (element) | Repu doda element. |
| dva | addFirst (element) | Doda element na glavo / spredaj. |
| 3. | addLast (element) | Doda element na rep / zadaj. |
| 4. | ponudba (element) | Repu doda element; vrne logično vrednost, ki označuje, ali je bilo vstavljanje uspešno. |
| 5. | offerFirst (element) | Glavi doda element; vrne logično vrednost, ki označuje, ali je bilo vstavljanje uspešno. |
| 6. | offerLast (element) | Repu doda element; vrne logično vrednost, ki označuje, ali je bilo vstavljanje uspešno. |
| 8. | descendingIterator () | Vrne iterator, ki ima obratni vrstni red za to deque. |
| 9. | potisni (element) | Doda element v glavo deque. |
| 10. | pop (element) | Odstrani element iz glave deque in ga vrne. |
| enajst | removeFirst () | Odstrani element na vrhu deke. |
| 12. | removeLast () | Odstrani element na repu deke. |
| 13. | anketa() | Pridobi in odstrani prvi element deque (predstavljen z glavo deque); vrne NULL, če je deque prazen. |
| 14. | anketaPrvi () | Pridobi in odstrani prvi element te enote; vrne null, če je ta deque prazen. |
| petnajst | pollLast () | Pridobi in odstrani zadnji element te enote; vrne null, če je ta deque prazen. |
| 16. | pokukati () | Pridobi glavo (prvi element deque) čakalne vrste, ki jo predstavlja ta deque; vrne null, če je ta deque prazen. Opomba: Ta postopek ne odstrani elementa. |
| 17. | peekFirst () | Pridobi prvi element tega deque; vrne null, če je ta deque prazen. Opomba: Ta postopek ne odstrani elementa. |
| 18. | peekLast () | Pridobi zadnji element tega deque ali vrne null, če je ta deque prazen. Opomba: Ta postopek ne odstrani elementa. |
Naslednja izvedba Java prikazuje različne zgoraj obravnavane 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); } } Izhod:
In (11, 7, 3, 1, 5, 9, 13)
Standardni iterator
11 7 3 1 5 9 13
Reverse Iterator
13 9 5 1 3 7 11
Pokukajte 11.
Po poku: (11, 7, 3, 1, 5, 9, 13)
Pop 11
Po pop: (7, 3, 1, 5, 9, 13)
Vsebuje element 3 ?: true
Deque po odstranitvi prvih in zadnjih elementov: (3, 1, 5, 9)
V zgornjem programu smo uporabili vmesnik Deque Java in definirali deque celoštevilskih elementov. Nato smo izvedli različne operacije na tej plošči in prikazali rezultate teh operacij.
Aplikacije
Deque lahko uporabljate v nekaterih naslednjih aplikacijah.
# 1) Algoritem razporejanja: Algoritem razporejanja, 'A-ukradite razpored algoritma', izvaja razporejanje nalog za različne procesorje v večprocesorskem sistemu. Ta izvedba uporablja deque in procesor dobi prvi element iz dequea za izvedbo.
# 2) Razveljavi seznam dejavnosti: V programskih aplikacijah imamo veliko dejanj. Ena je 'razveljavi'. Ko smo večkrat izvedli razveljavitev, se vsa ta dejanja shranijo na seznam. Ta seznam se vzdržuje kot deque, tako da lahko z katerega koli konca zlahka dodajamo / odstranjujemo vnose.
# 3) Odstranite vnose čez nekaj časa: Aplikacije osvežijo vnose na svojem seznamu, na primer aplikacije, ki navajajo zaloge itd. Te aplikacije jih po določenem času odstranijo in vstavijo tudi nove. To se naredi z uporabo deque.
Zaključek
Deque je dvojna vrsta, ki nam omogoča dodajanje / odstranjevanje elementov na obeh koncih, tj. Spredaj in zadaj, čakalne vrste. Deque lahko izvedemo z uporabo nizov ali povezanih seznamov. Vendar imamo tudi razred Standard Template Library (STL), ki izvaja različne operacije Dequea.
V Javi imamo vmesnik Deque, ki je podedovan od vmesnika čakalne vrste za izvedbo Deque. Poleg osnovnih standardnih operacij Deque ta vmesnik podpira tudi druge druge operacije, ki jih je mogoče izvajati na Dequeu.
Deque se običajno uporablja za aplikacije, ki zahtevajo dodajanje / odstranjevanje elementov z obeh koncev. Prav tako se večinoma uporablja pri razporejanju procesorjev v večprocesorskih sistemih.
=> Oglejte si celotno serijo usposabljanj za C ++