double ended queue c with examples
En grundig opplæring om Deque eller dobbeltkø i C ++. Opplæringen forklarer hva som er Deque, grunnleggende operasjoner, C ++ og Java-implementering og applikasjoner:
Dobbeltkø eller bare kalt “Deque” er en generalisert versjon av køen.
Forskjellen mellom kø og Deque er at den ikke følger FIFO-tilnærmingen (First In, First Out). Det andre trekket ved Deque er at vi kan sette inn og fjerne elementer fra enten for- eller bakenden.
=> Les gjennom Easy C ++ Training Series
Hva du vil lære:
- Dobbelt slutt kø-klassifisering
- Grunnleggende berøringsoperasjoner
- og illustrasjon
- og implementering
- applikasjoner
- Konklusjon
- Anbefalt lesing
Dobbelt slutt kø-klassifisering
Deque kan klassifiseres som følger:
Inngang med begrenset berøring; I inngangsbegrenset kan sletting gjøres fra begge ender, men innsetting kan bare gjøres i bakenden av køen.
Utgangsbegrenset Deque: I den utgangsbegrensede køen kan innsetting gjøres fra begge ender, men sletting gjøres bare i den ene enden, dvs. frontenden av køen.
Vi kan også implementere stabler og køer ved hjelp av deque.
Grunnleggende berøringsoperasjoner
Følgende er de grunnleggende operasjonene som kan utføres på deque.
- sett inn front: Sett inn eller legg til et element på forsiden av duken.
- insertLast: Sett inn eller legg til et element på baksiden av duken.
- deleteFront: Slett eller fjern elementet fra forsiden av køen.
- slett sist: Slett eller fjern elementet fra baksiden av køen.
- getFront: Henter fremre element i deken.
- getLast: Henter det siste elementet i køen.
- er tom: Sjekker om dekken er tom.
- er full: Sjekker om dekken er full.
og illustrasjon
En tom deque er representert som følger:
hvordan åpne torrented filer mac
Deretter setter vi inn element 1 foran.
Nå setter vi inn element 3 bak.
Deretter legger vi til element 5 foran og når det økes, peker fronten til 4.
Deretter setter vi inn element 7 bak og 9 foran. Dekken vil se ut som vist nedenfor.
La oss deretter fjerne et element fra fronten.
Dermed ser vi at når elementene settes inn foran, blir frontposisjonen dekrementert mens den økes når et element fjernes. For bakenden økes stillingen for innsetting og reduseres for fjerning .
og implementering
100 ++ touch Implementering
Vi kan implementere en deque i C ++ ved hjelp av arrays samt en koblet liste. Bortsett fra dette, har Standard Template Library (STL) en klasse 'deque' som implementerer alle funksjonene for denne datastrukturen.
Array-implementeringen av deque er gitt nedenfor. Siden det er en kø med to ender, har vi brukt sirkulære matriser for implementering.
#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; } Produksjon:
Sett inn element 1 i bakenden
sett inn element 3 på bakenden
bakre element av deque 3
Etter forsinkelse, bak = 1
innsettingselement 5 i frontenden
frontelement av deque 5
Etter strykefronten, front = 1
Gjennomføring av Java-implementering
Deque-grensesnittet i Java, 'java.util.Deque' er avledet fra 'java.util.Queue' -grensesnittet. Deque kan brukes som kø (First In, First Out) eller en stack (Last In, First Out). Disse implementeringene fungerer raskere enn den koblede listen.
spørsmål om kvalitetssikring analytiker jobbintervju
Nedenfor er hierarkiet for Deque-grensesnittet i Java.
Vi må huske noen få punkter om Deque-grensesnittet i Java:
- Implementeringen er ikke trådsikker, da det ikke er noen ekstern synkronisering.
- Deque støtter ikke samtidighet med flere tråder.
- Deques implementert ved hjelp av arrays tillater ikke bruk av NULL-elementer.
- Arrays får lov til å vokse i henhold til kravene, med begrensningsfri kapasitet og størrelsesstørrelse for størrelsesstørrelse som er de to viktigste funksjonene.
Følgende er de forskjellige metodene som støttes av Deque-grensesnittet:
oracle sql intervju spørsmål og svar for 3 års erfaring
| Ikke. | Metode | Beskrivelse |
|---|---|---|
| 7 | iterator () | Returnerer en iterator for deken. |
| 1 | legg til (element) | Legger til et element i halen. |
| to | addFirst (element) | Legger til et element i hodet / fronten. |
| 3 | addLast (element) | Legger til et element i halen / baksiden. |
| 4 | tilbud (element) | Legger til et element i halen; returnerer en boolsk verdi for å indikere om innsettingen var vellykket. |
| 5 | offerFirst (element) | Legger til et element i hodet; returnerer en boolsk verdi for å indikere om innsettingen var vellykket. |
| 6 | offerLast (element) | Legger til et element i halen; returnerer en boolsk verdi for å indikere om innsettingen var vellykket. |
| 8 | synkendeIterator () | Returnerer en iterator som har omvendt rekkefølge for denne deken. |
| 9 | trykk (element) | Legger til et element i hodet til deque. |
| 10 | pop (element) | Fjerner et element fra hodet til deque og returnerer det. |
| elleve | removeFirst () | Fjerner elementet på toppen av dekket. |
| 12 | removeLast () | Fjerner elementet på baksiden av deken. |
| 1. 3 | avstemming() | Henter ut og fjerner det første elementet i deken (representert av hodet til deken); returnerer NULL hvis dekken er tom. |
| 14 | pollFirst () | Henter og fjerner det første elementet i denne deken; returnerer null hvis denne deken er tom. |
| femten | pollLast () | Henter og fjerner det siste elementet i denne deken; returnerer null hvis denne deken er tom. |
| 16 | kikke () | Henter hodet (første element i deque) til køen representert av denne deque; returnerer null hvis denne deken er tom. Merk: Denne operasjonen fjerner ikke elementet. |
| 17 | peekFirst () | Henter det første elementet i denne deken; returnerer null hvis denne deken er tom. Merk: Denne operasjonen fjerner ikke elementet. |
| 18 | peekLast () | Henter det siste elementet i denne deken, eller returnerer null hvis denne deken er tom. Merk: Denne operasjonen fjerner ikke elementet. |
Følgende Java-implementering demonstrerer de forskjellige operasjonene som er diskutert ovenfor.
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); } } Produksjon:
Og (11, 7, 3, 1, 5, 9, 13)
Standard Iterator
11 7 3 1 5 9 13
Omvendt Iterator
13 9 5 1 3 7 11
Kikk 11
Etter titt: (11, 7, 3, 1, 5, 9, 13)
Pop 11
Etter pop: (7, 3, 1, 5, 9, 13)
Inneholder element 3 ?: sant
Dekke etter fjerning av første og siste element: (3, 1, 5, 9)
I programmet ovenfor har vi brukt Deque-grensesnittet til Java, og vi definerte en deque av heltallelementer. Deretter utførte vi forskjellige operasjoner på denne deque og resultatene av disse operasjonene vises.
applikasjoner
Deque kan brukes i noen av følgende applikasjoner.
# 1) Planleggingsalgoritme: En planleggingsalgoritme, 'A-stjele planleggingsalgoritme' implementerer oppgaveplanlegging for forskjellige prosessorer i flerprosessorsystemet. Denne implementeringen bruker deque og prosessoren får det første elementet fra deque for utføring.
# 2) Angre listen over aktiviteter: I programvare har vi mange handlinger. Den ene er 'angre'. Når vi har utført angrepet mange ganger, lagres alle disse handlingene i en liste. Denne listen opprettholdes som en deque slik at vi lett kan legge til / fjerne oppføringer fra hvilken som helst ende.
# 3) Fjern postene etter en stund: Apper oppdaterer oppføringene i listen som apper som viser lageroppføringene osv. Disse appene fjerner oppføringene etter en stund og setter også inn nye oppføringer. Dette gjøres ved hjelp av en deque.
Konklusjon
Deque er en dobbeltkølet kø som lar oss legge til / fjerne elementer fra begge ender, dvs. foran og bak, i køen. Deque kan implementeres ved hjelp av arrays eller koblede lister. Imidlertid har vi også en Standard Template Library (STL) klasse som implementerer de forskjellige operasjonene til Deque.
I Java har vi et Deque-grensesnitt som er arvet fra køgrensesnittet for å implementere Deque. Bortsett fra de grunnleggende standardoperasjonene til Deque, støtter dette grensesnittet forskjellige andre operasjoner som kan utføres på Deque.
Deque brukes vanligvis til applikasjoner som krever tilsetning / fjerning av elementer fra begge ender. Det brukes også mest ved planlegging av prosessorer i flerprosessorsystemer.
=> Sjekk ut den komplette C ++ treningsserien
Anbefalt lesing
- Prioritetskø I STL
- Hva er sammenligningstesting (Lær med eksempler)
- Python DateTime Tutorial med eksempler
- Skalsortering i C ++ med eksempler
- Klipp kommandoen i Unix med eksempler
- Unix Cat Command Syntax, Alternativer med eksempler
- Bruk av markør i MongoDB med eksempler
- Ls Command i Unix med eksempler