Sisältö

• Vertailutaulukko
• Määritelmä Pino
• esimerkki
• Määritelmä Jono
• esimerkki
• Pinojen toteutus
• Jonon toteutus
• Operaatiot pinolla
• Operaatiot jonossa
• Stackin sovellukset
• Jonon sovellukset
• johtopäätös

Pinot ja jonot ovat molemmat ei-primitiivisiä tietorakenteita. Tärkeimmät erot pinon ja jonon välillä ovat siinä, että pino käyttää LIFO-menetelmää (viimeinen ensimmäisessä ulos) dataelementtien käyttämiseen ja lisäämiseen, kun taas Jono käyttää FIFO-menetelmää (First in first out) tietojen käyttämiseen ja lisäämiseen.

Pinossa on vain yksi pää avoinna dataelementtien työntämiseen ja popputtamiseen. Jonossa on molemmat päät avoinna dataelementtien enkeroimiseksi ja purkamiseksi.

Pino ja jono ovat tietoelementtien tallentamiseen käytettäviä tietorakenteita, ja ne tosiasiallisesti perustuvat reaalimaailman vastaaviin. Pino on esimerkiksi pino CD-levyjä, joista voit ottaa pois ja asettaa CD-levyn CD-pino yläosan kautta. Samoin jono on teatterilippujen jono, jossa ensisijaisesti eli jonon edessä seisova henkilö palvelee ensin ja saapuva uusi henkilö ilmestyy jonon takaosaan (jonon takaosa).

1. Vertailutaulukko
2. Määritelmä
3. Keskeiset erot
4. Toteutus
5. toiminnot
6. Sovellukset
7. johtopäätös

Vertailutaulukko

Vertailun perusteet	Pino	Jonottaa
Toimintaperiaate	LIFO (viimeinen ensimmäisenä)	FIFO (ensimmäinen sisään ensin)
Rakenne	Samaa päätä käytetään elementtien lisäämiseen ja poistamiseen.	Toista päätä käytetään asetukseen, ts. Takapäätä ja toista päätä käytetään elementtien, ts. Etuosan, poistamiseen.
Käytettyjen osoittimien lukumäärä	Yksi	Kaksi (yksinkertaisessa jonossa)
Suoritetut toimenpiteet	Push ja pop	Enqueque ja dequeque
Tyhjän tilan tutkiminen	Ylä == -1	Edessä == -1 || Edessä == Taka + 1
Koko kunnon tarkastus	Ylä == enintään - 1	Takana == Max - 1
variantit	Sillä ei ole muunnoksia.	Sillä on muunnoksia, kuten pyöreä jono, prioriteettijono, kaksinkertaisesti päättynyt jono.
Toteutus	yksinkertaisempi	Suhteellisen monimutkainen

Määritelmä Pino

Pino on ei-primitiivinen lineaarinen tietorakenne. Se on tilattu luettelo, johon uusi kohde lisätään ja olemassa oleva elementti poistetaan vain yhdestä päästä, nimeltään pinon yläosa (TOS). Koska kaikki poisto ja lisäys pinoon tehdään pinon yläosasta, viimeinen lisätty elementti on ensimmäinen, joka poistetaan pinosta. Tästä syystä pinoa kutsutaan viimeksi-ensin-ulos (LIFO) -tyyppiseksi luetteloksi.

Huomaa, että pinoon usein käytetty elementti on ylin elementti, kun taas viimeisin käytettävissä oleva elementti on pinon alaosassa.

esimerkki

Jotkut teistä voivat syödä keksit (tai poppinsit). Jos oletat, vain kannen toinen puoli on revitty, ja keksit otetaan yksitellen ulos. Tätä kutsutaan poppingiksi, ja vastaavasti, jos haluat säilyttää joitain keksejä jonkin aikaa myöhemmin, laitat ne takaisin pakkaukseen saman revityn pään kautta, jota kutsutaan työntämiseksi.

Määritelmä Jono

Jono on lineaarinen tietorakenne, joka kuuluu ei-primitiivisen tyypin luokkaan. Se on kokoelma samanlaisia ​​elementtejä. Uusien elementtien lisääminen tapahtuu toisessa päässä, jota kutsutaan takaosaksi. Samoin olemassa olevien elementtien poistaminen tapahtuu etupäässä nimeltään toisesta päästä, ja se on loogisesti FIFO-tyyppinen luettelo.

esimerkki

Päivittäisessä elämässämme kohtaamme monia tilanteita, joissa odotamme toivottua palvelua, siellä meidän on päästävä odotuslinjaan vuoromme saadaksemme huoltoa. Tätä odotusjonoa voidaan ajatella jonona.

1. Pino seuraa LIFO-mekanismia. Jono seuraa FIFO-mekanismia elementtien lisäämiseksi ja poistamiseksi.
2. Pinossa samaa päätä käytetään elementtien lisäämiseen ja poistamiseen. Päinvastoin, jonossa käytetään kahta eri päätä elementtien lisäämiseksi ja poistamiseksi.
3. Koska Stackilla on vain yksi avoin pää, syynä on, että vain yhtä osoitinta käytetään viittaamaan pinon yläosaan. Mutta jono käyttää kahta osoitinta jonon etu- ja takaosan osoittamiseen.
4. Stack suorittaa kaksi operaatiota, joka tunnetaan nimellä push ja pop, kun taas Jonossa se tunnetaan nimellä enqueque and dequeque.
5. Pinojen toteutus on helpompaa, kun taas jonon toteutus on hankalaa.
6. Jonossa on muunnoksia, kuten pyöreä jono, prioriteettijono, kaksinkertaisesti päättynyt jono jne. Sen sijaan pinolla ei ole muunnoksia.

Pinojen toteutus

Pinoa voidaan käyttää kahdella tavalla:

1. Staattinen toteutus käyttää taulukkoja pinon luomiseen. Staattinen toteutus on tosin vaivatonta tekniikkaa, mutta ei ole joustava tapa luoda, koska pinon koko on ilmoitettava ohjelman suunnittelun aikana, sen jälkeen kokoa ei voida muuttaa. Lisäksi staattinen toteutus ei ole kovin tehokas muistin käytön suhteen. Koska taulukko (pinon toteuttamiseksi) julistetaan ennen toiminnan alkamista (ohjelman suunnittelun aikana). Nyt, jos lajiteltavien elementtien lukumäärä on pinossa hyvin vähemmän, staattisesti varattu muisti tuhlataan. Toisaalta, jos pinoon on tallennettava enemmän lukumääriä elementtejä, emme voi pysty muuttamaan taulukon kokoa lisätäkseen sen kapasiteettia, niin että siihen mahtuu uusia elementtejä.
2. Dynaaminen toteutus kutsutaan myös linkitetyn luettelon esitykseksi ja käyttää osoittimia pino-tyyppisen tietorakenteen toteuttamiseen.

Jonon toteutus

Jono voidaan toteuttaa kahdella tavalla:

1. Staattinen toteutus: Jos jono toteutetaan taulukkojen avulla, tarkka lukumäärä elementtejä, jotka haluamme tallentaa jonoon, on varmistettava ennen, koska taulukon koko on ilmoitettava suunnitteluaikana tai ennen käsittelyn aloittamista. Tässä tapauksessa taulukon alusta tulee jonon etuosa, ja taulukon viimeinen sijainti toimii jonon takana. Seuraava relaatio antaa kokonaiset elementit jonossa olemassa, kun ne toteutetaan taulukkojen avulla:
   edessä - takana + 1
   Jos “takana <edessä”, jonossa ei ole mitään elementtiä tai jono on aina tyhjä.
2. Dynaaminen toteutus: Toteutetaan jonoja osoittimien avulla, suurin haittapuoli on, että linkitetyn esityksen solmu kuluttaa enemmän muistitilaa kuin vastaava elementti taulukon esityksessä. Koska jokaisessa solmussa on ainakin kaksi kenttää yksi tietokenttää varten ja toinen seuraavan solmun osoitteen tallentamiseksi, kun taas linkitetyssä esityksessä on vain tietokenttä. Linkitetyn esityksen käytön ansio tulee ilmeiseksi, kun joudutaan lisäämään tai poistamaan elementti muiden elementtien ryhmän keskelle.

Operaatiot pinolla

Pinoon suoritettavat perustoiminnot ovat seuraavat:

1. TYÖNTÄÄ: Kun uusi elementti lisätään pinon yläosaan, kutsutaan PUSH-operaatioksi. Elementin työntäminen pinossa merkitsee elementin lisäämistä, koska uusi elementti asetetaan yläosaan. Jokaisen työntämisen jälkeen yläosaa kasvatetaan yhdellä. Jos taulukko on täynnä eikä uusia elementtejä voida lisätä, sitä kutsutaan PYSYYS-TÄYTYY-tilaksi tai PAKASTUS YLIVUORAKSI. PUSH-KÄYTTÖ - toiminto C: ssä:
   Pino huomioon ottaminen julistetaan
   int pino, ylä = -1;
tyhjä työntö ()
{
int tuote;
if (ylhäällä <4)
{
f ("Syötä numero");
skannaus ("% d", & esine);
top = top + 1;
pino = esine;
}
muu
{
f ("Pino on täynnä");
}
}
2. POP: Kun elementti poistetaan pinon yläosasta, se tunnetaan nimellä POP-toiminta. Pino pienenee yhdellä jokaisen pop-toiminnon jälkeen. Jos pinosta ei ole jäljellä mitään elementtiä ja pop suoritetaan, tämä johtaa STACK UNDERFLOW -tilaan, mikä tarkoittaa, että pinosi on tyhjä. POP-TOIMINTA - toiminnot C: ssä:
   Pino huomioon ottaminen julistetaan
   int pino, ylä = -1;
tyhjä pop ()
{
int tuote;
if (ylhäällä = = 4)
{
esine = pino;
top = top - 1;
f ("Poistettu numero on =% d", kohta);
}
muu
{
f ("Pino on tyhjä");
}
}

Operaatiot jonossa

Perusoperaatiot, jotka voidaan suorittaa jonossa, ovat:

1. enqueue: Elementin lisääminen jonoon. Käyttötoiminnon suorittaminen C: ssä:
   Jono julistetaan
   int jonossa, edessä = -1 ja takana = -1;
tyhjä lisäys ()
{
int tuote;
if (takana <4)
{
f ("Syötä numero");
skannaus ("% d", & esine);
if (edessä == -1)
{
edessä = 0;
takana = 0;
}
muu
{
takana = takana + 1;
}
jono = esine;
}
muu
{
f ("Jono on täynnä");
}
}

2. Dequeue: Elementin poistaminen jonosta. Käyttötoiminnon suorittaminen C: ssä:
   Jono julistetaan
   int jonossa, edessä = -1 ja takana = -1;
tyhjä poista ()
{
int tuote;
if (edessä! = -1)
{
esine = jono;
if (edessä == takana)
{
edessä = -1;
takana = -1;
}
muu
{
edessä = edessä + 1;
f ("Poistettu numero on =% d", kohta);
}
}
muu
{
f ("Jono on tyhjä");
}
}

Stackin sovellukset

• Jäsentäminen kääntäjässä.
• Java-virtuaalikone.
• Kumoa tekstinkäsittelyohjelmassa.
• Takaisin-painike verkkoselaimessa.
• PostScript-kieli.
• Toimintokutsujen toteuttaminen kääntäjässä.

Jonon sovellukset

• Tietopuskurit
• Asynkroninen tiedonsiirto (tiedosto IO, putket, pistorasiat).
• Pyyntöjen jakaminen jaetulle resurssille (prosessori).
• Liikenneanalyysi.
• Määritä supermarketeissa olevien kassajoukkojen lukumäärä.

johtopäätös

Pino ja Jono ovat lineaarisia tietorakenteita, jotka eroavat tietyillä tavoilla, kuten toimintamekanismi, rakenne, toteutus, variantit, mutta molempia käytetään luettelon elementtien tallentamiseen ja luettelon toimintojen suorittamiseen, kuten elementtien lisääminen ja poistaminen. Vaikka yksinkertaisella jonolla on joitain rajoituksia, jotka otetaan käyttöön käyttämällä muun tyyppisiä jonoja.