logo

TechCodeview

Deque (eller dobbeltkø)

I denne artikel vil vi diskutere den dobbelte kø eller deque. Vi skal først se en kort beskrivelse af køen.

Hvad er en kø?

En kø er en datastruktur, hvor det, der kommer først, går først ud, og den følger FIFO-politikken (First-In-First-Out). Indsættelse i køen sker fra den ene ende kendt som bagende eller den hale, hvorimod sletningen sker fra en anden ende kendt som forenden eller den hoved af køen.

min skærmstørrelse

Eksemplet i den virkelige verden på en kø er billetkøen uden for en biografsal, hvor den, der træder først ind i køen, får billetten først, og den, der kommer sidst i køen, får billetten til sidst.

Hvad er en Deque (eller dobbeltkø)

Deque står for Double Ended Queue. Deque er en lineær datastruktur, hvor indsættelses- og sletningsoperationerne udføres fra begge ender. Vi kan sige, at deque er en generaliseret version af køen.

Selvom indsættelse og sletning i en deque kan udføres i begge ender, følger den ikke FIFO-reglen. Repræsentationen af ​​et deque er givet som følger -

Deque (eller dobbeltkø)

Typer af deque

Der er to typer af deque -

  • Input begrænset kø
  • Output begrænset kø

Input begrænset kø

I inputbegrænset kø kan indsættelsesoperationen kun udføres i den ene ende, mens sletning kan udføres fra begge ender.

Deque (eller dobbeltkø)

Output begrænset kø

I outputbegrænset kø kan sletningsoperation kun udføres i den ene ende, mens indsættelse kan udføres fra begge ender.

Deque (eller dobbeltkø)

Operationer udført på bord

Der er følgende operationer, der kan anvendes på en bordplade -

  • Indsættelse foran
  • Indsættelse bagpå
  • Sletning foran
  • Sletning bagpå

Vi kan også udføre kig-operationer i deque sammen med de operationer, der er anført ovenfor. Gennem kig-betjening kan vi få dequeens for- og bagelementer af dequeen. Så udover ovenstående operationer understøttes følgende operationer også i deque -

np.random.rand
  • Få den forreste vare fra deque
  • Hent den bagerste vare fra deque
  • Tjek om deque er fuld eller ej
  • Kontrollerer, om bordet er tomt eller ej

Lad os nu forstå den operation, der udføres ved hjælp af et eksempel.

Indsættelse i forenden

I denne operation indsættes elementet fra forenden af ​​køen. Før vi implementerer operationen, skal vi først kontrollere, om køen er fuld eller ej. Hvis køen ikke er fuld, så kan elementet indsættes fra frontenden ved at bruge nedenstående betingelser -

  • Hvis køen er tom, initialiseres både bag og front med 0. Nu vil begge pege på det første element.
  • Ellers skal du kontrollere frontens position, hvis fronten er mindre end 1 (foran<1), then reinitialize it by front = n - 1, dvs. det sidste indeks af arrayet.
Deque (eller dobbeltkø)

Indsættelse i bagenden

I denne operation indsættes elementet fra den bagerste ende af køen. Før vi implementerer operationen, skal vi først kontrollere igen, om køen er fuld eller ej. Hvis køen ikke er fuld, kan elementet indsættes fra bagenden ved at bruge nedenstående betingelser -

salman khan alder
  • Hvis køen er tom, initialiseres både bag og front med 0. Nu vil begge pege på det første element.
  • Ellers skal du øge bagsiden med 1. Hvis bagsiden er ved sidste indeks (eller størrelse - 1), skal vi i stedet for at øge den med 1 gøre den lig med 0.
Deque (eller dobbeltkø)

Sletning i forenden

I denne operation slettes elementet fra forenden af ​​køen. Før vi implementerer operationen, skal vi først kontrollere, om køen er tom eller ej.

Hvis køen er tom, dvs. front = -1, er det underløbstilstanden, og vi kan ikke udføre sletningen. Hvis køen ikke er fuld, så kan elementet indsættes fra frontenden ved at bruge nedenstående betingelser -

Hvis deque kun har ét element, skal du indstille bag = -1 og front = -1.

Ellers, hvis forsiden er i slutningen (det betyder forside = størrelse - 1), skal du indstille forsiden = 0.

js multiline streng

Ellers øges forsiden med 1, (dvs. front = front + 1).

Deque (eller dobbeltkø)

Sletning i bagenden

I denne operation slettes elementet fra den bagerste ende af køen. Før vi implementerer operationen, skal vi først kontrollere, om køen er tom eller ej.

Hvis køen er tom, dvs. front = -1, er det underløbstilstanden, og vi kan ikke udføre sletningen.

Hvis deque kun har ét element, skal du indstille bag = -1 og front = -1.

Hvis bag = 0 (bag er foran), så sæt bag = n - 1.

Ellers skal du sænke den bageste med 1 (eller, bagsiden = bagsiden -1).

Deque (eller dobbeltkø)

Check tom

Denne handling udføres for at kontrollere, om deque er tom eller ej. Hvis front = -1, betyder det, at deque er tom.

Tjek fuld

Denne operation udføres for at kontrollere, om deque er fuld eller ej. Hvis front = bag + 1, eller front = 0 og bag = n - 1 betyder det, at deque er fuld.

Tidskompleksiteten af ​​alle de ovennævnte operationer af deque er O(1), dvs. konstant.

Anvendelser af deque

  • Deque kan bruges som både stak og kø, da det understøtter begge operationer.
  • Deque kan bruges som en palindrom checker betyder, at hvis vi læser strengen fra begge ender, ville strengen være den samme.

Implementering af deque

Lad os nu se implementeringen af ​​deque i programmeringssproget C.

klasse vs objekt java 
 #include #define size 5 int deque[size]; int f = -1, r = -1; // insert_front function will insert the value from the front void insert_front(int x) { if((f==0 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (r==-1)) { f=r=0; deque[f]=x; } else if(f==0) { f=size-1; deque[f]=x; } else { f=f-1; deque[f]=x; } } // insert_rear function will insert the value from the rear void insert_rear(int x) { if((f==0 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (r==-1)) { r=0; deque[r]=x; } else if(r==size-1) { r=0; deque[r]=x; } else { r++; deque[r]=x; } } // display function prints all the value of deque. void display() { int i=f; printf(&apos;
Elements in a deque are: &apos;); while(i!=r) { printf(&apos;%d &apos;,deque[i]); i=(i+1)%size; } printf(&apos;%d&apos;,deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at front is: %d&apos;, deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at rear is %d&apos;, deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=0; } else { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[r]); f=-1; r=-1; } else if(r==0) { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=size-1; } else { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=r-1; } } int main() { insert_front(20); insert_front(10); insert_rear(30); insert_rear(50); insert_rear(80); display(); // Calling the display function to retrieve the values of deque getfront(); // Retrieve the value at front-end getrear(); // Retrieve the value at rear-end delete_front(); delete_rear(); display(); // calling display function to retrieve values after deletion return 0; }

Produktion:

Deque (eller dobbeltkø)

Så det handler om artiklen. Håber, artiklen vil være nyttig og informativ for dig.