Uživatelské nástroje
informatika:maturita:21a
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
| Obě strany předchozí revize Předchozí verze | |||
|
informatika:maturita:21a [30. 01. 2018, 13.08] xsilling korekce |
informatika:maturita:21a [16. 03. 2020, 13.57] (aktuální) xbures1 Přidána cyklická fronta a též přidány příklady reálné implementace fronty. |
||
|---|---|---|---|
| Řádek 11: | Řádek 11: | ||
| Funguje na principu **FIFO** (first in first out), to znamená, že si frontu můžeme představit třeba jako frontu na úřadu práce. Lidé (data) se řadí po příchodu do fronty a ve stejném pořadí se i dostanou na řadu (data jsou tedy dříve vrácena). | Funguje na principu **FIFO** (first in first out), to znamená, že si frontu můžeme představit třeba jako frontu na úřadu práce. Lidé (data) se řadí po příchodu do fronty a ve stejném pořadí se i dostanou na řadu (data jsou tedy dříve vrácena). | ||
| + | |||
| + | Jsou potřeba dva ukazatele: front (zde jsou odebírána data) a rear (zde jsou data vkládána) | ||
| ==== Metody Implementace ==== | ==== Metody Implementace ==== | ||
| Řádek 16: | Řádek 18: | ||
| === Pomocí statického pole === | === Pomocí statického pole === | ||
| - | Řešení pomocí statického pole funguje tak, že si vytvoříme danou frontu jako **pole**. V rámci funkce push(objekt) pak postupně dáváme data do pole a ve funkci pop() vždy vezmeme první položku a všechny zbylé posuneme o jedno místo dopředu. | + | Existují dva způsoby statické implementace – klasická a cyklická frotna: |
| - | Nevýhodou tohoto způsobu implementace je, že jsme **omezeni velikostí** námi vytvořeného pole. Výhodou zase naopak je, že za všech okolností **víme, kolik máme na data místa**. | + | U obou variant začínáme tím, že si vytvoříme danou frontu jako **pole**. V rámci funkce push(objekt) pak postupně vkládáme data do pole pomocí ukazatele rear a funkcí pop() získáváme data pomocí ukazatele front. Nyní se dva zmíněné způsoby implementace začínají lišit: |
| + | |||
| + | ** klasická fronta **: Při volání funkce pop() získáme data, snížíme hodnotu rear ukazatele a všechny položky posuneme o jedno dopředu. | ||
| + | |||
| + | zde ukázka klasické varianty statické implementace fronty v jazyce Java: | ||
| + | |||
| + | {{ :informatika:maturita:staticarrayqueue.png?nolink |}} | ||
| + | |||
| + | V rámci konstruktoru vkládáme do fronty čísla 7 a 8 a text "nine", když poté čtyřikrát voláme funkci pop() – zde metoda deQueue() a necháváme vypsat její výstup, finální výstup vypadá takto: | ||
| + | |||
| + | {{ :informatika:maturita:queueoutput.png?nolink |}} | ||
| + | |||
| + | ** cyklická fronta **: Při volání funkce pop() opět získáme data, ale tentokrát hodnotu rear ukazatele ponecháváme a naopak se zvyšuje hodnota ukazatele front. Celá fronza je navíc skutečně cyklická, takže v situaci kdy se uvolní prostor z původního "začátku" fronty, může být znova zaplňen na jejím konci. | ||
| + | |||
| + | viz. diagram: | ||
| + | |||
| + | {{ :informatika:maturita:circularqueuediagram.png?nolink |}} | ||
| + | |||
| + | Nevýhodou statické implementace je, že jsme **omezeni velikostí** námi vytvořeného pole. Výhodou zase naopak je, že za všech okolností **víme, kolik máme na data místa**. | ||
| === Pomocí ukazatelů === | === Pomocí ukazatelů === | ||
| Řádek 26: | Řádek 46: | ||
| {{:informatika:maturita:queuepointerdiagram.png|}} | {{:informatika:maturita:queuepointerdiagram.png|}} | ||
| + | |||
| + | Zde můžeme vidět implementaci pomocí ukazatelů v jazyce Java a to konkrétně s využitím kolekce LinkedList. Všimněme si též těla metody deQueue(), kde musíme zachytávat vyjímku chybějícího ukazatele, je-li fronta prázdná. | ||
| + | |||
| + | {{ :informatika:maturita:dynamicqueue.png?nolink |}} | ||
| ===== Zásobník (stack) ===== | ===== Zásobník (stack) ===== | ||
informatika/maturita/21a.1517314124.txt.gz · Poslední úprava: 30. 01. 2018, 13.08 autor: xsilling
Nástroje pro stránku
