Fronta je v programování abstraktní datový typ typu FIFO (z anglického First In, First Out, česky První dovnitř, první ven). Fronta používaná v operačních systémech pro meziprocesovou komunikaci je také nazývána roura (angl. pipe). Opakem fronty FIFO je zásobník (LIFO).
Minimální implementace fronty
- inicializace fronty (create)
- vlož položku na konec fronty (enqueue)
- vyber položku ze začátku fronty s čekáním, pokud je fronta prázdná (dequeue)
- vyber položku ze začátku fronty bez čekání - doplňková funkce
- získání položky ze začátku bez jejího odebrání z fronty (peek) nebo (front) - doplňková funkce
- dotaz na prázdnost fronty (is_empty)
Synchronizace
Fronta zpráv je synchronizační primitivum. Skládá se z fronty, do které se ukládají zprávy, funkce pro odeslání zprávy (která může blokovat při zaplnění fronty) a funkce pro přijetí zprávy, která blokuje proces, pokud zpráva není přítomna. Fronta může být pojmenovaná nebo může patřit konkrétnímu programu (a nikdo jiný z ní nesmí zprávy číst).
V praxi existuje obvykle i funkce zjišťující, zda je přítomna zpráva (bez čekání), ale pro funkci synchronizačního primitiva není potřebná.
Složitost v závislosti na implementaci
Frontu lze implementovat (nejen) pomocí paměťového pole, kruhového pole a jednosměrného spojového seznamu. V těchto implementacích je pro všechny operace asymptotická složitost operací konstantní - mimo výběru položky v paměťovém poli. V tomto případě je asymptotická složitost O(n). Je totiž nutné všechny předchozí prvky posunout o jednu pozici doleva.
Související články
- Zásobník (datová struktura)
- Synchronizační primitivum
- Deadlock
- Prioritní fronta implementovaná haldou
Externí odkazy
Obrázky, zvuky či videa k tématu fronta na Wikimedia Commons
 |
Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty. |
| Zdroj dat | cs.wikipedia.org |
|---|---|
| Originál | cs.wikipedia.org/wiki/Fronta_(programování) |
