logo

TechCodeview

Deque (arba dvipusė eilė)

Šiame straipsnyje aptarsime dvipusę eilę arba deque. Pirmiausia turėtume pamatyti trumpą eilės aprašymą.

Kas yra eilė?

Eilė yra duomenų struktūra, kurioje pirmiausia išeis viskas, kas atsiranda anksčiau, ir ji atitinka FIFO (pirmas į pirmus išeinančius) politiką. Įterpimas į eilę atliekamas iš vieno galo, žinomo kaip galas arba uodega, kadangi ištrynimas atliekamas iš kito galo, žinomo kaip priekinis galas arba galva iš eilės.

latekso stalas

Realus eilės pavyzdys yra bilietų eilė už kino salės, kai asmuo, kuris patenka pirmas į eilę, gauna bilietą pirmas, o asmuo, įeinantis paskutinis, gauna bilietą pagaliau.

Kas yra deque (arba dvipusė eilė)

Deque reiškia Double Ended Queue. Deque yra linijinė duomenų struktūra, kurioje įterpimo ir ištrynimo operacijos atliekamos iš abiejų galų. Galima sakyti, kad deque yra apibendrinta eilės versija.

Nors įterpimas ir ištrynimas deque gali būti atliekamas abiejuose galuose, tai neatitinka FIFO taisyklės. Deque vaizdavimas pateikiamas taip -

Deque (arba dvipusė eilė)

Deque rūšys

Yra du deque tipai -

  • Įvesties apribota eilė
  • Išvesties apribota eilė

Įvestis apribota eilė

Apribotoje įvesties eilėje įterpimo operacija gali būti atliekama tik viename gale, o ištrynimas gali būti atliekamas iš abiejų galų.

Deque (arba dvipusė eilė)

Išvestis apribota eilė

Apribotoje išvesties eilėje ištrynimo operacija gali būti atliekama tik viename gale, o įterpimas gali būti atliekamas iš abiejų galų.

Deque (arba dvipusė eilė)

Deque atliekamos operacijos

Yra šios operacijos, kurias galima pritaikyti deque -

  • Įdėjimas priekyje
  • Įdėjimas gale
  • Ištrynimas priekyje
  • Ištrynimas gale

Taip pat galime atlikti žvilgtelėjimo operacijas deque kartu su aukščiau išvardytomis operacijomis. Per peek operaciją galime gauti priekinius ir užpakalinius deque elementus. Taigi, be pirmiau minėtų operacijų, deque taip pat palaikomos šios operacijos -

javascript komentaras
  • Gaukite priekinį elementą iš deko
  • Gaukite galinį elementą iš deko
  • Patikrinkite, ar deka pilna, ar ne
  • Patikrina, ar deka tuščia, ar ne

Dabar supraskime deque operaciją naudodami pavyzdį.

Įterpimas priekinėje pusėje

Atliekant šią operaciją, elementas įterpiamas iš priekinės eilės galo. Prieš vykdydami operaciją, pirmiausia turime patikrinti, ar eilė pilna, ar ne. Jei eilė nepilna, elementą galima įterpti iš priekinės dalies, naudojant toliau nurodytas sąlygas -

  • Jei eilė tuščia, tiek gale, tiek priekyje inicijuojami 0. Dabar abu bus nukreipti į pirmąjį elementą.
  • Kitu atveju patikrinkite priekinės dalies padėtį, jei priekinė dalis yra mažesnė nei 1 (priekis<1), then reinitialize it by front = n - 1 , t.y., paskutinis masyvo indeksas.
Deque (arba dvipusė eilė)

Įdėjimas galinėje dalyje

Atliekant šią operaciją, elementas įterpiamas iš eilės galo. Prieš vykdydami operaciją, pirmiausia turime dar kartą patikrinti, ar eilė pilna, ar ne. Jei eilė nepilna, elementą galima įterpti iš galinės dalies, laikantis toliau nurodytų sąlygų -

  • Jei eilė tuščia, tiek gale, tiek priekyje inicijuojami 0. Dabar abu bus nukreipti į pirmąjį elementą.
  • Kitu atveju padidinkite galinę dalį 1. Jei užpakalinės dalies indeksas yra paskutinis (arba dydis - 1), tada užuot padidinę jį 1, turime padaryti jį lygų 0.
Deque (arba dvipusė eilė)

Ištrynimas priekinėje dalyje

kiek sveria kat timpf

Atliekant šią operaciją elementas ištrinamas iš priekinės eilės galo. Prieš vykdydami operaciją, pirmiausia turime patikrinti, ar eilė tuščia, ar ne.

Jei eilė tuščia, t. y. priekis = -1, tai yra perpildymo sąlyga ir negalime ištrinti. Jei eilė nepilna, elementą galima įterpti iš priekinės dalies, naudojant toliau nurodytas sąlygas -

Jei deque yra tik vienas elementas, nustatykite užpakalinę = -1 ir priekinę = -1.

Kitu atveju, jei priekis yra gale (tai reiškia, kad priekis = dydis - 1), nustatykite priekį = 0.

java konstantos

Kitu atveju padidinkite priekį 1 (ty priekis = priekis + 1).

Deque (arba dvipusė eilė)

Ištrynimas gale

Atliekant šią operaciją elementas ištrinamas iš eilės galo. Prieš vykdydami operaciją, pirmiausia turime patikrinti, ar eilė tuščia, ar ne.

Jei eilė tuščia, t. y. priekis = -1, tai yra perpildymo sąlyga ir negalime ištrinti.

Jei deque yra tik vienas elementas, nustatykite užpakalinę = -1 ir priekinę = -1.

Jei galas = 0 (galas yra priekyje), tada nustatykite galą = n - 1.

Kitu atveju sumažinkite galinę dalį 1 (arba galinis = galinis -1).

Deque (arba dvipusė eilė)

Patikrinkite tuščią

Ši operacija atliekama norint patikrinti, ar deka tuščia, ar ne. Jei front = -1, tai reiškia, kad deque tuščia.

Patikrinkite pilnas

Ši operacija atliekama norint patikrinti, ar deka pilna, ar ne. Jei priekis = galinis + 1 arba priekis = 0, o galas = n - 1, tai reiškia, kad deka pilna.

Visų aukščiau išvardintų deque operacijų laiko sudėtingumas yra O(1), ty pastovus.

Deque taikymai

  • Deque gali būti naudojamas ir kaip dėklas, ir kaip eilė, nes palaiko abi operacijas.
  • Deque gali būti naudojamas kaip palindromo tikrintuvas reiškia, kad jei eilutę skaitytume iš abiejų galų, eilutė būtų ta pati.

Deque įgyvendinimas

Dabar pažiūrėkime, kaip deque yra įdiegta C programavimo kalba.

atgalinio skambučio pragaras javascript 
 #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; }

Išvestis:

Deque (arba dvipusė eilė)

Taigi, viskas apie straipsnį. Tikimės, kad straipsnis bus jums naudingas ir informatyvus.