logo

TechCodeview

Deque (ali dvojno končana čakalna vrsta)

V tem članku bomo obravnavali dvostransko čakalno vrsto ali deque. Najprej bi morali videti kratek opis čakalne vrste.

Kaj je čakalna vrsta?

Čakalna vrsta je podatkovna struktura, v kateri bo tisto, kar pride prej, najprej šlo ven, in sledi pravilniku FIFO (First-In-First-Out). Vstavljanje v čakalno vrsto se izvede z enega konca, znanega kot zadnji del ali rep, medtem ko je brisanje izvedeno z drugega konca, znanega kot sprednji del ali glavo čakalne vrste.

stlc

Primer čakalne vrste iz resničnega sveta je vrsta za vstopnice zunaj kinematografske dvorane, kjer oseba, ki vstopi prva v čakalni vrsti, prejme vstopnico prva, oseba, ki vstopi zadnja v čakalni vrsti, pa jo prejme nazadnje.

Kaj je Deque (ali dvojno končana čakalna vrsta)

Deque pomeni Double Ended Queue. Deque je linearna podatkovna struktura, kjer se operacije vstavljanja in brisanja izvajajo z obeh koncev. Lahko rečemo, da je deque posplošena različica čakalne vrste.

Čeprav je vstavljanje in brisanje v deque mogoče izvesti na obeh koncih, ni v skladu s pravilom FIFO. Predstavitev deque je podana na naslednji način -

Deque (ali dvostranska čakalna vrsta)

Vrste deque

Obstajata dve vrsti deque -

  • Čakalna vrsta z omejenim vnosom
  • Čakalna vrsta z omejenim izhodom

Čakalna vrsta z omejenim vnosom

V čakalni vrsti z omejenim vnosom je mogoče operacijo vstavljanja izvesti samo na enem koncu, brisanje pa na obeh koncih.

Deque (ali dvojno končana čakalna vrsta)

Čakalna vrsta z omejenim izhodom

V čakalni vrsti z omejenim izhodom se lahko operacija brisanja izvede samo na enem koncu, medtem ko se lahko vstavljanje izvede na obeh koncih.

Deque (ali dvojno končana čakalna vrsta)

Operacije, izvedene na deque

Obstajajo naslednje operacije, ki jih je mogoče uporabiti za deque -

  • Vstavljanje spredaj
  • Vstavljanje zadaj
  • Izbris spredaj
  • Izbris zadaj

Poleg zgoraj navedenih operacij lahko izvedemo tudi operacije peek v deque. Z operacijo peek lahko dobimo sprednje in zadnje elemente deque deque. Torej so poleg zgornjih operacij v dequeu podprte tudi naslednje operacije -

bourne-again školjka
  • Vzemite sprednji predmet iz deque
  • Vzemite zadnji predmet iz deque
  • Preverite, ali je deque poln ali ne
  • Preveri, ali je deque prazna ali ne

Zdaj pa na primeru razumejmo operacijo, izvedeno na deque.

Vstavljanje na sprednjem koncu

Pri tej operaciji se element vstavi s sprednjega dela čakalne vrste. Pred izvedbo operacije moramo najprej preveriti, ali je čakalna vrsta polna ali ne. Če čakalna vrsta ni polna, lahko element vstavite s sprednje strani z uporabo spodnjih pogojev -

  • Če je čakalna vrsta prazna, sta zadnji in sprednji del inicializirana z 0. Zdaj bosta oba kazala na prvi element.
  • V nasprotnem primeru preverite položaj sprednje strani, če je sprednja stran manjša od 1 (sprednja stran<1), then reinitialize it by front = n - 1, tj. zadnji indeks matrike.
Deque (ali dvojno končana čakalna vrsta)

Vložek na zadnji strani

Pri tej operaciji je element vstavljen z zadnjega dela čakalne vrste. Pred izvedbo operacije moramo ponovno preveriti, ali je čakalna vrsta polna ali ne. Če čakalna vrsta ni polna, lahko element vstavite z zadnjega konca z uporabo spodnjih pogojev -

  • Če je čakalna vrsta prazna, sta zadnji in sprednji del inicializirana z 0. Zdaj bosta oba kazala na prvi element.
  • V nasprotnem primeru povečajte zadnji del za 1. Če ima zadnji del zadnji indeks (ali velikost - 1), ga moramo namesto povečanja za 1 nastaviti na 0.
Deque (ali dvojno končana čakalna vrsta)

Izbris na sprednji strani

Pri tej operaciji se element izbriše s sprednjega dela čakalne vrste. Pred izvedbo operacije moramo najprej preveriti, ali je čakalna vrsta prazna ali ne.

Če je čakalna vrsta prazna, tj. spredaj = -1, je to pogoj premajhnega pretoka in ne moremo izvesti brisanja. Če čakalna vrsta ni polna, lahko element vstavite s sprednje strani z uporabo spodnjih pogojev -

kako inicializirati matriko v Javi

Če ima deque samo en element, nastavite rear = -1 in front = -1.

V nasprotnem primeru, če je fronta na koncu (to pomeni fronta = size - 1), nastavite front = 0.

krožni razpored

Drugače povečajte sprednji del za 1 (tj. sprednji = sprednji + 1).

Deque (ali dvojno končana čakalna vrsta)

Izbris na zadnjem koncu

Pri tej operaciji se element izbriše z zadnjega dela čakalne vrste. Pred izvedbo operacije moramo najprej preveriti, ali je čakalna vrsta prazna ali ne.

Če je čakalna vrsta prazna, tj. spredaj = -1, je to pogoj premajhnega pretoka in ne moremo izvesti brisanja.

Če ima deque samo en element, nastavite rear = -1 in front = -1.

Če je zadaj = 0 (zadaj je spredaj), potem nastavite zadaj = n - 1.

V nasprotnem primeru zmanjšajte zadnji del za 1 (ali zadnji = zadnji -1).

Deque (ali dvojno končana čakalna vrsta)

Ček prazen

Ta operacija se izvede za preverjanje, ali je deque prazna ali ne. Če je front = -1, pomeni, da je deque prazen.

Preverite polno

Ta operacija se izvede za preverjanje, ali je deque poln ali ne. Če je spredaj = zadaj + 1 ali spredaj = 0 in zadaj = n - 1, to pomeni, da je deque poln.

Časovna kompleksnost vseh zgornjih operacij deque je O(1), tj. konstantna.

Aplikacije deque

  • Deque se lahko uporablja tako kot sklad kot kot čakalna vrsta, saj podpira obe operaciji.
  • Deque lahko uporabimo kot preverjalnik palindroma, kar pomeni, da če beremo niz z obeh koncev, bi bil niz enak.

Izvedba deque

Zdaj pa si oglejmo implementacijo deque v programskem jeziku C.

pojasni neodvisnost podatkov 
 #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; }

Izhod:

Deque (ali dvojno končana čakalna vrsta)

Torej, to je vse o članku. Upam, da vam bo članek koristen in informativen.