Obsah

• Porovnávacia tabuľka
• Definícia zásobníka
• príklad
• Definícia frontu
• príklad
• Implementácia zásobníka
• Implementácia frontu
• Operácie na zásobníku
• Operácie vo fronte
• Aplikácia zásobníka
• Aplikácie vo fronte
• záver

Stack aj Queue sú neaplitívne dátové štruktúry. Hlavné rozdiely medzi zásobníkom a frontom sú v tom, že zásobník používa metódu LIFO (last in first out) na prístup a pridávanie dátových prvkov, zatiaľ čo front používa na prístup a pridávanie dátových prvkov metódu FIFO (First in first out).

Zásobník má otvorený len jeden koniec na tlačenie a otváranie dátových prvkov na druhej strane. Fronta má otvorené oba konce na enklúziu a dekódovanie dátových prvkov.

Zásobník a front sú dátové štruktúry používané na ukladanie dátových prvkov a v skutočnosti sú založené na nejakom ekvivalente v skutočnom svete. Stoh je napríklad stoh CD, z ktorého môžete vybrať a vložiť CD cez vrch stohu CD. Podobne je fronta frontom do divadelných lístkov, kde sa osobe, ktorá stojí na prvom mieste, t. J. Pred frontu, bude doručená prvá a nová prichádzajúca osoba sa objaví v zadnej časti frontu (zadný koniec frontu).

1. Porovnávacia tabuľka
2. definícia
3. Kľúčové rozdiely
4. uskutočnenie
5. operácie
6. aplikácia
7. záver

Porovnávacia tabuľka

Základ pre porovnanie	Stoh	fronta
Pracovný princíp	LIFO (Posledné v prvom von)	FIFO (prvé v prvom von)
štruktúra	Rovnaký koniec sa používa na vkladanie a mazanie prvkov.	Jeden koniec sa používa na zasunutie, t. J. Zadný koniec a druhý koniec sa používa na odstránenie prvkov, t. J. Predný koniec.
Počet použitých ukazovateľov	jeden	Dva (v prípade jednoduchého poradia)
Vykonané operácie	Push a Pop	Enqueue a dequeue
Skúška stavu prázdneho	Top == -1	Predná strana == -1 || Predné == Zadné + 1
Skúška úplného stavu	Top == Max - 1	Zadné == Max - 1
varianty	Nemá varianty.	Má varianty ako kruhový front, prioritný front, dvojnásobne ukončený front.
uskutočnenie	jednoduchšie	Pomerne zložitý

Definícia zásobníka

Zásobník je neaplitívna lineárna dátová štruktúra. Je to usporiadaný zoznam, do ktorého sa pridáva nová položka a existujúci prvok sa vymaže iba z jedného konca, ktorý sa nazýva ako vrchol stohu (TOS). Pretože celé vymazanie a vloženie do stohu sa uskutoční z vrchu stohu, posledný pridaný prvok bude prvý, ktorý bude zo stohu odstránený. To je dôvod, prečo sa zásobník nazýva typ zoznamu Last-in-First-out (LIFO).

Všimnite si, že prvok, ktorý je často prístupný v zväzku, je najvyšším prvkom, zatiaľ čo posledný dostupný prvok je v spodnej časti zväzku.

príklad

Niektorí z vás môžu jesť sušienky (alebo maky). Ak predpokladáte, je potrhaná iba jedna strana obalu a sušienky sa vyberajú jedna po druhej. Toto sa nazýva praskanie a podobne, ak si chcete uchovať nejaké sušienky na nejaký čas neskôr, vložíte ich späť do balenia pomocou rovnakého roztrhnutého konca, ktorý sa nazýva tlačenie.

Definícia frontu

Fronta je lineárna dátová štruktúra, ktorá patrí do kategórie nepreprimitívneho typu. Je to zbierka podobných typov prvkov. Pridávanie nových prvkov sa uskutočňuje na jednom konci nazývanom zadný koniec. Podobne sa mazanie existujúcich prvkov uskutočňuje na druhom konci, ktorý sa nazýva front-end, a je logicky prvým zoznamom typu FIFO.

príklad

V našom každodennom živote sa stretávame s mnohými situáciami, keď čakáme na požadovanú službu, musíme sa dostať do čakacej rady, aby sme mohli vykonať servis. Túto čakaciu frontu možno považovať za frontu.

1. Zásobník sleduje mechanizmus LIFO na druhej strane Fronta sleduje mechanizmus FIFO na pridávanie a odoberanie prvkov.
2. V zásobníku sa ten istý koniec používa na vkladanie a odstraňovanie prvkov. Naopak, vo fronte sa na vloženie a vymazanie prvkov používajú dva rôzne konce.
3. Pretože zásobník má iba jeden otvorený koniec, je dôvodom použitia iba jedného ukazovateľa na označenie hornej časti stohu. Fronta však používa dva ukazovatele na označenie prednej a zadnej časti frontu.
4. Zásobník vykonáva dve operácie známe ako push a pop, zatiaľ čo vo fronte je známy ako enqueue a dequeue.
5. Implementácia zásobníka je jednoduchšia, zatiaľ čo implementácia frontu je zložitá.
6. Fronta má varianty ako kruhový front, prioritný front, dvakrát ukončený front atď. Na rozdiel od toho zásobník nemá varianty.

Implementácia zásobníka

Zásobník je možné aplikovať dvoma spôsobmi:

1. Statická implementácia používa polia na vytvorenie zásobníka. Statická implementácia je síce nenáročnou technikou, ale nie je flexibilným spôsobom tvorby, pretože deklarovanie veľkosti zásobníka sa musí robiť počas návrhu programu, potom sa veľkosť nedá meniť. Okrem toho statická implementácia nie je príliš efektívna, pokiaľ ide o využitie pamäte. Pretože sa pole (na implementáciu zásobníka) deklaruje pred začiatkom operácie (v čase návrhu programu). Ak je teraz počet prvkov, ktoré sa majú usporiadať, v zásobníku veľmi menší, staticky pridelená pamäť sa stratí. Na druhú stranu, ak je v zásobníku uložených viac prvkov, nemôžeme byť schopní zmeniť veľkosť poľa, aby sme zvýšili jeho kapacitu, aby sa v ňom mohli umiestniť nové prvky.
2. Dynamická implementácia sa nazýva aj reprezentácia prepojeného zoznamu a používa ukazovatele na implementáciu typu dátovej štruktúry zásobníka.

Implementácia frontu

Frontu možno implementovať dvoma spôsobmi:

1. Statická implementácia: Ak sa front implementuje pomocou polí, presný počet prvkov, ktoré chceme uložiť do frontu, sa musí zabezpečiť skôr, pretože veľkosť poľa sa musí deklarovať v čase návrhu alebo pred začatím spracovania. V tomto prípade sa začiatok poľa stane prednou časťou frontu a posledné umiestnenie poľa bude pôsobiť ako zadná časť frontu. Nasledujúci vzťah dáva celkovým prvkom, ktoré existujú vo fronte pri implementácii pomocou polí:
   predný - zadný + 1
   Ak je „zadná <predná“, potom nebude existovať žiadny prvok vo fronte alebo bude vždy prázdny.
2. Dynamická implementácia: Implementáciou frontov pomocou ukazovateľov je hlavnou nevýhodou to, že uzol v prepojenej reprezentácii spotrebuje viac pamäte ako zodpovedajúci prvok v zobrazení poľa. Pretože v každom uzle sú najmenej dve polia, jedno pre dátové pole a ďalšie na uloženie adresy nasledujúceho uzla, zatiaľ čo v prepojenom znázornení je k dispozícii iba dátové pole. Význam použitia prepojenej reprezentácie je zrejmý, keď je potrebné vložiť alebo odstrániť prvok uprostred skupiny ďalších prvkov.

Operácie na zásobníku

Základné operácie, ktoré možno na zásobníku vykonať, sú tieto:

1. TAM: keď je nový prvok pridaný do hornej časti zásobníka, je známy ako operácia PUSH. Zatlačenie prvku v stohu vyvolá pridanie prvku, keďže nový prvok sa vloží hore. Po každej tlačnej operácii sa horná časť zväčší o jednu. Ak je pole plné a nie je možné pridať nový prvok, nazýva sa STACK-FULL alebo STACK OVERFLOW. PUSH OPERATION - funkcia v C:
   Zohľadnenie zásobníka je deklarované ako
   int stack, top = -1;
neplatné tlačenie ()
{
int položka;
ak (hore <4)
{
f („Zadajte číslo“);
skenovanie ("% d", & položka);
top = top + 1;
stack = item;
}
inak
{
f („Zásobník je plný“);
}
}
2. POP: Keď sa prvok odstráni z hornej časti zásobníka, nazýva sa to operácia POP. Zásobník sa po každej operácii pop zníži o jednu. Ak v zásobníku nezostane žiadny prvok a vykoná sa pop, bude to mať za následok STACK UNDERFLOW, čo znamená, že váš stack je Empty. POP OPERATION - funguje v C:
   Zohľadnenie zásobníka je deklarované ako
   int stack, top = -1;
neplatné pop ()
{
int položka;
ak (hore> = 4)
{
item = stack;
top = top - 1;
f („Počet vymazaných je =% d“, položka);
}
inak
{
f („Zásobník je prázdny“);
}
}

Operácie vo fronte

Základné operácie, ktoré možno vykonať vo fronte, sú:

1. Enqueue: Na vloženie elementu do frontu. Vyžadujúca operačná funkcia v C:
   Fronta sa deklaruje ako
   fronta vpredu, predná = -1 a zadná = -1;
neplatné pridanie ()
{
int položka;
ak (zadný <4)
{
f („Zadajte číslo“);
skenovanie ("% d", & položka);
ak (front == -1)
{
front = 0;
zadná = 0;
}
inak
{
zadný = zadný + 1;
}
front = položka;
}
inak
{
f („Fronta je plná“);
}
}

2. dequeue: Vymazanie prvku z frontu. Vyžadujúca operačná funkcia v C:
   Fronta sa deklaruje ako
   fronta vpredu, predná = -1 a zadná = -1;
neplatné vymazanie ()
{
int položka;
ak (vpredu! = -1)
{
item = front;
ak (predná == zadná)
{
front = -1;
zadná = -1;
}
inak
{
predné = predné + 1;
f („Počet vymazaných je =% d“, položka);
}
}
inak
{
f („Poradie je prázdne“);
}
}

Aplikácia zásobníka

• Analýza v kompilátore.
• Virtuálny stroj Java.
• Vrátiť späť v textovom editore.
• Tlačidlo Späť vo webovom prehľadávači.
• PostScriptový jazyk pre ers.
• Implementácia volaní funkcií v kompilátore.

Aplikácie vo fronte

• Dátové vyrovnávacie pamäte
• Asynchrónny prenos údajov (súbor IO, rúry, zásuvky).
• Pridelenie požiadaviek na zdieľaný prostriedok (er, procesor).
• Analýza dopravy.
• Určite počet pokladníkov, ktoré majú mať v supermarkete.

záver

Stack a Queue sú lineárne dátové štruktúry, ktoré sa určitým spôsobom líšia, ako napríklad pracovný mechanizmus, štruktúra, implementácia, varianty, ale obidve sa používajú na ukladanie prvkov v zozname a na vykonávanie operácií v zozname, ako je pridávanie a odstraňovanie prvkov. Aj keď existujú jednoduché obmedzenia jednoduchého frontu, ktoré sa kompenzujú použitím iných typov frontu.