GMLWiki

Uživatelské nástroje

Nástroje pro tento web

Historie: • Algoritmizace • Procesor a základní deska • Viry a malware • Tiskárny a skenery • Video • Bitmapová grafika • Teorie informace • Historie VT • Sítě (technologie, topologie, HW) • Grafický popis algoritmu
informatika:maturita:21a

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

Obě strany předchozí revizePředchozí verze
informatika:maturita:21a [30. 01. 2018, 13.08] – korekce xsillinginformatika:maturita:21a [16. 03. 2020, 13.57] (aktuální) – Přidána cyklická fronta a též přidány příklady reálné implementace fronty. xbures1
Řá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: autor: xsilling
Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki