Razlika med skladom in čakalno vrsto

Avtor: Laura McKinney
Datum Ustvarjanja: 2 April 2021
Datum Posodobitve: 12 Maj 2024
Anonim
Razlika med skladom in čakalno vrsto - Tehnologija
Razlika med skladom in čakalno vrsto - Tehnologija

Vsebina


Stack in čakalna vrsta sta neprimitivni strukturi podatkov. Glavne razlike med skladom in čakalno vrsto so, da sklad uporablja LIFO (zadnji v prvem izhodu) metodo za dostop in dodajanje podatkovnih elementov, medtem ko Queue uporablja FIFO (First in first out) za dostop in dodajanje podatkovnih elementov.

Stock ima samo en konec odprt za potiskanje in prekašanje podatkovnih elementov na drugi strani. Čakalna vrsta ima oba konca odprta za pridobivanje in odstranitev podatkovnih elementov.

Sklad in vrsta so podatkovne strukture, ki se uporabljajo za shranjevanje podatkovnih elementov in dejansko temeljijo na nekem ekvivalentu v resničnem svetu. Na primer, sveženj je kup CD-jev, iz katerega lahko vzamete in vstavite CD na vrh kopice CD-jev. Podobno je čakalna vrsta za vstopnice za gledališče, kjer bo oseba, ki stoji na prvem mestu, to je spredaj, čakalna vrsta čakanja, nova oseba, ki prihaja, pa se bo pojavila na zadnjem delu čakalne vrste (zadnji konec čakalne vrste).


  1. Primerjalna tabela
  2. Opredelitev
  3. Ključne razlike
  4. Izvajanje
  5. Operacije
  6. Prijave
  7. Zaključek

Primerjalna tabela

Osnove za primerjavoZložite Čakalna vrsta
Načelo delaLIFO (zadnji v prvem izhodu)FIFO (prvi v prvem izhodu)
StrukturaIsti konec se uporablja za vstavljanje in brisanje elementov.En konec se uporablja za vstavljanje, to je zadnji konec, drugi konec pa za brisanje elementov, to je sprednji del.
Število uporabljenih kazalcevEnoDva (v enostavnem primeru iz čakalne vrste)
Opravljene operacijePush in Pop Enqueue in dequeue
Pregled praznega stanjaNa vrh == -1Spredaj == -1 || Spredaj == Zadaj + 1
Pregled popolne kondicije
Na vrh == Največ - 1Zadaj == Max - 1
VarianteNima variante.Ima različice, kot so krožna čakalna vrsta, prednostna vrsta, čakalno čakalno vrsto.
IzvajanjePreprostejšePrimerjalno zapleteno


Opredelitev Stack

Stack je neprimitivna linearna struktura podatkov. To je urejen seznam, kjer se doda nov element in obstoječi element se izbriše samo z enega konca, ki se imenuje kot zgornji del sklada (TOS). Ker se vse brisanje in vstavljanje v paketu izvede z vrha sklada, bo zadnji dodani element prvi odstranjen iz sklada. To je razlog, zakaj se sklad imenuje vrsta Last-in-First-out (LIFO).

Upoštevajte, da je element, do katerega pogosto dostopate v skladovnici, najbolj zgornji element, medtem ko je zadnji razpoložljivi element na dnu skladovnice.

Primer

Nekateri boste morda jedli piškote (ali Poppins). Če domnevate, je samo ena stran pokrova, piškoti pa jih vzamemo enega za drugim. Temu pravimo popping, in podobno, če želite nekaj piškotov ohraniti nekaj časa kasneje, jih boste skozi isti raztrgan konec dali nazaj v zavoj, se imenuje potiskanje.

Opredelitev čakalne vrste

Čakalna vrsta je linearna struktura podatkov, ki spada v kategorijo neprimitivnega tipa. Gre za zbirko elementov podobne vrste. Dodajanje novih elementov poteka na enem koncu, imenovanem zadnji konec. Podobno se brisanje obstoječih elementov zgodi na drugem koncu, imenovanem Front-end, in logično je vrsta seznama First in first out (FIFO).

Primer

V našem vsakodnevnem življenju naletimo na številne situacije, ko čakamo na želeno storitev, tam pa se moramo spraviti v čakalno vrsto, da bomo dobili svoj servis. To čakalno čakalno vrsto lahko predstavljamo kot čakalno vrsto.

  1. Stack sledi mehanizmu LIFO, na drugi strani čakalna vrsta sledi mehanizmu FIFO za dodajanje in odstranjevanje elementov.
  2. V skladovnici se isti konec uporablja za vstavljanje in brisanje elementov. V čakalni vrsti za vstavljanje in brisanje elementov se v čakalni vrsti uporabljata dva različna konca.
  3. Ker imajo Stack samo en odprt konec, je razlog za uporabo le enega kazalca za sklicevanje na vrh skladovnice. Toda čakalna vrsta uporablja dva kazalca za napotitev sprednjega in zadnjega konca čakalne vrste.
  4. Stack izvaja dve operaciji, znani kot push in pop, medtem ko je v čakalni vrsti znan kot enqueue in dequeue.
  5. Implementacija zlaganja je lažja, medtem ko je izvajanje čakalne vrste težavno.
  6. Čakalna vrsta ima različice, kot so krožna čakalna vrsta, prednostna vrsta, dvojno končana vrsta itd. V nasprotju s tem pa skladanje nima različic.

Izvedba skladov

Nabor je mogoče uporabiti na dva načina:

  1. Statična izvedba uporablja matrike za ustvarjanje sklada. Statična izvedba je sicer preprosta tehnika, vendar ni prilagodljiv način ustvarjanja, saj je treba deklariranje velikosti sklada opraviti med načrtovanjem programa, potem pa velikosti ni mogoče spreminjati. Poleg tega statična izvedba pri uporabi pomnilnika ni zelo učinkovita. Ker je matrika (za izvajanje sklada) razglašena pred začetkom operacije (v času načrtovanja programa). Če je število elementov, ki jih je treba razvrstiti, v skladovnici zelo manj, bo zapravljen statično dodeljen pomnilnik. Po drugi strani pa, če je v skladbi shranjenih več število elementov, ne moremo spremeniti velikosti matrike, da bi povečali njeno zmogljivost, tako da lahko sprejme nove elemente.
  2. Dinamična izvedba se imenuje tudi povezano predstavljanje seznama in uporablja kazalce za izvajanje vrste podatkovne strukture podatkov.

Izvajanje čakalne vrste

Čakalno vrsto lahko izvajate na dva načina:

  1. Statična izvedba: Če je vrsta izpeljana s pomočjo nizov, je treba predhodno zagotoviti točno število elementov, ki jih želimo shraniti v čakalno vrsto, saj je treba velikost matrike objaviti v času načrtovanja ali pred začetkom obdelave. V tem primeru bo začetek matrike postal sprednji del čakalne vrste, zadnja lokacija matrike pa bo delovala kot zadnja vrsta čakalne vrste. Naslednji odnos podaja, da v čakalni vrsti obstajajo celotni elementi, ko se izvajajo s pomočjo nizov:
    spredaj - zadaj + 1
    Če je "zadaj <spredaj", potem v čakalni vrsti ne bo nobenega elementa ali bo vrsta vedno prazna.
  2. Dinamična izvedba: Pri izvajanju čakalnih vrst s kazalci je glavna pomanjkljivost ta, da vozlišče v povezani predstavitvi porabi več pomnilniškega prostora kot ustrezen element v predstavitvi matrike. Ker sta v vsakem vozlišču vsaj dve polji, eno za podatkovno polje in drugo za shranjevanje naslova naslednjega vozlišča, medtem ko je v povezani predstavitvi samo podatkovno polje. Zasluga za uporabo povezane predstavitve postane očitna, ko je treba vstaviti ali izbrisati element sredi skupine drugih elementov.

Operacije na Stacku

Osnovne operacije, ki jih je mogoče izvajati na kupu, so naslednje:

  1. PUSH: ko je nov element dodan na vrh zložbe, je znano kot operacija PUSH. Potiskanje elementa v sveženj zahteva dodajanje elementa, saj bo nov element vstavljen na vrhu. Po vsakem pritisku se vrh poveča za eno. Če je matrika polna in ni mogoče dodati nobenega novega elementa, se imenuje STACK-FULL condition ali STACK OVERFLOW. DELOVANJE PUSH - funkcija v C:
    Ob upoštevanju stack je razglašen kot
    int stack, top = -1;
    nični pritisk ()
    {
    element int;
    če (vrh <4)
    {
    f ("Vnesite številko");
    skeniranje ("% d", & element);
    top = vrh + 1;
    sklad = element;
    }
    drugače
    {
    f ("sklad je poln");
    }
    }
  2. POP: Ko je element izbrisan z vrha sklada, je to znano kot operacija POP. Kop se po vsaki pop operaciji zmanjša za eno. Če na nizu ni nobenega elementa in se izvede pop, potem bo to stanje STACK UNDERFLOW, kar pomeni, da je vaš sklad prazen. DELOVANJE POP - funkcije v C:
    Ob upoštevanju stack je razglašen kot
    int stack, top = -1;
    void pop ()
    {
    element int;
    če (vrh> = 4)
    {
    element = sklad;
    vrh = vrh - 1;
    f ("Število izbrisanih je =% d", točka);
    }
    drugače
    {
    f ("sklad je prazen");
    }
    }

Operacije na čakalni vrsti

Osnovne operacije, ki jih lahko izvedemo na čakalni vrsti so:

  1. Enqueue: Vstaviti element v čakalno vrsto. Funkcija delovanja v C:
    Čakalna vrsta je razglašena za
    int čakalna vrsta, spredaj = -1 in zadaj = -1;
    neveljaven dodaj ()
    {
    element int;
    če (zadaj <4)
    {
    f ("Vnesite številko");
    skeniranje ("% d", & element);
    če (spredaj == -1)
    {
    spredaj = 0;
    zadaj = 0;
    }
    drugače
    {
    zadaj = zadaj + 1;
    }
    čakalna vrsta = element;
    }
    drugače
    {
    f ("čakalna vrsta je polna");
    }
    }
  2. Dequeue: Za brisanje elementa iz čakalne vrste. Funkcija delovanja v C:
    Čakalna vrsta je razglašena za
    int čakalna vrsta, spredaj = -1 in zadaj = -1;
    neveljavno brisanje ()
    {
    element int;
    če (spredaj! = -1)
    {
    item = čakalna vrsta;
    če (spredaj == zadaj)
    {
    spredaj = -1;
    zadaj = -1;
    }
    drugače
    {
    spredaj = spredaj + 1;
    f ("Število izbrisanih je =% d", točka);
    }
    }
    drugače
    {
    f ("Čakalna vrsta je prazna");
    }
    }

Uporaba Stack-a

  • Razčlenitev v prevajalniku.
  • Java virtualni stroj.
  • Razveljavite v urejevalniku besedil.
  • Gumb Nazaj v spletnem brskalniku.
  • PostScript jezik za ers.
  • Izvajanje klicev funkcije v prevajalniku.

Prijave iz čakalne vrste

  • Podatkovni odbojniki
  • Asinhroni prenos podatkov (IO datoteke, cevi, vtičnice).
  • Dodeljevanje zahtev v skupnem viru (er, obdelovalec).
  • Analiza prometa.
  • Določite število blagajnikov v supermarketu.

Zaključek

Stack in čakalna vrstica sta linearni podatkovni strukturi na določene načine različni, kot so delovni mehanizem, struktura, izvedba, različice, vendar se oba uporabljata za shranjevanje elementov na seznamu in izvajanje operacij na seznamu, kot sta dodajanje in brisanje elementov. Čeprav obstajajo nekatere omejitve preproste čakalne vrste, ki se jo povrne z uporabo drugih vrst čakalne vrste.