Čo je to front?
Chvosty sú dátové štruktúry, ktoré sa používajú na ukladanie a získavanie prvkov vo vopred určenom poradí. Ide o lineárnu dátovú štruktúru, ktorá sa podobá zásobníku a dodržiava FIFO (prvý dnu, prvý von) pravidlo. Možno to prirovnať k čakacej listine alebo k radu, kde je prvá osoba, ktorá príde, obsluhovaná ako prvá. Existujúce komponenty sú vypustené z prednej časti fronte , a na zadnej strane sú pridané nové prvky.
Implementácia frontu v Golangu
Realizácia a fronte in Go je jednoduchý a efektívny a možno ho implementovať pomocou nasledujúcich štyroch metód.
1: Plátky
V Go, a plátok je dynamické pole, ktorého veľkosť sa môže meniť. Na realizáciu a fronte pomocou a plátok , môžeme pridať prvky na zadnú stranu plátok pomocou vstavanej funkcie pripojiť a odstrániť prvky z prednej časti plátok pomocou krájania.
Tento prístup sa dá ľahko zostaviť a vďaka vstavaným rezom Go ponúka dobrý výkon pri operáciách pridávania a krájania. Metóda krájania, ktorá zahŕňa kopírovanie prvkov do nového základného poľa, sa však môže stať neefektívnou, ak fronte rozširuje a vyžaduje opakované operácie vyraďovania z radu.
Nasledujúci kód definuje fronte implementácia pomocou rezu v Go.
hlavný balík
importovať 'fmt'
func main ( ) {
fronte := urobiť ( [ ] rozhranie { } , 0 )
fronte = priložiť ( fronte , 'Angličtina' )
fronte = priložiť ( fronte , 'urdu' )
fronte = priložiť ( fronte , 'matematika' )
ak len ( fronte ) > 0 {
položka := fronte [ 0 ]
fronte = fronte [ 1 : ]
fmt. Println ( položka )
}
ak len ( fronte ) == 0 {
fmt. Println ( 'Zoznam je prázdny' )
} inak {
fmt. Println ( fronte )
}
}
Vyššie uvedený kód Go používa rez na vytvorenie jednoduchého fronte dátová štruktúra. The pripojiť () funkcia sa používa na radenie prvkov do fronte rez a operácia rezu, ktorá odstráni počiatočný prvok, sa použije na ich vyradenie z radu. s fmt.Println() , vytlačí sa vyradený prvok. Kód potom používa len() funkcia na určenie, či je front prázdny, a ak áno, zapíše „ Fronta je prázdny“ pomocou funkcie fmt.Println().
Výkon
2: Prepojené zoznamy
Uzly, ktoré nesú hodnotu a ukazovateľ na nasledujúci uzol v zozname, tvoria prepojený zoznam. Pomocou dvoch ukazovateľov, z ktorých jeden ukazuje dopredu (hlava) zoznamu a druhý dozadu (chvost), môžeme implementovať fronte pomocou prepojeného zoznamu. Odstránenie položky z frontu (zaradenie do frontu) zahŕňa odstránenie uzla na začiatku zoznamu, zatiaľ čo pridanie položky do frontu (zaradenie do frontu) zahŕňa pridanie nového uzla na koniec zoznamu.
Táto metóda umožňuje efektívne operácie zaraďovania a vyraďovania z radu, pretože je potrebné zmeniť iba ukazovatele hlavy a konca, na rozdiel od riešenia založeného na segmentoch, kde by bolo potrebné kopírovať prvky.
Použite prepojený zoznam na implementáciu a fronte pomocou nižšie uvedeného kódu:
hlavný balíkimportovať 'fmt'
zadajte Uzol štrukturovať {
hodnotové rozhranie { }
Ďalšie * Uzol
}
zadajte Front štrukturovať {
hlavu * Uzol
chvost * Uzol
}
func main ( ) {
fronte := & Fronta { hlavu : nula , chvost : nula }
newNode := & Uzol { hodnotu : 'Angličtina' , Ďalšie : nula }
fronte. chvost = newNode
fronte. hlavu = newNode
newNode = & Uzol { hodnotu : 'urdu' , Ďalšie : nula }
fronte. chvost . Ďalšie = newNode
fronte. chvost = newNode
newNode = & Uzol { hodnotu : 'matematika' , Ďalšie : nula }
fronte. chvost . Ďalšie = newNode
fronte. chvost = newNode
ak fronte. hlavu != nula {
položka := fronte. hlavu . hodnotu
fronte. hlavu = fronte. hlavu . Ďalšie
fmt. Println ( položka )
}
ak fronte. hlavu == nula {
fmt. Println ( 'Zoznam je prázdny' )
}
}
Štruktúra uzla predstavuje každú položku vo fronte a obsahuje dve polia: pole hodnoty na uloženie hodnoty položky a ďalšie pole na ukazovanie na ďalšiu položku vo fronte. Štruktúra frontu využíva vlastnosti hlavy a chvosta na sledovanie prednej a zadnej časti frontu. The chvost prvá položka je označená vlastnosťou head, zatiaľ čo jej posledná položka je označená vlastnosťou chvosta.
Parametre hlavy a chvosta sú pôvodne nastavené na nula keď nový fronte je stanovená vo funkcii main(). Ukazovatele hlavy a chvosta sa aktualizujú tak, aby do systému pridali tri uzly fronte s hodnotami 'angličtina', 'urdu', a 'matematika'. The 'Angličtina' položka je potom 'odradené' (odstránené) z prednej časti fronte zobrazením jeho hodnoty a posunutím ukazovateľa hlavy na nasledujúci uzol v fronte . Ak sa po vyradení z radu stane hlavička nulová, znamená to, že rad je prázdny a zobrazí sa správa „ Fronta je prázdne“.
Výkon
3: Štruktúry
V Go môžete vytvoriť vlastnú dátovú štruktúru s názvom a štrukturovať zastupovať a fronte . Toto štrukturovať môže mať polia na uloženie fronte prvky a metódy na pridávanie a odstraňovanie položiek, kontrola, či je front prázdny, a získanie aktuálnej veľkosti frontu.
Tento spôsob vytvárania a fronte in Go ponúka pohodlnú a zapuzdrenú implementáciu s ľahko použiteľnými metódami, ktoré možno rozšíriť a prispôsobiť o ďalšie funkcie. Je to flexibilný prístup, ktorý umožňuje vykonať zmeny v implementácii alebo pridať nové schopnosti, kedykoľvek je to potrebné.
Vytvorenie zvyku štrukturovať s metódami zahŕňa písanie dodatočného kódu v porovnaní s ostatnými dvoma spôsobmi, čo môže zvýšiť zložitosť. Poskytuje však aj väčšiu flexibilitu a kontrolu nad implementáciou fronte .
Nasledujúci príklad ukazuje vytvorenie dátovej štruktúry reprezentujúcej a fronte v Go.
hlavný balíkimportovať 'fmt'
zadajte Front štrukturovať {
položky [ ] rozhranie { }
}
func ( q * Fronta ) Zaradiť do radu ( rozhranie položky { } ) {
q. položky = priložiť ( q. položky , položka )
}
func ( q * Fronta ) Dequeue ( ) rozhranie { } {
ak len ( q. položky ) == 0 {
vrátiť nula
}
položka := q. položky [ 0 ]
q. položky = q. položky [ 1 : ]
vrátiť položka
}
func ( q * Fronta ) Je prázdny ( ) bool {
vrátiť len ( q. položky ) == 0
}
func ( q * Fronta ) Veľkosť ( ) int {
vrátiť len ( q. položky )
}
func main ( ) {
fronte := & Fronta { položky : urobiť ( [ ] rozhranie { } , 0 ) }
fronte. Zaradiť do radu ( 'Angličtina' )
fronte. Zaradiť do radu ( 'urdu' )
fronte. Zaradiť do radu ( 'matematika' )
položka := fronte. Dequeue ( )
fmt. Println ( položka )
ak fronte. Je prázdny ( ) {
fmt. Println ( 'Zoznam je prázdny' )
}
veľkosť := fronte. Veľkosť ( )
fmt. Println ( 'Veľkosť frontu:' , veľkosť )
}
Vo vyššie uvedenom kóde je položka pripojená k časti položky cez Zaradiť () metóda, ktorá ho presunie na koniec fronte . Nasleduj Prvý dnu, prvý von (FIFO) princíp, Dequeue() metóda vyberie položku z prednej časti fronte a vráti to. Dĺžka časti položky sa kontroluje ako súčasť Je prázdny() metóda overí, či je fronte je prázdny. Vrátením dĺžky časti položky, Veľkosť () metóda vracia prúd chvost veľkosť.
Funkcia main() používa Štruktúra frontu na vytvorenie nového fronte , pridávať do nej prvky, odstraňovať z nej položky, určiť, či je fronte je prázdny a vypočítajte jeho veľkosť.
Výkon
4: Kanály
V Go možno vstavaný typ kanála použiť na implementáciu a fronte dátová štruktúra. Kanál môže byť vytvorený s veľkosťou vyrovnávacej pamäte, aby sa obmedzil počet prvkov, ktoré môžu byť v danom čase zaradené do frontu. Ak chcete pridať prvok do fronte , môžete ho odoslať na kanál pomocou <- operátor, zatiaľ čo na odstránenie prvku z frontu ho možno prijať z kanála pomocou rovnakého operátora.
Tento prístup môže byť celkom užitočný v situáciách, keď súbežný prístup k fronte je potrebné, pretože kanály sú vo svojej podstate bezpečné pri súbežnom používaní.
Je dôležité si zapamätať, že kanály Go sú zadané. To znamená, že cez kanál môžete odosielať iba hodnoty určitého typu a z kanála môžete prijímať iba hodnoty toho istého typu.
Toto je ilustrácia toho, ako použiť kanál na vytvorenie a fronte dátovú štruktúru v Go.
hlavný balíkimportovať (
'fmt'
'čas'
)
zadajte Front štrukturovať {
kanálové rozhranie položiek { }
}
funcNewQueue ( ) * Fronta {
q := & Fronta {
položky : urobiť ( rozhranie chan { } ) ,
}
ísť q. processItems ( )
vrátiť q
}
func ( q * Fronta ) processItems ( ) {
pre položka := rozsah q. položky {
ak položka == 'Angličtina' {
fmt. Println ( 'Vyradené z frontu:' , položka )
}
}
}
func ( q * Fronta ) Zaradiť do radu ( rozhranie položky { } ) {
q. položky <- položka
}
funcmain ( ) {
fronte := NewQueue ( )
fronte. Zaradiť do radu ( 'Angličtina' )
fronte. Zaradiť do radu ( 'urdu' )
fronte. Zaradiť do radu ( 'matematika' )
čas . Spánok ( 2 * čas . Po druhé )
}
Vyššie uvedený kód vytvára a Štruktúra frontu s jediným poľom položky ktorý je kanálom rozhranie{} typu. The NewQueue() funkcia vytvorí novú inštanciu Fronta a inicializuje ho 'položky' pole s novým kanálom bez vyrovnávacej pamäte. Spustí tiež novú rutinu na spracovanie položiek pridaných do frontu pomocou processItems() funkciu. The processItems() funkcia skontroluje, či sa prijatá položka rovná 'Angličtina' a vytlačí správu do konzoly iba pre túto položku. The Zaradiť () funkcia sa používa na pridávanie nových položiek do frontu.
Výkon
Záver
Front je základná dátová štruktúra v Go, ktorá sa používa na ukladanie a získavanie prvkov v špecifickom poradí. Realizácia a fronte in Go je bezpečný pre vlákna, vďaka čomu je ideálnou voľbou na implementáciu súbežnosti v programoch. Dá sa implementovať pomocou rezov, prepojených zoznamov, štruktúr a kanálov. Všetky podrobnosti sú už uvedené vo vyššie uvedených pokynoch.