Úvod
Poté, co jsme dokončili malou sérii o Stack, začneme s Frontou.
Co je to fronta?
- používá princip „první dovnitř, první ven“
- Příklady:fronta lidí před obchodem, fronta na tiskárny
- Existuje několik způsobů, jak implementovat frontu:pole, jednotlivě propojený seznam, dvojitě propojený seznam
Velké O ve frontě
- Přístup:
O(N) - Hledat:
O(N) - Vložte:
O(1) - Smazat:
O(1)
Příklad
K vytvoření naší fronty použijeme jednotlivě propojený seznam.
A (start) ==> B (end)
- můžeme zařadit (=přidat) až na konec (např. nová osoba bude poslední osobou ve frontě)
- můžeme vyřadit (=odstranit) od začátku (např. osoba na začátku bude obsloužena jako další)
Aje další uzel v řaděAmá ukazatel (next) na další uzel (B)Bje poslední uzel, který jsme zařadili do fronty (=přidali) do fronty- pokud vyřadíme z fronty (=odstraníme)
A, další uzel v řadě by měl býtB
Nastavení
K vytvoření naší fronty potřebujeme následující části:
- Uzel s hodnotou a ukazatelem na další položku ve frontě
- Fronta s délkou, ukazatel na začátek fronty, ukazatel na konec fronty
// a Node has a value (`value`) and a pointer to the next node (`next`)
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
// a Queue has a length (`length`), a start (`start`), an end (`end`)
class Queue {
constructor() {
this.length = 0;
this.start = null;
this.end = null;
}
}
Myšlenky
Nastavili jsme frontu. Nyní potřebujeme v rámci fronty alespoň dvě metody:
- metoda, která přidá nový uzel na konec fronty:
enqueue - metoda, která odebere uzel ze začátku fronty:
dequeue
Další část
Implementujeme naši první metodu pro frontu.
Nenechte si ujít zajímavé věci, přihlaste se k odběru!
Otázky
- Mohli bychom také použít pole k vytvoření fronty. Jak jsme to mohli udělat? Nějaké pro nebo proti?