Stack ja Queue erinevus

• 2019

Stack ja Queue on mõlemad mitte-primitiivsed andmestruktuurid. Peamised erinevused korstnate ja järjekordade vahel on see, et stack kasutab LIFO-d (viimane esmakordselt välja), et pääseda juurde andmetele ja lisada neid elementidele, samas kui järjekord kasutab FIFO (First in first out) meetodit andmeelementide kasutamiseks ja lisamiseks.

Stackil on ainult üks ots, mis on avatud andmeelementide surumiseks ja avamiseks. Teisest küljest on järjekorras mõlemad otsad andmelementide ülesehitamiseks ja deformeerimiseks.

Stack ja järjekord on andmestruktuurid, mida kasutatakse andmeelementide salvestamiseks ja mis põhinevad tegelikult mõnel reaalses maailmas. Näiteks on stack CD-plaat, kus saate CD-plaadi ülaosast CD-plaadi välja võtta ja CD-plaadi panna. Samamoodi on järjekord teatripiletite järjekord, kus esmalt seisev isik, st järjekorra esikülg on kätte toimetatud, ja uus saabuv inimene ilmub järjekorda tagaosas (järje tagaosa).

Võrdluskaart

Võrdluse alus	Stack	Järjekord
Tööpõhimõte	LIFO (viimati esimesena välja)	FIFO (esmakordselt välja)
Struktuur	Sama otsa kasutatakse elementide sisestamiseks ja kustutamiseks.	Ühe otsa kasutatakse sisestamiseks, st tagaosa ja teist otsa kasutatakse elementide kustutamiseks, st esiosa.
Kasutatavate märkide arv	Üks	Kaks (lihtsas järjekorras)
Toimingud	Push ja pop	Enqueue ja dequeue
Tühja seisundi uurimine	Üles == -1	Front == -1 || Front == Tagumine + 1
Täieliku seisundi uurimine	Üles == Max - 1	Tagasi == Max - 1
Variandid	See ei sisalda variante.	Sellel on variandid nagu ümmargune järjekord, prioriteetne järjekord, kahekordselt lõppenud järjekord.
Rakendamine	Lihtsam	Võrdlevalt keeruline

Stacki määratlus

Stack on mitte-primitiivne lineaarne andmestruktuur. See on tellitud nimekiri, kus uus element lisatakse ja olemasolev element kustutatakse ainult ühest otsast, mida nimetatakse virna (TOS) ülaservaks. Kuna kogu deletsioon ja sisestamine virna tehakse alates virna ülemisest osast, on viimane lisatud element stackist esimesena eemaldatav. See on põhjus, miks korstnat nimetatakse nimeks Last-in-First-out (LIFO).

Pange tähele, et korstnatesse sageli juurde pääsev element on ülemine element, kusjuures viimane saadaval olev element on virna allosas.

Näide

Mõned teist söövad küpsiseid (või Poppinsi). Kui eeldate, on ainult üks kate külg purunenud ja küpsised eemaldatakse ükshaaval. Seda nimetatakse poppingiks ja sarnaselt, kui soovite mõneks ajaks mõningaid küpsiseid säilitada, siis paned nad tagasi pakendisse sama rebitud otsa kaudu, mida nimetatakse surumiseks.

Järjekorra määratlus

Järjekord on lineaarne andmestruktuur, mis kuulub mittepriimitaarse tüübi kategooriasse. See on sarnaste elementide kogum. Uute elementide lisamine toimub ühes otsas, mida nimetatakse tagaosaks. Samamoodi toimub olemasolevate elementide kustutamine teises otsas, mida nimetatakse Front-endiks, ja see on loogiliselt loendist First in first (FIFO).

Näide

Meie igapäevaelus oleme kohanud paljusid olukordi, kus me ootame soovitud teenust, sealt peame ootama ooteaega, et meie kätte saada. Seda ootavat järjekorda võib pidada järjekorda.

Stacki ja järjekordade vahelised peamised erinevused

1. Stack järgib LIFO mehhanismi teiselt poolt Queue järgib FIFO mehhanismi elementide lisamiseks ja eemaldamiseks.
2. Stackis kasutatakse elementide sisestamiseks ja kustutamiseks sama lõppu. Vastupidi, elementide sisestamiseks ja kustutamiseks kasutatakse järjekorras kahte erinevat otsa.
3. Kuna Stackil on ainult üks avatud ots, on põhjuseks, miks kasutatakse ainult ühte kursorit, et viidata virna ülaosale. Kuid järjekord kasutab järjekorra eesmise ja tagumise otsa viimiseks kahte näidikut.
4. Stack täidab kahte operatsiooni, mida nimetatakse push ja pop'iks, samas kui järjekorras on see tuntud kui enqueue ja dequeue.
5. Stacki rakendamine on lihtsam, kuid järjekordne rakendamine on keeruline.
6. Järjekorras on variandid nagu ümmargune järjekord, prioriteetne järjekord, kahekordselt lõppenud järjekord jne. Seevastu korstnatel ei ole variante.

Stacki rakendamine

Stacki saab rakendada kahel viisil:

1. Staatiline rakendamine kasutab korstna loomiseks massiive. Staatiline rakendamine on küll kerge tehnikaga, kuid ei ole paindlik loomise viis, kuna stacki suuruse deklaratsioon tuleb teha programmi kavandamise ajal, pärast seda ei saa suurust muuta. Lisaks ei ole staatiline rakendamine mälu kasutamisel väga tõhus. Kuna massiivi (stacki rakendamiseks) on deklareeritud enne operatsiooni algust (programmi kavandamise ajal). Nüüd, kui sorteeritavate elementide arv on stackis väga väike, siis staatiliselt eraldatud mälu raisatakse. Teisest küljest, kui seal on rohkem elemente, mida salvestatakse virna, ei saa me muuta massiivi suurust, et suurendada selle mahtu, nii et see mahutab uusi elemente.
2. Dünaamilist rakendamist nimetatakse ka seotud nimekirja esitluseks ja kasutatakse viiteid andmestruktuuri stack-tüüpi rakendamiseks.

Järjekorra rakendamine

Järjekorda saab rakendada kahel viisil:

1. Staatiline rakendamine : Kui järjekorda rakendatakse massiivide abil, tuleb eelnevalt säilitada järjekorras salvestatavate elementide täpne arv, sest massiivi suurus tuleb deklareerida projekteerimise ajal või enne töötlemise algust. Sel juhul muutub massiivi algus järjekorda ja massiivi viimane asukoht toimib järje taga. Järgnev suhe annab järjekorras kogu elemendi olemasolu massiivide kasutamisel:
   ees - taga + 1
   Kui “tagumine <ees”, siis ei ole järjekorda ühtegi elementi või järjekord on alati tühi.
2. Dünaamiline rakendamine : järjekordade rakendamine viitega, peamine puudus on see, et seotud esinduse sõlme tarbib rohkem mäluruumi kui vastavat elementi massiiviesituses. Kuna iga sõlme puhul on andmevälja jaoks vähemalt kaks välja ja teine, et salvestada järgmise sõlme aadress, samas kui seotud esinduses on ainult andmevälja. Seotud esitusviisi kasutegur muutub selgeks, kui on vaja elementi sisestada või kustutada teiste elementide rühma keskel.

Stacki toimingud

Põhitoimingud, mida saab korstnatega kasutada, on järgmised:

1. PUSH : kui virna ülaosale lisatakse uus element, nimetatakse seda PUSH-toiminguks. Stacki elemendi vajutamine viitab elemendi lisamisele, kuna uus element sisestatakse ülaosas. Pärast iga survetoimingut suurendatakse ülaosa ühe võrra. Kui massiiv on täis ja uut elementi ei saa lisada, nimetatakse seda STACK-FULL või STACK OVERFLOW. PUSH OPERATION - funktsioon C:
   Arvestades, et korstnat on deklareeritud kui
   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");
}
}
2. POP : Kui elemendi ülaosast kustutatakse element, nimetatakse seda POP-toiminguks. Pärast iga popoperatsiooni väheneb korstnat ühe võrra. Kui stackil pole ühtegi elementi ja pop on tehtud, siis see toob kaasa STACK UNDERFLOW seisundi, mis tähendab, et teie virn on tühi. POP OPERATION - funktsioonid C:
   Arvestades, et korstnat on deklareeritud kui
   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");
}
}

Toimingud järjekorda

Põhijärjekorras tehtavad põhitoimingud on järgmised:

1. Enqueue : elemendi sisestamine järjekorda.Kasutamise funktsioon C:
   Järjekord on deklareeritud kui
   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") ;
}
}

2. Dequeue : elemendi kustutamiseks järjekorrast.
   Järjekord on deklareeritud kui
   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") ;
}
}

Stacki rakendused

• Analüüsimine kompilaatoris.
• Java virtuaalne masin.
• Võta sõna tekstiprotsessoris tagasi.
• Tagasi nupp veebibrauseris.
• Printerite PostScript keel.
• Funktsioonikõnede rakendamine kompilaatoris.

Järjekorra rakendused

• Andmepuhvrid
• Asünkroonne andmeedastus (fail IO, torud, pistikupesad).
• Päringute jagamine jagatud ressursile (printer, protsessor).
• Liikluse analüüs.
• Määrake supermarketis olevate kassapidajate arv.

Järeldus

Stack ja Queue on lineaarsed andmestruktuurid, mis erinevad teatavatel viisidel nagu töömehhanism, struktuur, rakendamine, variandid, kuid mõlemaid kasutatakse loendi elementide salvestamiseks ja toimingute tegemiseks nimekirjas nagu elementide lisamine ja kustutamine. Kuigi lihtsate järjekordade puhul on mõningaid piiranguid, mis taastatakse teiste järjekordade abil.