Stack má iba jeden koniec otvorený pre tlačenie a vyskakovanie dátových prvkov na druhej strane. Queue má obidva konce otvorené pre vykrúcanie a vylúčenie dátových prvkov.
Stack a fronta sú dátové štruktúry používané na ukladanie dátových prvkov a skutočne sú založené na ekvivalente v reálnom svete. Napríklad, zásobník je stoh CD, kde môžete vytiahnuť a vložiť CD cez hornú časť stohu CD. Podobne, fronta je fronta pre divadelné vstupenky, kde osoba, ktorá stojí na prvom mieste, tj predná časť frontu bude najprv podaná a nová osoba, ktorá príde, sa objaví v zadnej časti frontu (zadný koniec frontu).
Porovnávacia tabuľka
| Základ pre porovnanie | Stoh | fronta |
|---|---|---|
| Pracovný princíp | LIFO (posledný v prvom out) | FIFO (prvý na prvom mieste) |
| štruktúra | Rovnaký koniec sa používa na vloženie a odstraňovanie prvkov. | Jeden koniec sa používa na vloženie, tj zadný koniec a druhý koniec sa používa na vymazanie prvkov, tj predného konca. |
| Počet použitých ukazovateľov | jeden | Dve (v prípade jednoduchého radu) |
| Vykonané operácie | Push a Pop | Zatlačte a deaktivujte |
| Skúmanie prázdneho stavu | Najvyššie == -1 | Predná strana == -1 || Predná strana == Zadná strana + 1 |
| Skúmanie plného stavu | Najvyššie == Max - 1 | Zadná strana == Max - 1 |
| varianty | Nemá varianty. | Má varianty ako kruhová fronta, prioritná fronta, fronta s dvojnásobným koncom. |
| uskutočnenie | jednoduchšie | Porovnateľne zložité |
Definícia zásobníka
Stack je neprirodzená lineárna štruktúra údajov. Ide o usporiadaný zoznam, do ktorého sa pridáva nová položka a existujúci prvok sa vymaže iba z jedného konca nazývaného ako vrchol zásobníka (TOS). Keďže všetky odstránenie a vloženie do zásobníka sa vykonáva z hornej časti zásobníka, posledný pridaný prvok bude prvý, ktorý sa má odstrániť zo zásobníka. To je dôvod, prečo sa zásobník nazýva zoznam typu Last-in-First-out (LIFO).
Všimnite si, že prvok, ktorý je často prístupný v zásobníku, je najvyšším prvkom, zatiaľ čo posledný dostupný prvok je v dolnej časti zásobníka.
príklad
Niektorí z vás môžu jesť sušienky (alebo Poppins). Ak predpokladáte, že sa roztrhne iba jedna strana krytu a sušienky sa vyberú jeden po druhom. To je to, čo sa nazýva popping, a podobne, ak chcete zachovať niektoré sušienky o niečo neskôr, budete ich vrátiť do balíčka cez rovnaký roztrhnutý koniec sa nazýva pushing.
Definícia frontu
Riadok je lineárna dátová štruktúra, ktorá prichádza do kategórie neprimitívneho typu. Ide o zbierku podobných prvkov. Pridanie nových prvkov prebieha na jednom konci nazývanom zadný koniec. Podobne, odstránenie existujúcich prvkov prebieha na druhom konci nazývanom front-end a je to logicky prvý z prvého zoznamu (FIFO).
príklad
V každodennom živote sa stretávame s mnohými situáciami, v ktorých máme čakať na požadovanú službu, musíme sa dostať do čakacej linky na to, aby sme dostali servis. Tento front čakania možno považovať za frontu.
Kľúčové rozdiely medzi stohom a frontom
- Stack nasleduje na LIFO mechanizmus na druhej strane Queue nasleduje FIFO mechanizmus na pridávanie a odstraňovanie prvkov.
- V zásobníku sa rovnaký koniec používa na vloženie a odstránenie prvkov. Naopak, vo fronte sa používajú dva odlišné konce na vloženie a odstránenie prvkov.
- Ako Stack máte iba jeden otvorený koniec, čo je dôvod, prečo sa používa iba jeden ukazovateľ na označenie hornej časti zásobníka. Riadok však používa dva ukazovatele na označenie frontu a zadného konca frontu.
- Stack vykonáva dve operácie známe ako push a pop, zatiaľ čo v zozname Queue je známy ako skript a dequeue.
- Implementácia zásobníka je jednoduchšia, zatiaľ čo implementácia frontu je zložitá.
- Fronta má varianty ako kruhová fronta, prioritná fronta, dvojitá koncová fronta atď. Naproti tomu zásobník nemá varianty.
Implementácia zásobníka
Stoh je možné použiť dvoma spôsobmi:
- Statická implementácia používa pole na vytvorenie zásobníka. Statická implementácia je však jednoduchou technikou, ale nie je flexibilným spôsobom tvorby, keďže deklarácia veľkosti zásobníka sa musí robiť počas návrhu programu, potom sa veľkosť nemôže meniť. Navyše statická implementácia nie je veľmi efektívna vzhľadom na využitie pamäte. Vzhľadom na to, že pole (pre implementáciu zásobníka) je deklarované pred začiatkom operácie (v čase návrhu programu). Teraz, ak je počet prvkov, ktoré majú byť zoradené, veľmi málo v zásobníku, staticky sa alokuje pamäť. Na druhej strane, ak existuje väčší počet prvkov, ktoré sa majú uložiť v zásobníku, potom nemôžeme zmeniť veľkosť poľa, aby sme zvýšili jeho kapacitu, aby sa mohli prispôsobiť novým prvkom.
- Dynamická implementácia sa tiež nazýva prepojené zobrazenie zoznamov a používa ukazovatele na implementáciu typu zásobníka dátovej štruktúry.
Implementácia frontu
Frontu možno implementovať dvomi spôsobmi:
- Statická implementácia : Ak je fronta implementovaná pomocou polí, musí sa presne zabezpečiť presný počet prvkov, ktoré chceme uložiť vo fronte, pretože veľkosť poľa sa musí deklarovať v čase návrhu alebo pred začiatkom spracovania. V tomto prípade sa začiatok poľa stáva prednou stranou frontu a posledná poloha poľa bude slúžiť ako zadná časť frontu. Nasledujúci vzťah udáva, že všetky prvky existujú vo fronte, keď sú implementované pomocou polí:
predné - zadné + 1
Ak je "zadná <predná", potom nebude vo fronte žiadny prvok alebo fronta bude vždy prázdna. - Dynamická implementácia : implementácia frontu pomocou ukazovateľov, hlavnou nevýhodou je, že uzol v prepojenej reprezentácii spotrebuje viac pamäte než zodpovedajúci prvok v reprezentácii poľa. Pretože v dátovom poli existujú najmenej dve polia v každom uzle a ďalšie na ukladanie adresy ďalšieho uzla, zatiaľ čo v prepojenej reprezentácii existuje len dátové pole. Zásluha používania prepojenej reprezentácie sa stáva zrejmou, keď sa vyžaduje vloženie alebo odstránenie prvku uprostred skupiny ďalších prvkov.
Operácie na zásobníku
Základné operácie, ktoré môžu byť použité v zásobníku, sú nasledovné:
- PUSH : ak je nový prvok pridaný do hornej časti zásobníka, je známy ako operácia PUSH. Stlačením prvku v zásobníku sa vyvolá pridanie prvku, pretože nový prvok bude vložený hore. Po každom stlačení tlačidla sa hora zväčší o jednu. Ak je pole plné a nemôže byť pridaný žiadny nový prvok, nazýva sa stav STACK-FULL alebo STACK OVERFLOW. PUSH OPERATION - funkcia v C:
Vzhľadom na to, že zásobník je deklarovaný akoint 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 : Ak sa prvok vymaže z hornej časti zásobníka, je známy ako operácia POP. Stoh sa zníži o jednu, po každej popovej operácii. Ak na zásobníku nezostane žiadny prvok a vykoná sa pop, výsledkom bude stav STACK UNDERFLOW, čo znamená, že váš zásobník je prázdny. POP OPERATION - funkcie v C:
Vzhľadom na to, že zásobník je deklarovaný akoint 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");}}
Operácie na fronte
Základné operácie, ktoré možno vykonať v rade, sú:
- Enqueue : Ak chcete vložiť prvok do frontu. Funkcia vynechania v C:
Fronta je deklarovaná akoint 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 : Vymazanie prvku z frontu. Funkcia vypínania v C:
Fronta je deklarovaná akoint 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") ;}}
Aplikácie Stack
- Parsovanie v kompilátore.
- Virtuálny stroj Java.
- Späť v textovom procesore.
- Tlačidlo Späť vo webovom prehliadači.
- Jazyk PostScript pre tlačiarne.
- Implementácia volaní funkcie v kompilátore.
Aplikácie fronty
- Dátové vyrovnávacie pamäte
- Asynchrónny prenos dát (súbor IO, potrubia, zásuvky).
- Pridávanie žiadostí o zdieľaný zdroj (tlačiareň, procesor).
- Analýza premávky.
- Určite počet pokladníkov, ktorí majú mať v supermarkete.
záver
Stack a fronta sú lineárne dátové štruktúry sa líšia určitými spôsobmi, ako sú pracovný mechanizmus, štruktúra, implementácia, varianty, ale obe sa používajú na ukladanie prvkov do zoznamu a vykonávanie operácií v zozname ako pridanie a odstránenie prvkov. Hoci existujú určité obmedzenia jednoduchej fronty, ktorá je vrátená použitím iných typov fronty.
