Razlika med skladom in čakalno vrsto

2019

Stack in Queue sta ne-primitivni podatkovni strukturi. Glavne razlike med stackom in čakalno vrsto so, da sklad uporablja metodo LIFO (zadnji v prvem izhodu) za dostopanje in dodajanje podatkovnih elementov, medtem ko Queue uporablja metodo FIFO (prvi v prvi vrsti) za dostop in dodajanje podatkovnih elementov.

Stack ima samo en konec odprt za potiskanje in iztiskanje podatkovnih elementov na drugi strani.

Stack in čakalne vrste so podatkovne strukture, ki se uporabljajo za shranjevanje podatkovnih elementov in dejansko temeljijo na ekvivalentu resničnega sveta. Na primer, stack je kup CD-jev, kjer lahko vzamete in vstavite CD na vrh kupa CD-jev. Podobno je čakalna vrsta čakalna vrsta za gledališke vozovnice, kjer je oseba, ki stoji na prvem mestu, tj. Sprednji del čakalne vrste, najprej vročena in nova prispela oseba se bo pojavila na zadnji strani čakalne vrste (zadnji konec čakalne vrste).

Primerjalna tabela

Podlaga za primerjavo	Stack	Čakalna vrsta
Načelo dela	LIFO (zadnji na prvem mestu)	FIFO (prva na prvem mestu)
Struktura	Isti konec se uporablja za vstavljanje in brisanje elementov.	En konec se uporablja za vstavljanje, tj. Zadnji konec in drugi konec se uporablja za izbris elementov, tj prednji konec.
Število uporabljenih kazalcev	Ena	Dva (v primeru enostavne čakalne vrste)
Opravljene operacije	Push in pop	Ujemite in odstranite
Pregled praznega stanja	Na vrh == -1	Spredaj == -1 \|\| Spredaj == Zadaj + 1
Pregled popolnega stanja	Na vrh == Max - 1	Zadaj == Max - 1
Različice	Ne vsebuje variant.	Ima različice, kot so krožna čakalna vrsta, prednostna čakalna vrsta, dvojno končana čakalna vrsta.
Izvajanje	Enostavno	Primerjalno zapleten

Opredelitev stack

Stack je ne-primitivna struktura podatkov. To je urejen seznam, kjer je dodan nov element in obstoječi element se izbriše iz enega samega konca, ki se imenuje vrh steka (TOS). Ker je vse brisanje in vstavljanje v sklad, izvedeno z vrha skladov, bo zadnji dodani element prvi, ki bo odstranjen iz sklada. To je razlog, zakaj se stack imenuje tip seznama LIFO (Last-in-First-out).

Upoštevajte, da je element, ki je pogosto dostopen v skladu, najvišji element, zadnji razpoložljivi element pa je na dnu sklada.

Primer

Nekateri od vas lahko jedo piškote (ali Poppins). Če predvidevate, je samo ena stran pokrova raztrgana in piškoti se vzamejo eno za drugo. To je tisto, kar se imenuje popping, in podobno, če želite ohraniti nekaj piškotov za nekaj časa kasneje, jih boste vrnili nazaj v paket skozi isto raztrgano konico, ki se imenuje potiskanje.

Opredelitev čakalne vrste

Vrstica je linearna podatkovna struktura, ki prihaja v kategorijo ne-primitivnega tipa. Je zbirka podobnih elementov. Dodatek novih elementov poteka na enem koncu, imenovanem zadnji konec. Podobno se brisanje obstoječih elementov opravi na drugem koncu, ki se imenuje Front-end, in je logično prvi na prvem mestu (FIFO) vrsta seznama.

Primer

V našem vsakodnevnem življenju naletimo na številne situacije, v katerih čakamo na želeno storitev, tam pa moramo v čakalno vrsto za našo vrsto za servisiranje. To čakalno vrsto lahko obravnavamo kot čakalno vrsto.

Ključne razlike med skladom in čakalno vrsto

Stack sledi LIFO mehanizmu na drugi strani pa Queue sledi FIFO mehanizmu za dodajanje in odstranjevanje elementov.
V nizu se isti konec uporablja za vstavljanje in brisanje elementov. Nasprotno, v čakalni vrsti se uporabljata dva različna konca za vstavljanje in brisanje elementov.
Ker imajo Stack samo en odprt konec, je razlog, da se uporablja le en kazalec, ki se nanaša na vrh sklada. Čakalna vrsta pa uporablja dve kazalniki za sprednji in zadnji del čakalne vrste.
Stack izvede dve operaciji, znani kot push in pop, v Queue pa je znana kot enqueue in dequeue.
Implementacija skladov je lažja, medtem ko je izvajanje čakalne vrste težavno.
Queue ima različice, kot so krožna čakalna vrsta, prednostna čakalna vrsta, dvojno končana čakalna vrsta itd. Nasprotno pa stack nima variant.

Implementacija skladov

Stack lahko uporabite na dva načina:

Statično izvajanje uporablja matrike za ustvarjanje skladov. Statična izvedba je preprosta tehnika, vendar ni fleksibilen način ustvarjanja, saj je treba izjavo o velikosti kupa narediti med načrtovanjem programa, potem pa velikosti ni mogoče spreminjati. Poleg tega statična izvedba ni zelo učinkovita pri uporabi pomnilnika. Ker je polje (za izvedbo skladov) razglašeno pred začetkom operacije (v času oblikovanja programa). Če je število elementov, ki jih želite razvrstiti, v nizu manj, bo statično dodeljen pomnilnik zapravljen. Po drugi strani pa, če je v skladu več elementov, ki jih je treba shraniti, ne moremo spremeniti velikosti matrike, da bi povečali njeno zmogljivost, tako da lahko sprejme nove elemente.
Dinamična izvedba se imenuje tudi povezava s povezanim seznamom in uporablja kazalce za implementacijo tipa podatkovne strukture.

Izvedba čakalne vrste

Čakalna vrsta se lahko izvaja na dva načina:

Statična izvedba : Če je čakalna vrsta izvedena z uporabo nizov, je treba predhodno zagotoviti točno število elementov, ki jih želimo shraniti v čakalno vrsto, ker mora biti velikost polja deklarirana ob č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 zadnji del čakalne vrste. Naslednja relacija daje celim elementom, ki obstajajo v čakalni vrsti, ko so uporabljeni nizi:
spredaj - zadaj + 1
Če »zadaj <spredaj« ne bo nobenega elementa v čakalni vrsti ali čakalne vrste bodo vedno prazne.
Dinamična izvedba : Izvajanje čakalnih vrst s kazalci, glavna pomanjkljivost je, da vozlišče v povezani predstavitvi porabi več pomnilnika kot ustrezen element v matrični predstavitvi. Ker sta v vsakem vozlišču vsaj dve polji za podatkovno polje in drugo za shranjevanje naslova naslednjega vozlišča, medtem ko je v povezani predstavitvi tam le podatkovno polje. Zasluge za uporabo povezane predstavitve postanejo očitne, ko je potrebno vstaviti ali izbrisati element v sredini skupine drugih elementov.

Operacije na Stacku

Osnovne operacije, ki jih je mogoče upravljati na skladu, so naslednje:

PUSH : ko je na vrh kupa dodan nov element, je znan kot delovanje PUSH. Potiskanje elementa v sklad zasede dodajanje elementa, ker bo novi element vstavljen na vrhu. Po vsakem pritisku se vrh poveča za eno. Če je polje polno in ni mogoče dodati nobenega novega elementa, se imenuje stanje STACK-FULL ali STACK OVERFLOW. PUSH OPERATION - funkcija v C:
Glede na stack je deklariran kot
int stack [5], top = -1;
void push()
{
int item;
if (top < 4)
{
printf ("Enter the number") ;
scan ("%d", & item) ;
top = top + 1;
stack [top] = item;
}
else
{
printf (" Stack is full");
}
}
POP : Če je element izbrisan z vrha, ga imenujemo operacija POP. Stack se zmanjša za eno, po vsaki pop operaciji. Če v skladu ni nobenega elementa in se izvede pop, bo to povzročilo stanje STACK UNDERFLOW, kar pomeni, da je vaš sklad prazen. OPERACIJA POP - funkcije v C:
Glede na stack je deklariran kot
int stack [5], top = -1;
void pop()
{
int item;
if (top >= 4)
{
item = stack [top];
top = top - 1;
printf ("Number deleted is = %d", item) ;
}
else
{
printf (" Stack is empty");
}
}

Operacije v čakalni vrsti

Osnovne operacije, ki se lahko izvedejo na čakalni vrsti, so:

Enqueue : za vstavitev elementa v čakalno vrsto.
Čakalna vrsta je deklarirana kot
int queue [5], Front = -1 and rear = -1;
void add ()
{
int item;
if ( rear < 4)
{
printf ("Enter the number") ;
scan ("%d", & item) ;
if (front == -1)
{
front =0 ;
rear =0 ;
}
else
{
rear = rear + 1;
}
queue [rear] = item ;
}
else
{
printf ("Queue is full") ;
}
}
Dequeue : Za brisanje elementa iz čakalne vrste.
Čakalna vrsta je deklarirana kot
int queue [5], Front = -1 and rear = -1;
void delete ()
{
int item;
if ( front ! = -1)
{
item = queue [ front ] ;
if (front == rear)
{
front =-1 ;
rear =-1 ;
}
else
{
front = front + 1;
printf ("Number deleted is = %d", item) ;
}
}
else
{
printf ("Queue is empty") ;
}
}

Aplikacije Stack

Parsing v prevajalniku.
Navidezni stroj Java.
Razveljavi v urejevalniku besedil.
Gumb Nazaj v spletnem brskalniku.
Jezik PostScript za tiskalnike.
Izvajanje funkcijskih klicev v prevajalniku.

Aplikacije čakalne vrste

Vmesniki podatkov
Asinhroni prenos podatkov (datoteka IO, cevi, vtičnice).
Dodeljevanje zahtev za vire v skupni rabi (tiskalnik, procesor).
Analiza prometa.
Določite število blagajn, ki jih želite imeti v supermarketu.

Zaključek

Stack in Queue sta linearni podatkovni strukturi, ki se razlikujeta na določene načine, kot sta delovni mehanizem, struktura, izvedba, različice, vendar se oba uporabljata za shranjevanje elementov na seznamu in izvajanje operacij na seznamu, kot sta dodatek in brisanje elementov. Čeprav obstajajo nekatere omejitve enostavne čakalne vrste, ki se povrne z uporabo drugih vrst čakalnih vrst.