logo

TechCodeview

Deque (nebo dvojitá fronta)

V tomto článku budeme diskutovat o dvojité frontě nebo deque. Nejprve bychom měli vidět stručný popis fronty.

Co je to fronta?

Fronta je datová struktura, ve které to, co přijde dřív, vyjde jako první, a řídí se zásadou FIFO (First-In-First-Out). Vkládání do fronty se provádí z jednoho konce známého jako zadní konec nebo ocas, zatímco mazání se provádí z jiného konce známého jako přední konec nebo hlava z fronty.

odstranění posledního commitu git

Příkladem fronty v reálném světě je fronta na lístky mimo kinosál, kde ten, kdo ve frontě vstoupí jako první, dostane lístek jako první a ten, kdo ve frontě vstoupí jako poslední, lístek nakonec dostane.

Co je to Deque (neboli dvojitá fronta)

Deque znamená Double Ended Queue. Deque je lineární datová struktura, kde se operace vkládání a mazání provádějí z obou konců. Můžeme říci, že deque je zobecněná verze fronty.

Ačkoli vkládání a mazání v deque může být provedeno na obou koncích, neřídí se pravidlem FIFO. Zastoupení deque je uvedeno následovně -

Deque (nebo dvojitá fronta)

Typy deque

Existují dva typy deque -

  • Fronta s omezeným vstupem
  • Výstupní omezená fronta

Fronta s omezeným vstupem

Ve frontě s omezeným vstupem lze operaci vložení provést pouze na jednom konci, zatímco odstranění lze provést z obou konců.

Deque (nebo dvojitá fronta)

Fronta s omezeným výstupem

Ve frontě s omezeným výstupem lze operaci odstranění provést pouze na jednom konci, zatímco vložení lze provést z obou konců.

Deque (nebo dvojitá fronta)

Operace prováděné na deque

Existují následující operace, které lze použít na deque -

  • Vložení vepředu
  • Vložení vzadu
  • Výmaz vepředu
  • Výmaz vzadu

Můžeme také provádět operace náhledu v deque spolu s operacemi uvedenými výše. Prostřednictvím operace peeku můžeme získat přední a zadní prvky deque. Takže kromě výše uvedených operací jsou v deque podporovány také následující operace -

co je rozhraní
  • Získejte přední položku od deque
  • Získejte zadní položku od deque
  • Zkontrolujte, zda je deque plná nebo ne
  • Zkontroluje, zda je deque prázdný nebo ne

Nyní pochopme operaci prováděnou na deque pomocí příkladu.

Vložení na předním konci

Při této operaci je prvek vložen z předního konce fronty. Před implementací operace musíme nejprve zkontrolovat, zda je fronta plná nebo ne. Pokud fronta není plná, lze prvek vložit z frontendu pomocí níže uvedených podmínek -

  • Pokud je fronta prázdná, zadní i přední jsou inicializovány na 0. Nyní budou obě ukazovat na první prvek.
  • V opačném případě zkontrolujte polohu přední části, pokud je přední část menší než 1 (přední<1), then reinitialize it by front = n - 1, tj. poslední index pole.
Deque (nebo dvojitá fronta)

Vložení na zadním konci

Při této operaci je prvek vložen ze zadního konce fronty. Před realizací operace musíme nejprve znovu zkontrolovat, zda je fronta plná nebo ne. Pokud není fronta plná, lze prvek vložit ze zadního konce za použití níže uvedených podmínek -

  • Pokud je fronta prázdná, zadní i přední jsou inicializovány na 0. Nyní budou obě ukazovat na první prvek.
  • V opačném případě zvyšte zadní část o 1. Pokud má zadní část poslední index (nebo velikost - 1), místo jejího zvýšení o 1 jej musíme nastavit na 0.
Deque (nebo dvojitá fronta)

Smazání na předním konci

Při této operaci je prvek odstraněn z přední části fronty. Před implementací operace musíme nejprve zkontrolovat, zda je fronta prázdná nebo ne.

algoritmus rychlého třídění

Pokud je fronta prázdná, tj. front = -1, jedná se o podmínku podtečení a nemůžeme provést odstranění. Pokud fronta není plná, lze prvek vložit z frontendu pomocí níže uvedených podmínek -

Pokud má deque pouze jeden prvek, nastavte zadní = -1 a přední = -1.

Jinak, pokud je přední strana na konci (to znamená přední strana = velikost - 1), nastavte přední stranu = 0.

délka pole v jazyce Java

Jinak zvyšte přední stranu o 1 (tj. přední = přední + 1).

Deque (nebo dvojitá fronta)

Smazání na zadním konci

Při této operaci je prvek odstraněn ze zadní části fronty. Před implementací operace musíme nejprve zkontrolovat, zda je fronta prázdná nebo ne.

Pokud je fronta prázdná, tj. front = -1, jedná se o podmínku podtečení a nemůžeme provést odstranění.

Pokud má deque pouze jeden prvek, nastavte zadní = -1 a přední = -1.

Pokud zadní = 0 (zadní je vpředu), nastavte zadní = n - 1.

Jinak snižte zadní část o 1 (nebo, zadní = zadní -1).

Deque (nebo dvojitá fronta)

Zkontrolujte prázdnou

Tato operace se provádí ke kontrole, zda je deque prázdný nebo ne. Pokud front = -1, znamená to, že deque je prázdný.

Zkontrolujte plnou

Tato operace se provádí ke kontrole, zda je deque plná nebo ne. Je-li přední = zadní + 1, nebo přední = 0 a zadní = n - 1, znamená to, že deque je plná.

Časová složitost všech výše uvedených operací deque je O(1), tj. konstantní.

Aplikace deque

  • Deque lze použít jako zásobník i jako frontu, protože podporuje obě operace.
  • Deque lze použít jako kontrolu palindromu, což znamená, že pokud bychom řetězec četli z obou konců, byl by řetězec stejný.

Implementace deque

Nyní se podívejme na implementaci deque v programovacím jazyce C.

neměnný seznam 
 #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ýstup:

Deque (nebo dvojitá fronta)

Tak to je k článku vše. Doufám, že vám článek bude užitečný a poučný.