Turinys

• Palyginimo diagrama
• Stack apibrėžimas
• Pavyzdys
• Eilės apibrėžimas
• Pavyzdys
• Stack įgyvendinimas
• Eilių įgyvendinimas
• Operacijos ant kamino
• Operacijos eilėje
• „Stack“ programos
• Eilės paraiškos
• Išvada

Stack ir Queue yra ne primityvios duomenų struktūros. Pagrindiniai skirtumai tarp krūvos ir eilės yra tie, kad krūva naudojasi LIFO (paskutinis iš pirmo išėjimo) metodu, kad pasiektų ir papildytų duomenų elementus, o eilė naudoja FIFO (pirmasis iš pirmo į išorę) metodą, kad pasiektų ir pridėtų duomenų elementus.

Stack yra tik vienas galas, atidarytas duomenų elementams stumti ir iššokti, kita vertus, eilėje yra abu galai, skirti duomenų elementams užmegzti ir sunaikinti.

Rietuvė ir eilė yra duomenų struktūros, naudojamos duomenų elementams saugoti, ir iš tikrųjų yra pagrįstos kažkokiu realaus pasaulio ekvivalentu. Pvz., Krūva yra kompaktinių diskų krūva, kurią galite išimti ir sudėti į kompaktinį diską per kompaktinių diskų rinkinio viršutinę dalį. Lygiai taip pat eilė yra teatro bilietų eilė, kai pirmiausia stojantis asmuo, t.y., eilės priekis bus aptarnautas, o atvykęs naujas asmuo pasirodys eilės gale (eilės gale).

1. Palyginimo diagrama
2. Apibrėžimas
3. Pagrindiniai skirtumai
4. Įgyvendinimas
5. Operacijos
6. Programos
7. Išvada

Palyginimo diagrama

Palyginimo pagrindas	Stack	Eilė
Darbo principas	LIFO (paskutinis iš pirmo)	FIFO (pirmas iš pirmo)
Struktūra	Ta pati pabaiga naudojama elementams įterpti ir ištrinti.	Vienas galas yra naudojamas įterpimui, t.y., galinis galas, o kitas galas yra naudojamas elementams ištrinti, t.y., priekinis galas.
Naudotų rodyklių skaičius	Vieną	Du (paprastu eilės atveju)
Atliktos operacijos	„Push and Pop“	Enqueque ir dequeque
Tuščios būklės tyrimas	Viršuje == -1	Priekis == -1 || Priekis == Galinis + 1
Visiškos būklės tyrimas	Viršuje == Daugiausiai - 1	Galinis == Maks. - 1
Variantai	Tai neturi variantų.	Jis turi tokius variantus kaip žiedinė eilė, prioritetinė eilė, dvigubai baigta eilė.
Įgyvendinimas	Paprastesnis	Palyginti sudėtinga

Stack apibrėžimas

Stack yra ne primityvi linijinė duomenų struktūra. Tai yra užsakytas sąrašas, kuriame pridedamas naujas elementas, o esamas elementas ištrinamas tik iš vieno galo, vadinamo krūvos viršuje (TOS). Kadangi visas trynimas ir įdėjimas į krūvą atliekamas iš krūvos viršaus, paskutinis pridėtas elementas bus pirmasis, kuris bus pašalintas iš krūvos. Dėl šios priežasties „stack“ yra vadinamas „LIFE“ sąrašo tipu.

Atminkite, kad elementas, į kurį dažnai kreipiamasi rietuvėje, yra aukščiausias elementas, o paskutinis prieinamas elementas yra rietuvės apačioje.

Pavyzdys

Kai kurie iš jūsų gali valgyti sausainius (arba „Poppins“). Jei manote, tik viena dangtelio pusė yra suplėšyta, o sausainiai išimami po vieną. Tai vadinama „popping“, ir panašiai, jei norite kurį laiką konservuoti sausainius vėliau, įdėkite juos atgal į pakuotę per tą patį suplėšytą galą, vadinamą stumdymą.

Eilės apibrėžimas

Eilė yra linijinė duomenų struktūra, kuri priklauso ne primityvaus tipo kategorijai. Tai panašaus tipo elementų kolekcija. Naujų elementų pridėjimas vyksta viename gale, vadinamame galine dalimi. Panašiai esamų elementų ištrynimas vyksta kitame gale, vadinamame „Front-end“, ir logiškai tai yra „FIFO“ tipo sąrašas „Visų pirma iš pirmo“.

Pavyzdys

Kasdieniniame gyvenime susiduriame su daugybe situacijų, kai laukiame norimos paslaugos, ten turime patekti į savo eilę, kad galėtume aptarnauti. Ši laukimo eilė gali būti suvokiama kaip eilė.

1. Stack seka LIFO mechanizmą, kita vertus, eilutė seka FIFO mechanizmą elementams pridėti ir pašalinti.
2. Rinkinyje tas pats galas naudojamas elementams įterpti ir ištrinti. Elementams įterpti ir ištrinti eilėje, priešingai, naudojami du skirtingi galai.
3. Kadangi „Stack“ turi tik vieną atvirą galą, todėl reikia naudoti tik vieną žymiklį, nukreipiantį į krūvos viršutinę dalį. Bet eilėje naudojami du rodyklės, kad būtų galima nukreipti į priekį ir užpakalinį eilės galą.
4. „Stack“ atlieka dvi operacijas, žinomas kaip „push“ ir „pop“, o eilėje jos žinomos kaip „enqueque and dequeque“.
5. Įdiegimas kaminuose yra lengvesnis, o eilių diegimas yra sudėtingas.
6. Eilėje yra tokių variantų kaip apskritoji eilė, prioritetinė eilė, dvigubai baigta eilė ir tt Priešingai, krūva variantų neturi.

Stack įgyvendinimas

Paketą galima pritaikyti dviem būdais:

1. Statinis įgyvendinimas naudoja masyvus, kad sukurtų krūvą. Statinis diegimas yra be pastangų reikalaujantis būdas, tačiau nėra lankstus kūrimo būdas, nes krūvos dydį reikia deklaruoti kuriant programą, o tada jo dydis negali būti keičiamas. Be to, statinis įgyvendinimas nėra labai efektyvus naudojant atmintį. Kadangi masyvas (kamino įgyvendinimui) deklaruojamas prieš operacijos pradžią (programos sudarymo metu). Dabar, jei krūvoje bus mažiau rūšiuojamų elementų, statiškai paskirta atmintis bus švaistoma. Kita vertus, jei krūvoje yra daugiau elementų, kuriuos reikia saugoti, tada negalime pakeisti masyvo dydžio, kad padidintume jo talpą, kad jame būtų naujų elementų.
2. Dinaminis įgyvendinimas taip pat vadinamas susietų sąrašų vaizdavimu ir naudoja rodykles duomenų struktūros kamino tipui įgyvendinti.

Eilių įgyvendinimas

Eilę galima įgyvendinti dviem būdais:

1. Statinis įgyvendinimas: Jei eilė įgyvendinama naudojant masyvus, prieš tai turi būti užtikrintas tikslus elementų, kuriuos norime išsaugoti eilėje, skaičius, nes masyvo dydis turi būti deklaruotas projektavimo metu arba prieš pradedant apdorojimą. Tokiu atveju masyvo pradžia taps eilės priekine dalimi, o paskutinė masyvo vieta veiks kaip eilės užpakalinė dalis. Šis ryšys parodo, kad visi elementai egzistuoja eilėje, kai jie įgyvendinami naudojant masyvus:
   priekis - galas + 1
   Jei „užpakalis <priekis“, eilėje nebus jokio elemento arba eilė visada bus tuščia.
2. Dinaminis įgyvendinimas: Įgyvendinant eiles naudojant rodykles, pagrindinis trūkumas yra tas, kad susietojo mazgo mazgas sunaudoja daugiau atminties nei atitinkamas elementas masyvo vaizde. Kadangi kiekviename mazge yra mažiausiai du laukai - vienas duomenų laukui, o kitas - kito mazgo adresui saugoti, o susietoje reprezentacijoje yra tik duomenų laukas. Susieto atvaizdo naudojimo pranašumas tampa akivaizdus, ​​kai reikia įterpti arba ištrinti elementą kitų elementų grupės viduryje.

Operacijos ant kamino

Pagrindinės operacijos, kurias galima atlikti su rietuve, yra šios:

1. PUSH: kai krūvos viršuje pridedamas naujas elementas, žinomas kaip PUSH operacija. Stumiant elementą krūvoje, elementas pridedamas, nes naujas elementas bus įdėtas viršuje. Po kiekvieno stumimo operacijos viršus padidinamas vienu. Jei masyvas yra pilnas ir joks naujas elementas negali būti pridėtas, jis vadinamas STACK-FULL arba STACK OVERFLOW. PUSH OPERATION - funkcija C:
   Atsižvelgiant į kaminą, jis deklaruojamas kaip
   vidinis krūvis, viršuje = -1;
tuščias stumimas ()
{
int punktas;
jei (viršuje <4)
{
f („Įveskite numerį“);
nuskaityti („% d“, & elementas);
viršuje = viršuje + 1;
kaminas = daiktas;
}
Kitas
{
f („Stack has full“);
}
}
2. POP: Kai elementas ištrinamas iš krūvos viršaus, jis žinomas kaip POP operacija. Po kiekvienos operacijos krūva sumažėja viena. Jei krūvoje neliko nė vieno elemento ir bus atliktas iššokimas, tai lems „STACK UNDERFLOW“ būklę, tai reiškia, kad jūsų krūva tuščia. POP OPERATION - funkcijos C:
   Atsižvelgiant į kaminą, jis deklaruojamas kaip
   vidinis krūvis, viršuje = -1;
tuščias pop ()
{
int punktas;
if (viršuje> = 4)
{
prekė = kaminas;
viršuje = viršuje - 1;
f („Skaičius išbrauktas =% d“, punktas);
}
Kitas
{
f („Rinkinys tuščias“);
}
}

Operacijos eilėje

Pagrindinės operacijos, kurias galima atlikti eilėje, yra šios:

1. Enqueque: Norėdami įterpti elementą į eilę. Įjungti C funkciją:
   Eilė deklaruojama kaip
   vidinė eilė, priekis = -1 ir galas = -1;
void add ()
{
int punktas;
jei (galinis <4)
{
f („Įveskite numerį“);
nuskaityti („% d“, & elementas);
if (priekyje == -1)
{
priekis = 0;
galinis = 0;
}
Kitas
{
galinis = galinis + 1;
}
eilė = prekė;
}
Kitas
{
f („Eilė pilna“);
}
}

2. Nuvilkite: Jei norite ištrinti elementą iš eilės, paleiskite funkciją C:
   Eilė deklaruojama kaip
   vidinė eilė, priekis = -1 ir galas = -1;
panaikinti panaikinimą ()
{
int punktas;
if (priekyje! = -1)
{
prekė = eilė;
if (priekis == galinis)
{
priekis = -1;
užpakalinė = -1;
}
Kitas
{
priekis = priekis + 1;
f („Skaičius išbrauktas =% d“, punktas);
}
}
Kitas
{
f („Eilutė tuščia“);
}
}

„Stack“ programos

• Analizavimas kompiliatoriuje.
• „Java“ virtualioji mašina.
• Anuliuoti teksto rengyklėje.
• Mygtukas „Atgal“ interneto naršyklėje.
• PostScript kalba ers.
• Funkcijų kvietimų įgyvendinimas kompiliatoriuje.

Eilės paraiškos

• Duomenų buferiai
• Asinchroninis duomenų perdavimas (failo IO, vamzdžiai, lizdai).
• Užklausų paskirstymas bendrai naudojamame šaltinyje (er, procesoriuje).
• Eismo analizė.
• Nustatykite, kiek kasininkų turi būti prekybos centre.

Išvada

Stack ir Queue yra linijinės duomenų struktūros, kurios tam tikrais būdais skiriasi, pvz., Darbo mechanizmas, struktūra, įgyvendinimas, variantai, tačiau abu jie yra naudojami elementų saugojimui sąraše ir operacijų sąraše atlikimui, pavyzdžiui, elementų pridėjimui ir ištrynimui. Nors yra keletas paprastos eilės, kuri atkuriama naudojant kitas eilės rūšis, apribojimų.