Tässä artikkelissa keskustelemme kaksipäisestä jonosta tai dequesta. Meidän pitäisi ensin nähdä lyhyt kuvaus jonosta.
Mikä on jono?
Jono on tietorakenne, jossa se, mikä tulee ensin, poistuu ensin, ja se noudattaa FIFO-käytäntöä (First-In-First-Out). Jonon lisääminen tehdään yhdestä päästä, joka tunnetaan nimellä takapää tai häntä, kun taas poisto tehdään toisesta päästä, joka tunnetaan nimellä etupää tai pää jonosta.
aseta java
Tosimaailman esimerkki jonosta on elokuvateatterin ulkopuolella oleva lippujono, jossa ensimmäisenä jonoon saapuva saa lipun ensimmäisenä ja jonoon viimeisenä saapuva saa lipun viimein.
Mikä on deque (tai kaksipäinen jono)
Deque tulee sanoista Double Ended Queue. Deque on lineaarinen tietorakenne, jossa lisäys- ja poistotoiminnot suoritetaan molemmista päistä. Voimme sanoa, että deque on yleinen versio jonosta.
Vaikka lisäys ja poistaminen dequessa voidaan suorittaa molemmissa päissä, se ei noudata FIFO-sääntöä. Dequen esitys esitetään seuraavasti -
Dequen tyypit
Deque-tyyppejä on kahdenlaisia -
- Syötä rajoitettu jono
- Lähtö rajoitettu jono
Syöttörajoitettu jono
Syöttörajoitetussa jonossa lisäystoiminto voidaan suorittaa vain toisessa päässä, kun taas poisto voidaan suorittaa molemmista päistä.
Lähtö rajoitettu jono
Lähtörajoitetussa jonossa poistotoiminto voidaan suorittaa vain toisessa päässä, kun taas lisäys voidaan suorittaa molemmista päistä.
Leikkaukset suoritettu dequella
On olemassa seuraavat toiminnot, joita voidaan käyttää dequessa -
- Sisäänpano edessä
- Sisäänpano takana
- Poisto edessä
- Poisto takana
Voimme myös suorittaa kurkistusoperaatioita dequessa yllä lueteltujen toimintojen ohella. Peek-operaation kautta saamme dequen etu- ja takaelementit esille. Joten yllä olevien toimintojen lisäksi seuraavat toiminnot ovat tuettuja deque-tilassa -
bharti jha
- Hanki etuosa dequesta
- Hanki takaosa dequesta
- Tarkista, onko deque täynnä vai ei
- Tarkistaa, onko deque tyhjä vai ei
Ymmärretään nyt esimerkin avulla dequelle suoritettu toimenpide.
Sisäänpano etupäässä
Tässä toiminnossa elementti lisätään jonon etupäästä. Ennen toiminnon toteuttamista meidän on ensin tarkistettava, onko jono täynnä vai ei. Jos jono ei ole täynnä, elementti voidaan lisätä etupäästä seuraavilla ehdoilla -
- Jos jono on tyhjä, sekä taka- että etuosa alustetaan 0:lla. Nyt molemmat osoittavat ensimmäiseen elementtiin.
- Muussa tapauksessa tarkista etuosan asento, jos etuosan asento on pienempi kuin 1 (etu<1), then reinitialize it by front = n - 1, eli taulukon viimeinen indeksi.
Sisäänpano takapäässä
ota java käyttöön
Tässä toiminnossa elementti lisätään jonon takapäästä. Ennen toiminnon toteuttamista meidän on ensin tarkistettava uudelleen, onko jono täynnä vai ei. Jos jono ei ole täynnä, elementti voidaan lisätä takapäästä seuraavilla ehdoilla -
- Jos jono on tyhjä, sekä taka- että etuosa alustetaan 0:lla. Nyt molemmat osoittavat ensimmäiseen elementtiin.
- Muussa tapauksessa lisää takaosaa yhdellä. Jos takaosan arvo on viimeinen (tai koko - 1), sen sijaan, että lisäisimme sitä yhdellä, meidän on tehtävä se yhtä suureksi kuin 0.
Poisto etupäässä
Tässä toiminnossa elementti poistetaan jonon etupäästä. Ennen toiminnon toteuttamista meidän on ensin tarkistettava, onko jono tyhjä vai ei.
Jos jono on tyhjä, eli front = -1, se on alivuoto, emmekä voi suorittaa poistoa. Jos jono ei ole täynnä, elementti voidaan lisätä etupäästä seuraavilla ehdoilla -
Jos dequessa on vain yksi elementti, aseta taka = -1 ja etu = -1.
Muussa tapauksessa, jos etuosa on lopussa (eli etuosa = koko - 1), aseta etuosa = 0.
25/100
Muuten lisää etuosaa 1:llä (eli etu = etu + 1).
Poisto takapäässä
Tässä toiminnossa elementti poistetaan jonon takapäästä. Ennen toiminnon toteuttamista meidän on ensin tarkistettava, onko jono tyhjä vai ei.
Jos jono on tyhjä, eli front = -1, se on alivuoto, emmekä voi suorittaa poistoa.
Jos dequessa on vain yksi elementti, aseta taka = -1 ja etu = -1.
Jos taka = 0 (taka on edessä), aseta taka = n - 1.
Muussa tapauksessa vähennä takaosaa yhdellä (tai, taka = taka -1).
Tarkista tyhjä
Tämä toimenpide suoritetaan sen tarkistamiseksi, onko deque tyhjä vai ei. Jos front = -1, se tarkoittaa, että deque on tyhjä.
Tarkista täynnä
Tämä toimenpide suoritetaan sen tarkistamiseksi, onko deque täynnä vai ei. Jos edessä = takana + 1 tai edessä = 0 ja takana = n - 1, se tarkoittaa, että deque on täynnä.
Kaikkien yllä olevien deque-toimintojen aikamonimutkaisuus on O(1), eli vakio.
Dequen sovellukset
- Dequea voidaan käyttää sekä pinona että jonona, koska se tukee molempia toimintoja.
- Dequeä voidaan käyttää palindromitarkistimena, mikä tarkoittaa, että jos luemme merkkijonon molemmista päistä, merkkijono olisi sama.
Dequen toteutus
Katsotaanpa nyt dequen toteutusta C-ohjelmointikielellä.
fizzbuzz java
#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; } Lähtö:
Eli siinä kaikki artikkelista. Toivottavasti artikkeli on hyödyllinen ja informatiivinen sinulle.