Hvad er en kø?
Haler er datastrukturer, der bruges til at lagre og hente elementer i en forudbestemt rækkefølge. Det er en lineær datastruktur, der ligner en stak og overholder FIFO (først ind, først ud) Herske. Det kan sammenlignes med en venteliste eller en kø, hvor den først ankommer serviceres først. Eksisterende komponenter tabes fra forsiden af kø , og nye elementer tilføjes på bagsiden.
Implementering af en kø i Golang
Implementeringen af en kø in Go er enkel og effektiv og kan implementeres ved hjælp af følgende fire metoder.
1: Skiver
I Go, en skive er et dynamisk array, der kan ændre sig i størrelse. At implementere en kø ved hjælp af en skive , kan vi tilføje elementer på bagsiden af skive ved hjælp af den indbyggede append-funktion og fjern elementer fra forsiden af skive ved hjælp af udskæring.
Denne tilgang er nem at bygge og giver god ydeevne til tilføjelse og udskæring takket være Go's indbyggede skiver. Udskæringsmetoden, som inkluderer kopiering af elementer til et nyt underliggende array, kan dog blive ineffektivt, hvis kø udvider og nødvendiggør gentagne dekø-operationer.
Følgende kode definerer kø implementering ved hjælp af et udsnit i Go.
hovedpakke
importere 'fmt'
func hoved ( ) {
kø := lave ( [ ] interface { } , 0 )
kø = Tilføj ( kø , 'engelsk' )
kø = Tilføj ( kø , 'urdu' )
kø = Tilføj ( kø , 'matematik' )
hvis kun ( kø ) > 0 {
vare := kø [ 0 ]
kø = kø [ 1 : ]
fmt. Udskrivln ( vare )
}
hvis kun ( kø ) == 0 {
fmt. Udskrivln ( 'Køen er tom' )
} andet {
fmt. Udskrivln ( kø )
}
}
Ovenstående Go-kode bruger et udsnit til at konstruere en ligetil kø datastruktur. Det Tilføj() funktionen bruges til at sætte elementer i kø i kø skive, og en skiveoperation, der fjerner det oprindelige element, bruges til at sætte dem i kø. Med fmt.Println() , udskrives elementet i kø. Koden bruger derefter kun() funktion til at bestemme, om køen er tom, og hvis den er, skriver den ' Kø er tom' ved hjælp af fmt.Println()-funktionen.
Produktion
2: Sammenkædede lister
Noder, der bærer en værdi og en pointer til den følgende node på listen, udgør en sammenkædet liste. Med to peger, den ene peger mod forsiden (hovedet) af listen og den anden peger bagud (halen), kan vi implementere en kø ved hjælp af en linket liste. Fjernelse af et element fra køen (afkø) involverer at fjerne noden foran på listen, mens tilføjelse af et element til køen (kø) involverer tilføjelse af en ny node bagerst på listen.
Denne metode giver mulighed for effektiv kø- og dekø-operationer, fordi kun hoved- og halepegerne skal ændres, i modsætning til den skivebaserede løsning, hvor elementer skal kopieres.
Brug en linket liste til at implementere en kø ved at bruge den medfølgende kode nedenfor:
hovedpakkeimportere 'fmt'
type Node struktur {
værdi grænseflade { }
Næste * Node
}
skriv Kø struktur {
hoved * Node
hale * Node
}
func hoved ( ) {
kø := & Kø { hoved : nul , hale : nul }
nyNode := & Node { værdi : 'engelsk' , Næste : nul }
kø. hale = nyNode
kø. hoved = nyNode
nyNode = & Node { værdi : 'urdu' , Næste : nul }
kø. hale . Næste = nyNode
kø. hale = nyNode
nyNode = & Node { værdi : 'matematik' , Næste : nul }
kø. hale . Næste = nyNode
kø. hale = nyNode
hvis kø. hoved != nul {
vare := kø. hoved . værdi
kø. hoved = kø. hoved . Næste
fmt. Println ( vare )
}
hvis kø. hoved == nul {
fmt. Udskrivln ( 'Køen er tom' )
}
}
Node-strukturen repræsenterer hvert element i køen og indeholder to felter: et værdifelt til lagring af elementets værdi og det næste felt til at pege på det næste element i køen. Køstrukturen bruger hoved- og haleegenskaber til at holde styr på henholdsvis for- og bagkanten af køen. Det halens første element er angivet med hovedegenskaben, mens dets sidste element er angivet med haleegenskaben.
Hoved- og haleparametrene er oprindeligt indstillet til nul når en ny kø er etableret i main()-funktionen. Hoved- og halemarkørerne opdateres for at tilføje tre noder til kø med værdierne 'engelsk', 'urdu', og 'matematik'. Det 'engelsk' varen er derefter 'fra kø' (fjernet) fra forsiden af kø ved at vise dens værdi og føre hovedmarkøren frem til den følgende node i kø . Efter fjernelse af kø, hvis hovedet bliver nul, betyder det, at køen er tom, og meddelelsen ' Kø er tom” udskrives.
Produktion
3: Strukturer
I Go kan du oprette en tilpasset datastruktur kaldet a struktur at repræsentere en kø . Det her struktur kan have felter til at gemme kø elementer og metoder til at tilføje og fjerne elementer, kontrollere, om køen er tom, og få den aktuelle køstørrelse.
Denne måde at skabe en kø in Go tilbyder en praktisk og indkapslet implementering med brugervenlige metoder, der kan udvides og tilpasses med flere funktioner. Det er en fleksibel tilgang, der gør det muligt at foretage ændringer i implementeringen eller tilføje nye muligheder, når det er nødvendigt.
Oprettelse af en brugerdefineret struktur med metoder involverer at skrive yderligere kode sammenlignet med de to andre måder, hvilket kan øge kompleksiteten. Det giver dog også mere fleksibilitet og kontrol over implementeringen af kø .
Følgende eksempel viser oprettelse af en datastruktur til at repræsentere en kø i Go.
hovedpakkeimportere 'fmt'
skriv Kø struktur {
genstande [ ] interface { }
}
func ( q * Kø ) Kø ( element interface { } ) {
q. genstande = Tilføj ( q. genstande , vare )
}
func ( q * Kø ) Afkø ( ) interface { } {
hvis kun ( q. genstande ) == 0 {
Vend tilbage nul
}
vare := q. genstande [ 0 ]
q. genstande = q. genstande [ 1 : ]
Vend tilbage vare
}
func ( q * Kø ) Er tom ( ) bool {
Vend tilbage kun ( q. genstande ) == 0
}
func ( q * Kø ) Størrelse ( ) int {
Vend tilbage kun ( q. genstande )
}
func hoved ( ) {
kø := & Kø { genstande : lave ( [ ] interface { } , 0 ) }
kø. Kø ( 'engelsk' )
kø. Kø ( 'urdu' )
kø. Kø ( 'matematik' )
vare := kø. Afkø ( )
fmt. Println ( vare )
hvis kø. Er tom ( ) {
fmt. Println ( 'Køen er tom' )
}
størrelse := kø. Størrelse ( )
fmt. Println ( 'Størrelse på køen:' , størrelse )
}
I ovenstående kode tilføjes en vare til varens udsnit via Enqueue() metode, som flytter den til slutningen af kø . Efter Først ind, først ud (FIFO) princip, den Dequeue() metoden tager et emne ud af forsiden af kø og returnerer den. Længden af varens udsnit kontrolleres som en del af Er tom() metodens tjek for at se, om kø er tom. Ved at returnere længden af emnerne skive, den Størrelse() metode returnerer den aktuelle halens størrelse.
Main()-funktionen bruger Køstruktur at oprette en ny kø , tilføje elementer til det, fjerne elementer fra det, afgøre, om kø er tom, og beregn dens størrelse.
Produktion
4: Kanaler
I Go kan den indbyggede kanaltype bruges til at implementere en kø datastruktur. Kanalen kan oprettes med en bufferstørrelse for at begrænse antallet af elementer, der kan stilles i kø på et givet tidspunkt. For at tilføje et element til kø , kan den sendes til kanalen ved hjælp af <- operatør, mens for at fjerne et element fra køen, kan det modtages fra kanalen med den samme operatør.
Denne tilgang kan være ganske nyttig i situationer, hvor samtidig adgang til kø er påkrævet, da kanaler i sagens natur er sikre til samtidig brug.
Det er afgørende at huske, at Go-kanaler er indtastet. Det betyder, at du kun kan sende værdier af en bestemt type gennem en kanal, og du kan kun modtage værdier af samme type fra kanalen.
Dette er en illustration af, hvordan man bruger en kanal til at konstruere en kø datastruktur i Go.
hovedpakkeimportere (
'fmt'
'tid'
)
skriv Kø struktur {
emner chaninterface { }
}
funcNewQueue ( ) * Kø {
q := & Kø {
genstande : lave ( chan interface { } ) ,
}
gå q. proceselementer ( )
Vend tilbage q
}
func ( q * Kø ) proceselementer ( ) {
til vare := rækkevidde q. genstande {
hvis vare == 'engelsk' {
fmt. Println ( 'Udsat kø:' , vare )
}
}
}
func ( q * Kø ) Kø ( element interface { } ) {
q. genstande <- vare
}
funcmain ( ) {
kø := Ny Kø ( )
kø. Kø ( 'engelsk' )
kø. Kø ( 'urdu' )
kø. Kø ( 'matematik' )
tid . Søvn ( 2 * tid . Anden )
}
Ovenstående kode skaber en Køstruktur med et enkelt felt genstande som er en kanal af grænseflade{} type. Det NewQueue() funktionen opretter en ny forekomst af Kø og initialiserer dens 'genstande' felt med en ny ikke-bufferet kanal. Det starter også en ny goroutine til at behandle de elementer, der er tilføjet til køen ved hjælp af processItems() fungere. Det processItems() funktion kontrollerer om den modtagne vare er lig med 'engelsk' og udskriver kun en besked til konsollen for det element. Det Enqueue() funktionen bruges til at tilføje nye varer til køen.
Produktion
Konklusion
Køen er en væsentlig datastruktur i Go, der bruges til at gemme og hente elementer i en bestemt rækkefølge. Implementeringen af en kø in Go er trådsikre, hvilket gør dem til et ideelt valg til implementering af samtidighed i programmer. Det kan implementeres ved hjælp af udsnit, sammenkædede lister, strukturer og kanaler. De fulde detaljer er allerede angivet i de ovenfor givne retningslinjer.