logo

TechCodeview

Deque (alebo dvojitý rad)

V tomto článku budeme diskutovať o dvojitom fronte alebo deque. Najprv by sme mali vidieť stručný popis frontu.

Čo je to rad?

Fronta je dátová štruktúra, v ktorej to, čo príde skôr, vyjde ako prvé a riadi sa politikou FIFO (prvý do seba, prvý von). Vkladanie do frontu sa vykonáva z jedného konca známeho ako zadný koniec alebo chvost, pričom vymazanie sa vykonáva z iného konca známeho ako predný koniec alebo hlavu z radu.

čo je prolog

Príkladom radu v reálnom svete je rad na lístky mimo kinosály, kde ten, kto vstúpi prvý v rade, dostane lístok ako prvý a ten, kto vstúpi ako posledný v rade, nakoniec dostane lístok.

Čo je to Deque (alebo dvojitý front)

Deque znamená Double Ended Queue. Deque je lineárna dátová štruktúra, kde sa operácie vkladania a vymazávania vykonávajú z oboch koncov. Môžeme povedať, že deque je zovšeobecnená verzia frontu.

Hoci vloženie a vymazanie v deque možno vykonať na oboch koncoch, nedodržiava pravidlo FIFO. Zastúpenie deque je uvedené takto -

Deque (alebo dvojitý rad)

Druhy deque

Existujú dva typy deque -

  • Obmedzený vstupný front
  • Výstup obmedzeného frontu

Obmedzený front vstupu

Vo fronte s obmedzeným vstupom možno operáciu vloženia vykonať iba na jednom konci, zatiaľ čo vymazanie možno vykonať z oboch koncov.

Deque (alebo dvojitý rad)

Výstup obmedzený front

Vo fronte s obmedzeným výstupom možno operáciu vymazania vykonať iba na jednom konci, zatiaľ čo vloženie možno vykonať z oboch koncov.

Deque (alebo dvojitý rad)

Operácie vykonávané na deque

Existujú nasledujúce operácie, ktoré možno použiť na deque -

  • Vloženie vpredu
  • Vkladanie vzadu
  • Výmaz vpredu
  • Výmaz vzadu

Spolu s operáciami uvedenými vyššie môžeme vykonávať aj operácie nahliadnutia v deque. Prostredníctvom funkcie peeku môžeme získať predné a zadné prvky deque. Takže okrem vyššie uvedených operácií sú v deque podporované aj nasledujúce operácie -

knn algoritmus
  • Získajte prednú položku z deque
  • Získajte zadnú položku z deque
  • Skontrolujte, či je deque plná alebo nie
  • Skontroluje, či je deque prázdny alebo nie

Teraz pochopme operáciu vykonanú na deque pomocou príkladu.

Vloženie na predný koniec

Pri tejto operácii sa prvok vloží z predného konca frontu. Pred realizáciou operácie musíme najskôr skontrolovať, či je front plný alebo nie. Ak fronta nie je plná, prvok možno vložiť z frontendu pomocou podmienok uvedených nižšie -

  • Ak je front prázdny, zadný aj predný sa inicializujú na 0. Teraz budú oba ukazovať na prvý prvok.
  • V opačnom prípade skontrolujte polohu prednej časti, ak je predná časť menšia ako 1 (predná časť<1), then reinitialize it by front = n - 1, t.j. posledný index poľa.
Deque (alebo dvojitý rad)

Vloženie na zadnom konci

Pri tejto operácii sa prvok vloží zo zadného konca frontu. Pred realizáciou operácie musíme najskôr znova skontrolovať, či je front plný alebo nie. Ak fronta nie je plná, prvok možno vložiť zo zadnej strany pomocou nižšie uvedených podmienok -

  • Ak je front prázdny, zadný aj predný sa inicializujú na 0. Teraz budú oba ukazovať na prvý prvok.
  • V opačnom prípade zväčšite zadnú časť o 1. Ak má zadná časť posledný index (alebo veľkosť - 1), potom namiesto zvýšenia o 1 ju musíme nastaviť na 0.
Deque (alebo dvojitý rad)

Odstránenie na prednej strane

Pri tejto operácii sa prvok vymaže z prednej časti frontu. Pred realizáciou operácie musíme najprv skontrolovať, či je front prázdny alebo nie.

abecedu podľa čísla

Ak je front prázdny, t.j. front = -1, ide o podmienku podtečenia a vymazanie nemôžeme vykonať. Ak fronta nie je plná, prvok možno vložiť z frontendu pomocou podmienok uvedených nižšie -

Ak má deque iba jeden prvok, nastavte zadné = -1 a predné = -1.

V opačnom prípade, ak je predná strana na konci (to znamená predná strana = veľkosť - 1), nastavte prednú stranu = 0.

java catch skúste

V opačnom prípade zvýšte prednú časť o 1 (t. j. predná strana = predná strana + 1).

Deque (alebo dvojitý rad)

Výmaz na zadnej strane

Pri tejto operácii sa prvok odstráni zo zadnej časti frontu. Pred realizáciou operácie musíme najprv skontrolovať, či je front prázdny alebo nie.

Ak je front prázdny, t.j. front = -1, ide o podmienku podtečenia a vymazanie nemôžeme vykonať.

Ak má deque iba jeden prvok, nastavte zadné = -1 a predné = -1.

Ak zadná časť = 0 (zadná časť je vpredu), nastavte zadnú časť = n - 1.

V opačnom prípade znížte zadnú časť o 1 (alebo, zadná = zadná -1).

Deque (alebo dvojitý rad)

Kontrola je prázdna

Táto operácia sa vykonáva na kontrolu, či je deque prázdny alebo nie. Ak front = -1, znamená to, že deque je prázdny.

Kontrola je plná

Táto operácia sa vykonáva na kontrolu, či je deque plná alebo nie. Ak predné = zadné + 1, alebo predné = 0 a zadné = n - 1, znamená to, že deque je plná.

Časová zložitosť všetkých vyššie uvedených operácií deque je O(1), teda konštantná.

Aplikácie deque

  • Deque môže byť použitý ako zásobník aj ako front, pretože podporuje obe operácie.
  • Deque sa dá použiť ako kontrola palindrómu znamená, že ak čítame reťazec z oboch koncov, reťazec by bol rovnaký.

Implementácia deque

Teraz sa pozrime na implementáciu deque v programovacom jazyku C.

git status -s 
 #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; }

Výkon:

Deque (alebo dvojitý rad)

Tak, to je o článku všetko. Dúfam, že článok bude pre vás užitočný a poučný.