Průvodce pro začátečníky k porozumění frontám a prioritním frontám

Jako programátor budete pracovat s různými datovými strukturami v závislosti na rozsahu vašich projektů. Jedním takovým konceptem je datová struktura fronty; fronty jsou pro studenty zásadní a používají se v mnoha důležitých algoritmech. Stejně jako fronty mají prioritní fronty podobný koncept, ale mají několik zásadních rozdílů.

Čtěte dále, abyste porozuměli frontám a prioritním frontám.

Co je to fronta?

Fronta je jednoduchá datová struktura, která má celou řadu aplikací v reálných projektech kódování. Datové struktury jsou ve své podstatě abstraktní, ale kvůli jednoduchosti si představujeme, že datová struktura fronty má lineární tvar se dvěma různými konci.

Z hlediska časové složitosti umožňuje fronta vkládání (zařazování) a mazání (odstraňování) v čase O (1). Díky své asymptotické účinnosti jsou fronty efektivní pro velké datové sady. Fronty jsou ve své podstatě FIFO (first-in-first-out), což znamená, že k datové položce, která je vložena jako první, bude přistupováno jako první. Naproti tomu zásobníky mají povahu LIFO (last-in-first-out-out) a mají pouze jeden otevřený konec.

Představte si frontu na lístky v kině; každý nový zákazník, který přijde, se připojí do fronty na jednom konci. Jeden po druhém si každý zákazník koupí lístek a opustí frontu z frontendu. Datová struktura fronty funguje přesně jako každá fronta v reálném světě a data se vkládají (zařazují do fronty) na jeden konec a odebírají (vyřazují z fronty) na druhém konci. Nyní už snad můžete pochopit zdůvodnění, proč se fronty řídí metodikou FIFO.

Fronta má spoustu reálných kódovacích aplikací. Běžněji se používá v aplikacích, kde data nemusí být zpracována okamžitě, ale spíše v pořadí FIFO. Plánování disku, asynchronní přenos dat, semafory jsou některé typické aplikace. Fronty využívají také úlohy plánování, kdo dřív přijde, ten dřív slouží, jako například zařazování tisku nebo vyrovnávací paměti vstupních zařízení.

Co je prioritní fronta?

Fronta priorit je podobná frontě, ale má další vlastnosti. Když je datový prvek zařazen do fronty priorit, je mu přiděleno číslo priority. Na rozdíl od vyřazení ze standardní fronty se datové prvky s vysokou prioritou odstraní před datovými prvky s nízkou prioritou. Priorita nahrazuje pořadí příchodu do prioritní fronty, což je důvod, proč prioritní fronty nemají konzistentní povahu FIFO.

Příbuzný: Algoritmy, které by měl znát každý programátor

Programátoři mohou implementovat prioritní frontu několika způsoby. Jednoduchou implementací je použití pole s datovou položkou struktury/třídy a datová položka bude obsahovat prioritu každého datového prvku a samotných dat. Další implementací primitivní prioritní fronty je použití propojeného seznamu. Prioritní fronty implementované prostřednictvím propojených seznamů jsou funkční, ale vzhledem k jejich výkonu nejsou ideální.

Frontu s lepší prioritou můžete implementovat pomocí hromady. Pokud si vzpomenete, binární haldy dávají maximální nebo minimální prvek za 0 (1) času a vložení trvá pouze 0 (logN). S pomocí hromádek poskytují prioritní fronty asymptoticky lepší výkon ve srovnání s frontami nebo poli.

Prioritní fronta má také řadu nezbytných aplikací. Prioritní fronty jsou klíčové v grafických algoritmech, jako je Prim's Minimum Spanning Tree a Dijkstra's Shortest Path algoritmus. Jsou také ideální v algoritmech plánování procesů výpočetní jednotky (CPU).

Naučte se datové struktury

Fronty a prioritní fronty jsou důležité datové struktury pro všechny začátečníky. Je velmi důležité, aby studenti byli s implementací těchto datových struktur spokojeni a používali je v různých projektech.

Další datové struktury, jako jsou hromady, hromádky a stromy, jsou pro studenty a profesionály stejně důležité. Je také velmi běžné, že tazatelé dotazují žadatele na datové struktury.

Po přečtení tohoto článku byste nyní měli mít dobrou představu o tom, jak fronty a prioritní fronty fungují. Pokud se vám vše zdá stále trochu nejasné, s těmito se vypořádáte, jak s jejich používáním získáte více zkušeností.

Haldy vs. Zásobníky: Co je odlišuje?

Slyšeli jste o Haldách a Hromádkách, ale kdy byste měli použít jeden přes druhý?

Číst dále

O autorovi