Fronta (datová struktura)

Znázornění fronty

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

Externí odkazy

Média použitá na této stránce

Data Queue.svg
Autor:
This Image was created by User:Vegpuff.
  • If you are using the image under the creative commons share alike license please credit the photo Vegpuff/Wikipedia and include a link to this page. No explicit permission is needed from me, but an email if my work has been of help to you.
  • If you dont want to release your work under a creative commons license, please mail me at vegpuff@gmail.com or catch me at my twitter stream for a custom license.
, Licence: CC BY-SA 3.0
Diagram representing Data Queues