Co je to fronta?
Ocasy jsou datové struktury, které se používají k ukládání a získávání prvků v předem určeném pořadí. Jedná se o lineární datovou strukturu, která se podobá zásobníku a drží se FIFO (první dovnitř, první ven) pravidlo. Lze to přirovnat k čekací listině nebo lince, kde je první osoba, která dorazí, obsluhována jako první. Stávající součásti jsou vypuštěny z přední části fronta a na zadní stranu jsou přidány nové prvky.
Implementace fronty v Golangu
Provádění a fronta in Go je jednoduchý a efektivní a lze jej implementovat pomocí následujících čtyř metod.
1: Plátky
V Go, a plátek je dynamické pole, jehož velikost se může měnit. Pro realizaci a fronta používat plátek , můžeme přidat prvky na zadní stranu plátek pomocí vestavěné funkce připojit a odebrat prvky z přední části plátek pomocí krájení.
Tento přístup se snadno sestavuje a nabízí dobrý výkon pro operace přidávání a dělení díky vestavěným řezům Go. Metoda krájení, která zahrnuje kopírování prvků do nového podkladového pole, se však může stát neefektivní, pokud fronta rozšiřuje a vyžaduje opakované operace vyřazování z fronty.
Následující kód definuje fronta implementace pomocí řezu v Go.
hlavní balíček
import 'fmt'
func main ( ) {
fronta := udělat ( [ ] rozhraní { } , 0 )
fronta = připojit ( fronta , 'Angličtina' )
fronta = připojit ( fronta , 'Urdu' )
fronta = připojit ( fronta , 'matematika' )
-li jen ( fronta ) > 0 {
položka := fronta [ 0 ]
fronta = fronta [ 1 : ]
fmt. Println ( položka )
}
-li jen ( fronta ) == 0 {
fmt. Println ( 'Fronta je prázdná' )
} jiný {
fmt. Println ( fronta )
}
}
Výše uvedený kód Go používá řez k vytvoření přímého fronta datová struktura. The připojit() funkce se používá k zařazení prvků do fronty fronta slice a k jejich vyřazení z fronty se použije operace slice, která odstraní počáteční prvek. S fmt.Println() , vytiskne se vyřazený prvek. Kód pak používá jen() funkce, která určí, zda je fronta prázdná, a pokud ano, zapíše „ Fronta je prázdný“ pomocí funkce fmt.Println().
Výstup
2: Propojené seznamy
Uzly, které nesou hodnotu a ukazatel na následující uzel v seznamu, tvoří propojený seznam. Se dvěma ukazateli, jedním směřujícím dopředu (hlava) seznamu a druhým dozadu (ocas), můžeme implementovat fronta pomocí propojeného seznamu. Odebrání položky z fronty (zařazení do fronty) zahrnuje odstranění uzlu na začátku seznamu, zatímco přidání položky do fronty (zařazení do fronty) zahrnuje přidání nového uzlu na konec seznamu.
Tato metoda umožňuje efektivní zařazování a vyřazování z fronty, protože je třeba změnit pouze ukazatele hlavy a konce, na rozdíl od řešení založeného na řezech, kde by bylo nutné kopírovat prvky.
Použijte propojený seznam k implementaci a fronta pomocí níže uvedeného kódu:
hlavní balíčekimport 'fmt'
zadejte Uzel strukturovat {
hodnotové rozhraní { }
další * Uzel
}
zadejte Fronta strukturovat {
hlava * Uzel
ocas * Uzel
}
func main ( ) {
fronta := & Fronta { hlava : nula , ocas : nula }
novýUzel := & Uzel { hodnota : 'Angličtina' , další : nula }
fronta. ocas = novýUzel
fronta. hlava = novýUzel
novýUzel = & Uzel { hodnota : 'Urdu' , další : nula }
fronta. ocas . další = novýUzel
fronta. ocas = novýUzel
novýUzel = & Uzel { hodnota : 'matematika' , další : nula }
fronta. ocas . další = novýUzel
fronta. ocas = novýUzel
-li fronta. hlava != nula {
položka := fronta. hlava . hodnota
fronta. hlava = fronta. hlava . další
fmt. Println ( položka )
}
-li fronta. hlava == nula {
fmt. Println ( 'Fronta je prázdná' )
}
}
Struktura Node představuje každou položku ve frontě a obsahuje dvě pole: pole hodnoty pro uložení hodnoty položky a další pole pro odkaz na další položku ve frontě. Struktura fronty využívá vlastnosti hlavy a paty ke sledování přední a zadní části fronty. The ocasu první položka je označena vlastností head, zatímco její poslední položka je označena vlastností tail.
Parametry hlavy a ocasu jsou zpočátku nastaveny na nula když nový fronta je stanovena ve funkci main(). Ukazatele hlavy a ocasu jsou aktualizovány tak, aby byly přidány tři uzly fronta s hodnotami 'angličtina', 'urdu', a „matematiku“. The 'Angličtina' položka je pak “odřazeno” (odstraněno) z přední části fronta zobrazením jeho hodnoty a posunutím ukazatele hlavy na následující uzel v fronta . Pokud se po vyřazení z fronty stane hlavička nulová, znamená to, že fronta je prázdná a zobrazí se zpráva „ Fronta je vytištěno“.
Výstup
3: Struktury
V Go můžete vytvořit vlastní datovou strukturu s názvem a strukturovat zastupovat a fronta . Tento strukturovat může mít pole pro uložení fronta prvky a metody pro přidání a odebrání položek, kontrolu, zda je fronta prázdná, a získání aktuální velikosti fronty.
Tento způsob vytváření a fronta in Go nabízí pohodlnou a zapouzdřenou implementaci se snadno použitelnými metodami, které lze rozšířit a přizpůsobit o další funkce. Jedná se o flexibilní přístup, který umožňuje provádět změny v implementaci nebo přidávat nové funkce, kdykoli je to potřeba.
Vytvoření zakázky strukturovat s metodami zahrnuje psaní dalšího kódu ve srovnání s ostatními dvěma způsoby, což může zvýšit složitost. Poskytuje však také větší flexibilitu a kontrolu nad implementací fronta .
Následující příklad ukazuje vytvoření datové struktury reprezentující a fronta v Go.
hlavní balíčekimport 'fmt'
zadejte Fronta strukturovat {
položky [ ] rozhraní { }
}
func ( q * Fronta ) Zařadit do fronty ( rozhraní položky { } ) {
q. položky = připojit ( q. položky , položka )
}
func ( q * Fronta ) Dequeue ( ) rozhraní { } {
-li jen ( q. položky ) == 0 {
vrátit se nula
}
položka := q. položky [ 0 ]
q. položky = q. položky [ 1 : ]
vrátit se položka
}
func ( q * Fronta ) Je prázdný ( ) bool {
vrátit se jen ( q. položky ) == 0
}
func ( q * Fronta ) Velikost ( ) int {
vrátit se jen ( q. položky )
}
func main ( ) {
fronta := & Fronta { položky : udělat ( [ ] rozhraní { } , 0 ) }
fronta. Zařadit do fronty ( 'Angličtina' )
fronta. Zařadit do fronty ( 'Urdu' )
fronta. Zařadit do fronty ( 'matematika' )
položka := fronta. Dequeue ( )
fmt. Println ( položka )
-li fronta. Je prázdný ( ) {
fmt. Println ( 'Fronta je prázdná' )
}
velikost := fronta. Velikost ( )
fmt. Println ( 'Velikost fronty:' , velikost )
}
Ve výše uvedeném kódu je položka připojena k řezu položky prostřednictvím Zařadit do fronty() metoda, která jej přesune na konec fronta . V návaznosti na První dovnitř, první ven (FIFO) princip, Dequeue() metoda vyjme položku z přední části fronta a vrátí to. Délka řezu položky se kontroluje jako součást Je prázdný() metoda je zkontrolovat, zda fronta je prázdný. Vrácením délky řezu položek, Velikost() metoda vrací proud ocasu velikost.
Funkce main() používá Struktura fronty vytvořit nový fronta , přidat do něj prvky, odebrat z něj položky, určit, zda fronta je prázdný a vypočítejte jeho velikost.
Výstup
4: Kanály
V Go lze vestavěný typ kanálu použít k implementaci a fronta datová struktura. Kanál lze vytvořit s velikostí vyrovnávací paměti, aby se omezil počet prvků, které lze v daném okamžiku zařadit do fronty. Chcete-li přidat prvek do fronta , lze jej odeslat do kanálu pomocí <- operátor, zatímco pro odstranění prvku z fronty jej lze přijmout z kanálu pomocí stejného operátora.
Tento přístup může být docela užitečný v situacích, kdy souběžný přístup k fronta je vyžadován, protože kanály jsou ze své podstaty bezpečné pro souběžné použití.
Je důležité mít na paměti, že kanály Go jsou zadány. To znamená, že prostřednictvím kanálu můžete odesílat pouze hodnoty určitého typu a z kanálu můžete přijímat pouze hodnoty stejného typu.
Toto je ilustrace toho, jak použít kanál ke konstrukci a fronta datová struktura v Go.
hlavní balíčekimport (
'fmt'
'čas'
)
zadejte Fronta strukturovat {
kanálové rozhraní položek { }
}
funcNewQueue ( ) * Fronta {
q := & Fronta {
položky : udělat ( rozhraní chan { } ) ,
}
jít q. processItems ( )
vrátit se q
}
func ( q * Fronta ) processItems ( ) {
pro položka := rozsah q. položky {
-li položka == 'Angličtina' {
fmt. Println ( 'Vyřazeno z fronty:' , položka )
}
}
}
func ( q * Fronta ) Zařadit do fronty ( rozhraní položky { } ) {
q. položky <- položka
}
funcmain ( ) {
fronta := NewQueue ( )
fronta. Zařadit do fronty ( 'Angličtina' )
fronta. Zařadit do fronty ( 'Urdu' )
fronta. Zařadit do fronty ( 'matematika' )
čas . Spát ( 2 * čas . Druhý )
}
Výše uvedený kód vytváří a Struktura fronty s jediným polem položky což je kanál rozhraní{} typ. The NewQueue() funkce vytvoří novou instanci Fronta a inicializuje jej 'položky' pole s novým kanálem bez vyrovnávací paměti. Spustí také novou rutinu pro zpracování položek přidaných do fronty pomocí processItems() funkce. The processItems() funkce zkontroluje, zda se přijatá položka rovná 'Angličtina' a vytiskne zprávu do konzole pouze pro tuto položku. The Zařadit do fronty() funkce se používá k přidávání nových položek do fronty.
Výstup
Závěr
Fronta je základní datová struktura v Go, která se používá k ukládání a načítání prvků v určitém pořadí. Provádění a fronta in Go je bezpečný pro vlákna, takže je ideální volbou pro implementaci souběžnosti v programech. Lze jej implementovat pomocí řezů, propojených seznamů, struktur a kanálů. Veškeré podrobnosti jsou již uvedeny ve výše uvedených pokynech.