Erinevus virna ja järjekorra vahel

Autor: Laura McKinney
Loomise Kuupäev: 2 Aprill 2021
Värskenduse Kuupäev: 15 Mai 2024
Anonim
Erinevus virna ja järjekorra vahel - Tehnoloogia
Erinevus virna ja järjekorra vahel - Tehnoloogia

Sisu


Stack ja Queue on mõlemad mitte-primitiivsed andmestruktuurid. Peamised erinevused pinu ja järjekorra vahel on selles, et pinu kasutab andmeelementide juurde pääsemiseks ja nende lisamiseks meetodit LIFO (viimane esimesena välja), samas kui järjekord kasutab andmeelementide juurde pääsemiseks ja lisamiseks FIFO (esimene sisse esimene välja) meetodit.

Stackil on andmeelementide tõukamiseks ja hüpitamiseks avatud ainult üks ots. Järjekorras on mõlemad elemendid andmeelementide sisselülitamiseks ja detekteerimiseks avatud.

Pinu ja järjekord on andmestruktuurid, mida kasutatakse andmeelementide salvestamiseks, ja need põhinevad tegelikult mõnel reaalse maailma ekvivalendil. Näiteks on virn CD-virna, kust saate CD-virna ülaosa kaudu välja võtta ja CD-le panna. Samamoodi on järjekord teatripiletite järjekord, kus teenindatakse kõigepealt seisvat, s.o järjekorra ees seisvat isikut ja saabuv uus inimene ilmub järjekorra tagumisse ossa (järjekorra tagumine ots).


  1. Võrdlusdiagramm
  2. Definitsioon
  3. Peamised erinevused
  4. Rakendamine
  5. Operatsioonid
  6. Rakendused
  7. Järeldus

Võrdlusdiagramm

Võrdluse alusKorstnat Järjekord
TööpõhimõteLIFO (viimane sisse esimene)FIFO (esimene välja esimene)
StruktuurElementide sisestamiseks ja kustutamiseks kasutatakse sama otsa.Ühte otsa kasutatakse sisestamiseks, st tagumist otsa ja teist otsa kasutatakse elementide, st esiosa, kustutamiseks.
Kasutatud näpunäidete arvÜksKaks (lihtsas järjekorras)
Teostatud toimingudPush ja pop Enqueque and dequeque
Tühja seisukorra kontrollimineÜlemine == -1Esiosa == -1 || Esiosa == Tagumine + 1
Tervisliku seisundi kontrollimine
Ülemine == maksimaalselt - 1Tagumine == maksimaalselt - 1
VariandidSellel pole variante.Sellel on variandid nagu ümmargune järjekord, prioriteedijärjekord, kahepoolse otsaga järjekord.
RakendamineLihtsamVõrdlemisi keeruline


Stacki määratlus

Stack on mitte-primitiivne lineaarne andmestruktuur. See on tellitud loend, kuhu lisatakse uus üksus ja olemasolev element kustutatakse ainult ühest otsast, mida nimetatakse virna ülaosaks (TOS). Kuna kogu kustutamine ja sisestamine virnas toimub virna ülaosast, eemaldatakse virnast esimene viimane lisatud element. See on põhjus, miks virna nimetatakse LIFO-tüüpi loendiks.

Pange tähele, et sageli korstnasse pääsev element on ülaosa, samas kui viimane saadaolev element on virna põhjas.

Näide

Mõni teist võib süüa küpsiseid (või poppinsi). Kui arvate, et ainult üks katte külg on rebenenud ja küpsised võetakse ükshaaval välja. Seda nimetatakse poputamiseks ja samamoodi, kui soovite küpsiseid mõnda aega hiljem säilitada, pange need sama rebenenud otsa kaudu tagasi pakendisse, mida nimetatakse tõukamiseks.

Järjekorra määratlus

Järjekord on lineaarne andmestruktuur, mis kuulub mitte-primitiivse tüübi kategooriasse. See on sama tüüpi elementide kogum. Uute elementide lisamine toimub ühest otsast, mida nimetatakse tagumiseks. Sarnaselt toimub olemasolevate elementide kustutamine teises otsas, mida nimetatakse esiotsaks, ja loogiliselt on tegemist FIFO-tüüpi loendi tüübiga kõigepealt.

Näide

Oma igapäevases elus puutume kokku paljude olukordadega, kus ootame soovitud teenust ootama, seal peame teeninduse saamiseks jõudma järjekorda oma järjekorda. Seda ootejärjekorda võib pidada järjekorda.

  1. Stack järgib LIFO mehhanismi, teiselt poolt. Järjekord järgib FIFO mehhanismi elementide lisamiseks ja eemaldamiseks.
  2. Virnas kasutatakse sama otsa elementide sisestamiseks ja kustutamiseks. Vastupidi, elementide sisestamiseks ja kustutamiseks kasutatakse järjekorras kahte erinevat otsa.
  3. Kuna virnal on ainult üks lahtine ots, on põhjus virna ülaosale viitamiseks ainult ühe osuti kasutamine. Järjekord kasutab aga kahte osuti järjekorra esi- ja tagumise otsa viitamiseks.
  4. Stack sooritab kaks toimingut, mida nimetatakse push ja pop-na, samal ajal kui järjekorras seda tuntud kui enqueque and dequeque.
  5. Korstna rakendamine on lihtsam, samas kui järjekorda rakendamine on keeruline.
  6. Järjekorras on sellised variandid nagu ümmargune järjekord, prioriteedijärjekord, kahepoolse otsaga järjekord jne. Seevastu virnal pole variante.

Korstnate rakendamine

Virna saab kasutada kahel viisil:

  1. Staatiline teostus kasutab virna loomiseks massiive. Staatiline juurutamine on küll vaevatu tehnika, kuid pole paindlik loomise viis, kuna virna suuruse deklareerimine tuleb teha programmi kavandamisel, pärast seda ei saa suurust muuta. Lisaks pole staatiline teostus mälu kasutamisel eriti tõhus. Kuna massiiv (virna rakendamiseks) deklareeritakse enne operatsiooni algust (programmi kavandamise ajal). Kui sorteeritavate elementide arv on virnas väga väike, läheb staatiliselt eraldatud mälu raisku. Teisest küljest, kui virnas on rohkem elemente, mida salvestada, siis ei saa me massiivi mahu suurendamiseks muuta, et see mahutaks uusi elemente.
  2. Dünaamiline rakendamine nimetatakse ka lingitud loendiesituseks ja kasutab viiteid andmestruktuuri korstnatüübi rakendamiseks.

Järjekorra rakendamine

Järjekorda saab rakendada kahel viisil:

  1. Staatiline teostus: Kui järjekorda rakendatakse massiivide abil, tuleb enne seda tagada täpne elementide arv, mida tahame järjekorda salvestada, sest massiivi suurus tuleb deklareerida kavandamise ajal või enne töötlemise algust. Sel juhul muutub massiivi algus järjekorra esiosaks ja massiivi viimane asukoht toimib järjekorra tagaosana. Järgmine seos annab kogu elementide olemasolu massiivi kasutades järjekorras:
    ees - taga + 1
    Kui “taga <ees”, siis järjekorras ühtegi elementi pole või järjekord on alati tühi.
  2. Dünaamiline rakendamine: Järjekordade rakendamine osutitega, peamine puudus on see, et lingitud esinduses olev sõlm tarbib rohkem mäluruumi kui massiivi esitusel olev vastav element. Kuna igas sõlmes on vähemalt kaks välja andmeväli ja teine ​​järgmise sõlme aadressi salvestamiseks, siis lingitud esinduses on ainult andmeväli. Lingitud esituse kasutamise eelis ilmneb siis, kui on vaja element lisada või kustutada muude elementide rühma keskele.

Operatsioonid virnadel

Peamised toimingud, mida saab virnaga kasutada, on järgmised:

  1. PUSH: kui virna ülaossa lisatakse uus element, nimetatakse seda PUSH-toiminguks. Elemendi virna lükamine kutsub esile elemendi lisamise, kuna uus element sisestatakse ülaossa. Pärast iga tõukeoperatsiooni suurendatakse ülaosa ühe võrra. Kui massiiv on täis ja uusi elemente ei saa lisada, nimetatakse seda STACK-FULL seisundiks või STACK OVERFLOW. LÜLITAMINE - funktsioon C-s:
    Stacki arvestamine kuulutatakse kui
    int stäkk, ülemine = -1;
    tühine tõuge ()
    {
    int üksus;
    if (ülemine <4)
    {
    f ("Sisestage number");
    skaneerimine ("% d", & üksus);
    ülemine = ülemine + 1;
    stäkk = ese;
    }
    muud
    {
    f ("Virn on täis");
    }
    }
  2. POP: Kui element virna ülaosast kustutatakse, nimetatakse seda POP-toiminguks. Pärast iga hüppelist toimingut vähendatakse virna ühe võrra. Kui virnast pole ühtegi elementi alles ja hüpik on tehtud, siis põhjustab see STACK UNDERFLOW tingimust, mis tähendab, et teie stäkk on tühi. POP-OPERATSIOON - funktsioonid C-s:
    Stacki arvestamine kuulutatakse kui
    int stäkk, ülemine = -1;
    tühine pop ()
    {
    int üksus;
    if (ülemine> = 4)
    {
    üksus = virn;
    ülalt = ülalt - 1;
    f ("Kustutatud arv on =% d", element);
    }
    muud
    {
    f ("Virn on tühi");
    }
    }

Operatsioonid järjekorras

Järjekorras tehtavad põhitoimingud on järgmised:

  1. Enqueque: Elemendi lisamiseks järjekorda. Toimimisfunktsiooni valimine C-s:
    Järjekord kuulutatakse kui
    sisejärjekord, ees = -1 ja taga = -1;
    tühine lisa ()
    {
    int üksus;
    kui (tagumine <4)
    {
    f ("Sisestage number");
    skaneerimine ("% d", & üksus);
    if (ees == -1)
    {
    ees = 0;
    taga = 0;
    }
    muud
    {
    taga = taga + 1;
    }
    järjekord = kirje;
    }
    muud
    {
    f ("Järjekord on täis");
    }
    }
  2. Dequeque: Elemendi kustutamine järjekorrast. Toimimisfunktsiooni valimine C-s:
    Järjekord kuulutatakse kui
    sisejärjekord, ees = -1 ja taga = -1;
    tühista kustutamine ()
    {
    int üksus;
    if (ees! = -1)
    {
    kirje = järjekord;
    if (ees == taga)
    {
    ees = -1;
    taga = -1;
    }
    muud
    {
    ees = ees + 1;
    f ("Kustutatud arv on =% d", element);
    }
    }
    muud
    {
    f ("Järjekord on tühi");
    }
    }

Stacki rakendused

  • Parsimine kompilaatoris.
  • Java virtuaalmasin.
  • Tühista tekstitöötlusprogrammis.
  • Nupp Tagasi veebibrauseris.
  • PostScripti keel ers.
  • Funktsiooni kõnede rakendamine kompilaatoris.

Järjekorra rakendused

  • Andmepuhvrid
  • Asünkroonne andmeedastus (faili IO, torud, pistikupesad).
  • Taotluste määramine ühisel ressursil (eriprotsessor).
  • Liikluse analüüs.
  • Määrake supermarketis olevate kassapidajate arv.

Järeldus

Stack ja Queue on lineaarsed andmestruktuurid, mis erinevad teatud viisil, näiteks töömehhanism, struktuur, teostus, variandid, kuid neid mõlemaid kasutatakse loendis olevate elementide hoidmiseks ja loendis toimingute tegemiseks, näiteks elementide lisamine ja kustutamine. Ehkki lihtsal järjekordal on mõned piirangud, mida taastub teist tüüpi järjekorda kasutades.