Stack má pouze jeden konec otevřený pro tlačení a vyskakování datových prvků na druhé straně. Queue má oba konce otevřené pro enquuing a dequeuing datových prvků.
Stack a fronta jsou datové struktury používané pro ukládání datových prvků a jsou ve skutečnosti založeny na nějakém ekvivalentu reálného světa. Zásobník je například svazek disků CD, na kterém můžete vyjmout disk CD a vložit jej do horní části svazku disků CD. Fronta je fronta pro vstupenky do divadla, kde bude první osoba, která stojí na prvním místě, tj. Přední strana fronty, doručena jako první a nová osoba, která přijde, se objeví v zadní části fronty (zadní konec fronty).
Srovnávací graf
| Základ pro srovnání | Zásobník | Fronta |
|---|---|---|
| Pracovní princip | LIFO (Last in First out) | FIFO (první z první) |
| Struktura | Stejný konec se používá pro vkládání a mazání prvků. | Jeden konec se používá pro zasunutí, tj. Zadní konec a druhý konec slouží k vymazání prvků, tj. Předního konce. |
| Počet použitých ukazatelů | Jeden | Dva (v jednoduchém případě fronty) |
| Provedené operace | Push a Pop | Enqueue a dequeue |
| Vyšetření prázdného stavu | Nahoru == -1 | Front == -1 || Přední == Zadní + 1 |
| Vyšetření úplného stavu | Top == Max - 1 | Zadní == Max - 1 |
| Varianty | Nemá varianty. | Má varianty jako kruhová fronta, prioritní fronta, dvojnásobně ukončená fronta. |
| Implementace | Jednodušší | Srovnatelně složité |
Definice zásobníku
Stack je nelimitivní lineární datová struktura. Je to uspořádaný seznam, do kterého je přidána nová položka a existující prvek je vymazán pouze z jednoho konce, nazývaný jako horní část zásobníku (TOS). Jelikož veškeré odstranění a vložení do zásobníku se provádí z horní části zásobníku, poslední přidaný prvek bude první, který bude odstraněn ze zásobníku. To je důvod, proč se zásobník nazývá seznam typu Last-in-First-out (LIFO).
Všimněte si, že prvek, ke kterému se často přistupuje, je nejvyšším prvkem, 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 Poppins). Pokud předpokládáte, že pouze jedna strana obálky je roztržena a sušenky jsou odebírány jeden po druhém. To je to, co se nazývá popping, a podobně, pokud chcete zachovat některé sušenky na nějakou dobu později, budete dát je zpět do balení přes stejný roztrhaný konec se nazývá tlačí.
Definice fronty
Fronta je lineární datová struktura přichází v kategorii neprimitivního typu. Jedná se o sbírku podobných prvků. Přidání nových prvků probíhá na jednom konci zvaném zadní konec. Podobně odstranění existujících prvků probíhá na druhém konci, nazývaném Front-end, a logicky je to seznam typu First in first out (FIFO).
Příklad
V našem každodenním životě se setkáváme s mnoha situacemi, kdy budeme čekat na požadovanou službu, tam se musíme dostat do čekací linky, aby se náš obrat dostal do servisu. Tato čekací fronta může být považována za frontu.
Klíčové rozdíly mezi zásobníku a fronty
- Stack následuje LIFO mechanismus na druhé straně Fronta následuje FIFO mechanismus přidat a odstranit elementy.
- V zásobníku se stejný konec používá k vložení a odstranění prvků. Ve frontě se naopak používají dva různé konce pro vložení a odstranění prvků.
- Stack má pouze jeden otevřený konec, který je důvodem pro použití pouze jednoho ukazatele pro označení horní části zásobníku. Fronta však používá dva ukazatele pro označení přední a zadní části fronty.
- Stack provádí dvě operace známé jako push a pop, zatímco v Queue je známý jako enqueue a dequeue.
- Implementace zásobníku je snazší, protože implementace fronty je složitá.
- Fronta má varianty, jako je například 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:
- Statické implementace používá pole k vytvoření zásobníku. Statická implementace je sice jednoduchá technika, ale není to flexibilní způsob vytvoření, protože deklarace velikosti zásobníku musí být provedena během návrhu programu, poté se velikost nemůže měnit. Statická implementace navíc není příliš efektivní, pokud jde o využití paměti. Protože pole (pro implementační zásobník) je deklarováno před zahájením operace (v době návrhu programu). Pokud je tedy počet prvků, které mají být tříděny, v zásobníku velmi menší, bude staticky přidělená paměť zbytečná. Na druhou stranu, pokud existuje více prvků, které mají být uloženy v zásobníku, pak nemůžeme být schopni změnit velikost pole, aby se zvýšila jeho kapacita, takže se může přizpůsobit novým prvkům.
- Dynamická implementace se také nazývá reprezentace spojeného seznamu a používá ukazatele k implementaci datové struktury typu zásobníku.
Implementace fronty
Frontu lze implementovat dvěma způsoby:
- Statické provedení : Pokud je fronta implementována pomocí polí, musí být 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 frontou fronty a poslední umístění pole bude fungovat jako zadní část fronty. Následující vztah dává celé prvky existující ve frontě při implementaci pomocí polí:
přední - zadní + 1
Je-li „vzadu“, pak ve frontě nebude žádný prvek nebo fronta bude vždy prázdná. - Dynamická implementace : Implementace fronty pomocí ukazatelů, hlavní nevýhodou je, že uzel ve spojené reprezentaci spotřebuje více místa paměti než odpovídající prvek v reprezentaci pole. Vzhledem k tomu, že v každém uzlu jsou alespoň dvě pole 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 nutné vložit nebo odstranit prvek uprostřed skupiny dalších prvků.
Operace na zásobníku
Základní operace, které lze na svazku ovládat, jsou následující:
- PUSH : když je nový prvek přidán do horní části zásobníku, je známý jako operace PUSH. Zatlačením prvku v zásobníku se vyvolá přidání prvku, protože nový prvek bude vložen nahoře. Po každém stisknutí se horní část zvýší o jednu. Pokud je pole plné a nelze přidat nový prvek, nazývá se STACK-FULL stav nebo STACK OVERFLOW. PUSH OPERATION - funkce v C:
Vzhledem k tomu, že zásobník je deklarován jakoint 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 : Když je prvek vymazán z horní části zásobníku, je znám jako operace POP. Po každé operaci popu se zásobník sníží o jednu. Pokud v zásobníku nezůstane žádný prvek a provede se pop, bude to mít za následek stav STACK UNDERFLOW, což znamená, že váš zásobník je prázdný. POP OPERATION - funkce v C:
Vzhledem k tomu, že zásobník je deklarován jakoint 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");}}
Operace ve frontě
Základní operace, které lze provádět ve frontě, jsou:
- Enqueue : Chcete-li vložit prvek do fronty.
Fronta je deklarována jakoint 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 : Chcete-li odstranit prvek z funkce front.Enqueuing v C:
Fronta je deklarována jakoint 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") ;}}
Aplikace Stack
- Analýza v kompilátoru.
- Virtuální stroj Java.
- Zpět v textovém procesoru.
- Tlačítko Zpět ve webovém prohlížeči.
- Jazyk PostScript pro tiskárny.
- Implementace volání funkcí v kompilátoru.
Aplikace fronty
- Datové vyrovnávací paměti
- Asynchronní přenos dat (soubor IO, potrubí, zásuvky).
- Přidělení požadavků na sdílený prostředek (tiskárna, procesor).
- Analýza provozu.
- Určete počet pokladníků, které budete mít v supermarketu.
Závěr
Stack a Queue jsou lineární datové struktury, které se liší určitými způsoby, jako je pracovní mechanismus, struktura, implementace, varianty, ale obě se používají pro ukládání prvků v seznamu a provádění operací na seznamu, jako je přidání a vymazání prvků. Ačkoliv existují některá omezení jednoduché fronty, která je kompenzována použitím jiných typů fronty.
