Obsah

• Srovnávací tabulka
• Definice zásobníku
• Příklad
• Definice fronty
• Příklad
• Implementace zásobníku
• Implementace ve frontě
• Operace na zásobníku
• Operace ve frontě
• Aplikace zásobníku
• Aplikace ve frontě
• Závěr

Stack i Queue jsou neaplitivní datové struktury. Hlavní rozdíly mezi zásobníkem a frontou jsou v tom, že zásobník používá k přístupu a přidávání datových prvků metodu LIFO (last in first out), zatímco Queue používá metodu FIFO (First in first out) k přístupu a přidávání datových prvků.

Zásobník má pouze jeden konec otevřený pro tlačení a vyskakování datových prvků na druhé straně Fronta má oba konce otevřené pro enqueuing a dequeuing datových prvků.

Zásobník a fronta jsou datové struktury používané pro ukládání datových prvků a ve skutečnosti jsou založeny na ekvivalentu skutečného světa. Stoh je například stoh CD, kde můžete vyjmout a vložit CD přes horní část stohu CD. Podobně je fronta fronta pro vstupenky do divadla, kde bude první osobě, tj. Přední frontě, doručena první osoba, a nová osoba, která přijde, se objeví na zadní straně fronty (zadní konec fronty).

1. Srovnávací tabulka
2. Definice
3. Klíčové rozdíly
4. Implementace
5. Operace
6. Aplikace
7. Závěr

Srovnávací tabulka

Základ pro srovnání	Zásobník	Fronta
Pracovní princip	LIFO (Last in First out)	FIFO (First in First out)
Struktura	Stejný konec se používá k vkládání a mazání prvků.	Jeden konec se používá pro vložení, tj. Zadní konec a druhý konec se používá pro odstranění prvků, tj. Přední konec.
Počet použitých ukazatelů	Jeden	Dva (v případě jednoduché fronty)
Provedené operace	Push and Pop	Enqueue a dequeue
Vyšetření prázdného stavu	Nahoru == -1	Přední == -1 || Přední == Zadní + 1
Zkouška úplného stavu	Nahoru == Max - 1	Zadní == Max - 1
Varianty	Nemá varianty.	Má varianty jako kruhová fronta, prioritní fronta, dvojnásobně ukončená fronta.
Implementace	Jednodušší	Poměrně složité

Definice zásobníku

Hromada je neprimitivní lineární datová struktura. Je to uspořádaný seznam, do kterého je nová položka přidána a existující prvek je vymazán pouze z jednoho konce, nazývaný jako horní část zásobníku (TOS). Protože veškeré mazání a vkládání do zásobníku se provádí z horní části zásobníku, bude poslední přidaný prvek první, který bude ze zásobníku odstraněn. To je důvod, proč se zásobník nazývá seznam typu Last-in-First-out (LIFO).

Všimněte si, že prvek, který je často ve svazku přístupný, je nejvyšší prvek, zatímco poslední dostupný prvek je ve spodní části zásobníku.

Příklad

Někteří z vás mohou jíst sušenky (nebo poppiny). Pokud předpokládáte, je potrhána pouze jedna strana obalu a sušenky jsou vyjmuty jeden po druhém. Toto se nazývá praskání a podobně, pokud si chcete uchovat nějaké sušenky na nějakou dobu později, vložíte je zpět do balení přes stejný roztržený konec, který se nazývá tlačení.

Definice fronty

Fronta je lineární datová struktura, která spadá do kategorie neaprimitivního typu. Je to sbírka podobných typů prvků. Přidání nových prvků probíhá na jednom konci zvaném zadní konec. Podobně k vymazání existujících prvků dochází na druhém konci zvaném Front-end a logicky se jedná o seznam typu First in first out (FIFO).

Příklad

V našem každodenním životě se setkáváme s mnoha situacemi, kdy musíme čekat na požadovanou službu, musíme se dostat do čekací linky, abychom mohli provést servis. Tuto čekající frontu lze považovat za frontu.

1. Zásobník sleduje mechanismus LIFO na druhé straně Fronta sleduje mechanismus FIFO pro přidávání a odebírání prvků.
2. Ve svazku se stejný konec používá k vložení a odstranění prvků. Naopak, ve frontě jsou použity dva různé konce pro vložení a odstranění prvků.
3. Protože zásobník má pouze jeden otevřený konec, je důvodem k použití pouze jednoho ukazatele k označení horní části zásobníku. Ale fronta používá dva ukazatele k odkazu na přední a zadní konec fronty.
4. Zásobník provádí dvě operace známé jako push a pop, zatímco ve frontě je známý jako enqueue a dequeue.
5. Implementace zásobníku je jednodušší, zatímco implementace fronty je složitá.
6. Fronta má varianty jako kruhová fronta, prioritní fronta, dvojnásobně ukončená fronta atd. Naproti tomu zásobník nemá varianty.

Implementace zásobníku

Zásobník lze použít dvěma způsoby:

1. Statická implementace používá pole k vytvoření zásobníku. Statická implementace je sice technikou bez námahy, ale nejedná se o flexibilní způsob vytváření, protože deklaraci velikosti zásobníku je třeba provést během návrhu programu, poté velikost nelze měnit. Navíc statická implementace není z hlediska využití paměti příliš účinná. Protože je pole (pro implementaci zásobníku) deklarováno před zahájením operace (v době návrhu programu). Nyní, pokud je počet prvků, které mají být tříděny, v zásobníku, staticky přidělená paměť bude ztracena. Na druhou stranu, pokud je v zásobníku uloženo více prvků, nemůžeme být schopni změnit velikost pole, aby se zvýšila jeho kapacita, takže může pojmout nové prvky.
2. Dynamická implementace se také nazývá reprezentace propojeného seznamu a používá ukazatele k implementaci typu datové struktury zásobníku.

Implementace ve frontě

Frontu lze implementovat dvěma způsoby:

1. Statická implementace: Je-li fronta implementována pomocí polí, musí být předem zajištěn přesný počet prvků, které chceme uložit do fronty, protože velikost pole musí být deklarována v době návrhu nebo před zahájením zpracování. V tomto případě se začátek pole stane přední stranou fronty a poslední umístění pole bude fungovat jako zadní fronta. Následující vztah dává celé prvky ve frontě, když jsou implementovány pomocí polí:
   přední - zadní + 1
   Pokud je „zadní <přední“, nebude ve frontě žádný prvek nebo bude vždy prázdná.
2. Dynamická implementace: Při implementaci front pomocí ukazatelů je hlavní nevýhodou to, že uzel v propojené reprezentaci spotřebovává více paměti než odpovídající prvek v reprezentaci pole. Protože v každém uzlu jsou alespoň dvě pole, jedno pro datové pole a další pro uložení adresy dalšího uzlu, zatímco v propojené reprezentaci je zde pouze datové pole. Význam použití propojené reprezentace je zřejmý, když je třeba vložit nebo odstranit prvek uprostřed skupiny dalších prvků.

Operace na zásobníku

Základní operace, které lze na zásobníku ovládat, jsou následující:

1. TAM: když je nový prvek přidán do horní části zásobníku, je znám jako operace PUSH. Zatlačení prvku v zásobníku vyvolá přidání prvku, protože nový prvek bude vložen nahoře. Po každé operaci tlačení se horní část zvětšuje o jednu. Pokud je pole plné a nelze přidat žádný nový prvek, nazývá se STACK-FULL podmínka nebo STACK OVERFLOW. PUSH OPERATION - funkce v C:
   Uvažující se zásobník je deklarován jako
   int stack, top = -1;
neplatné push ()
{
int položka;
pokud (top <4)
{
f („Zadejte číslo“);
skenování ("% d", & položka);
top = top + 1;
stack = item;
}
jiný
{
f („Zásobník je plný“);
}
}
2. POP: Když je prvek odstraněn z horní části zásobníku, je znám jako operace POP. Zásobník se po každé operaci pop sníží o jednu. Pokud na zásobníku není žádný prvek a je provedeno vyskakování, bude to mít za následek STACK UNDERFLOW, což znamená, že váš zásobník je prázdný. POP OPERATION - funkce v C:
   Uvažující se zásobník je deklarován jako
   int stack, top = -1;
neplatné pop ()
{
int položka;
pokud (nahoře> = 4)
{
item = stack;
top = top - 1;
f ("Počet smazaných je =% d", položka);
}
jiný
{
f („Zásobník je prázdný“);
}
}

Operace ve frontě

Základní operace, které lze ve frontě provádět, jsou:

1. Zařadit do fronty: Chcete-li vložit prvek do fronty. Funkce funkce operace v C:
   Fronta je deklarována jako
   int fronta, Front = -1 a zadní = -1;
neplatný add ()
{
int položka;
pokud (zadní <4)
{
f („Zadejte číslo“);
skenování ("% d", & položka);
if (front == -1)
{
přední = 0;
zadní = 0;
}
jiný
{
zadní = zadní + 1;
}
queue = item;
}
jiný
{
f („Fronta je plná“);
}
}

2. Dequeue: Chcete-li odstranit prvek z fronty.Uvádění funkce operace v C:
   Fronta je deklarována jako
   int fronta, Front = -1 a zadní = -1;
neplatné smazání ()
{
int položka;
pokud (přední! = -1)
{
item = fronta;
pokud (přední == zadní)
{
přední = -1;
zadní = -1;
}
jiný
{
přední = přední + 1;
f ("Počet smazaných je =% d", položka);
}
}
jiný
{
f („Fronta je prázdná“);
}
}

Aplikace zásobníku

• Parsování v kompilátoru.
• Virtuální stroj Java.
• Zpět v textovém procesoru.
• Tlačítko Zpět ve webovém prohlížeči.
• PostScriptový jazyk pro ers.
• Implementace volání funkcí v kompilátoru.

Aplikace ve frontě

• Datové vyrovnávací paměti
• Asynchronní přenos dat (soubor IO, roury, sokety).
• Přidělení požadavků na sdílený prostředek (er, procesor).
• Analýza provozu.
• Určete počet pokladníků, které mají v supermarketu.

Závěr

Zásobník a fronta jsou lineární datové struktury, které se určitým způsobem liší, jako je pracovní mechanismus, struktura, implementace, varianty, ale obě se používají pro ukládání prvků v seznamu a provádění operací v seznamu, jako je přidávání a mazání prvků. I když existují určitá omezení jednoduché fronty, která je kompenzována použitím jiných typů fronty.