Š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 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ų.
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 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.
Į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.
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).
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).
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 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (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 && r==size-1) || (f==r+1)) { printf('Overflow'); } else if((f==-1) && (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('
Elements in a deque are: '); while(i!=r) { printf('%d ',deque[i]); i=(i+1)%size; } printf('%d',deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf('
The value of the element at front is: %d', deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else { printf('
The value of the element at rear is %d', deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf('
The deleted element is %d', deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf('
The deleted element is %d', deque[f]); f=0; } else { printf('
The deleted element is %d', deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) && (r==-1)) { printf('Deque is empty'); } else if(f==r) { printf('
The deleted element is %d', deque[r]); f=-1; r=-1; } else if(r==0) { printf('
The deleted element is %d', deque[r]); r=size-1; } else { printf('
The deleted element is %d', 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:
Taigi, viskas apie straipsnį. Tikimės, kad straipsnis bus jums naudingas ir informatyvus.