Hva er en kø?
Haler er datastrukturer som brukes til å lagre og hente elementer i en forhåndsbestemt rekkefølge. Det er en lineær datastruktur som ligner en stabel og holder seg til FIFO (først inn, først ut) regel. Det kan sammenlignes med en venteliste eller en kø hvor den første som ankommer blir betjent først. Eksisterende komponenter slippes fra forsiden av kø , og nye elementer legges til på baksiden.
Implementering av en kø i Golang
Gjennomføringen av en kø in Go er enkelt og effektivt og kan implementeres ved hjelp av følgende fire metoder.
1: Skiver
I Go, a skive er en dynamisk matrise som kan endre seg i størrelse. Å implementere en kø bruker en skive , kan vi legge til elementer på baksiden av skive ved å bruke den innebygde append-funksjonen og fjerne elementer fra forsiden av skive ved hjelp av skjæring.
Denne tilnærmingen er enkel å bygge og gir god ytelse for tilføynings- og skjæreoperasjoner takket være Gos innebygde skiver. Imidlertid kan skjæringsmetoden, som inkluderer kopiering av elementer til en ny underliggende matrise bli ineffektiv hvis kø utvider og nødvendiggjør gjentatte dekøoperasjoner.
Følgende kode definerer kø implementering ved hjelp av et stykke i Go.
hovedpakke
import 'fmt'
func main ( ) {
kø := gjøre ( [ ] grensesnitt { } , 0 )
kø = legge til ( kø , 'Engelsk' )
kø = legge til ( kø , 'urdu' )
kø = legge til ( kø , 'matte' )
hvis bare ( kø ) > 0 {
punkt := kø [ 0 ]
kø = kø [ 1 : ]
fmt. Println ( punkt )
}
hvis bare ( kø ) == 0 {
fmt. Println ( 'Køen er tom' )
} ellers {
fmt. Println ( kø )
}
}
Go-koden ovenfor bruker en skive for å konstruere en enkel kø data struktur. De legge til() funksjonen brukes til å sette elementer i kø i kø skive, og en skiveoperasjon som fjerner det første elementet brukes til å sette dem i kø. Med fmt.Println() , skrives elementet ut av kø. Koden bruker deretter bare() funksjon for å finne ut om køen er tom, og hvis den er det, skriver den ' Kø er tom' ved å bruke funksjonen fmt.Println().
Produksjon
2: Koblede lister
Noder som har en verdi og en peker til følgende node i listen utgjør en koblet liste. Med to pekere, en som peker foran (hodet) av listen og den andre peker bakover (hale), kan vi implementere en kø ved hjelp av en koblet liste. Å fjerne et element fra køen (fra kø) innebærer å fjerne noden foran på listen, mens å legge til et element i køen (kø) innebærer å legge til en ny node bak på listen.
Denne metoden muliggjør effektiv kø- og fjerning av kø fordi bare hode- og halepekerne må endres, i motsetning til den skivebaserte løsningen der elementer må kopieres.
Bruk en koblet liste for å implementere en kø ved å bruke koden nedenfor:
hovedpakkeimport 'fmt'
type Node struktur {
verdi grensesnitt { }
neste * Node
}
skriv inn kø struktur {
hode * Node
hale * Node
}
func main ( ) {
kø := & Kø { hode : null , hale : null }
nyNode := & Node { verdi : 'Engelsk' , neste : null }
kø. hale = nyNode
kø. hode = nyNode
nyNode = & Node { verdi : 'urdu' , neste : null }
kø. hale . neste = nyNode
kø. hale = nyNode
nyNode = & Node { verdi : 'matte' , neste : null }
kø. hale . neste = nyNode
kø. hale = nyNode
hvis kø. hode != null {
punkt := kø. hode . verdi
kø. hode = kø. hode . neste
fmt. Println ( punkt )
}
hvis kø. hode == null {
fmt. Println ( 'Køen er tom' )
}
}
Nodestrukturen representerer hvert element i køen og inneholder to felt: et verdifelt for å lagre elementets verdi, og det neste feltet for å peke til neste element i køen. Køstrukturen bruker hode- og haleegenskaper for å holde styr på henholdsvis foran og bak i køen. De halens første element er indikert med hodeegenskapen, mens det siste elementet er indikert med haleegenskapen.
Hode- og haleparametrene er i utgangspunktet satt til null når en ny kø er etablert i hoved()-funksjonen. Hode- og halepekerne oppdateres for å legge til tre noder til kø med verdiene 'engelsk', 'urdu', og 'matte'. De 'Engelsk' varen er da 'fra kø' (fjernet) fra forsiden av kø ved å vise verdien og flytte hodepekeren til følgende node i kø . Etter fjerning av kø, hvis hodet blir null, betyr det at køen er tom, og meldingen ' Kø er tom” skrives ut.
Produksjon
3: Strukturer
I Go kan du lage en tilpasset datastruktur kalt a struktur å representere en kø . Dette struktur kan ha felt for å lagre kø elementer og metoder for å legge til og fjerne elementer, sjekke om køen er tom, og få gjeldende køstørrelse.
Denne måten å lage en kø in Go tilbyr en praktisk og innkapslet implementering med brukervennlige metoder som kan utvides og tilpasses med flere funksjoner. Det er en fleksibel tilnærming som gjør det mulig å gjøre endringer i implementeringen eller legge til nye funksjoner når det er nødvendig.
Opprette en egendefinert struktur med metoder innebærer å skrive tilleggskode sammenlignet med de to andre måtene, noe som kan øke kompleksiteten. Det gir imidlertid også mer fleksibilitet og kontroll over implementeringen av kø .
Følgende eksempel viser hvordan du oppretter en datastruktur for å representere en kø i Go.
hovedpakkeimport 'fmt'
skriv inn kø struktur {
gjenstander [ ] grensesnitt { }
}
func ( q * Kø ) Kø ( elementgrensesnitt { } ) {
q. gjenstander = legge til ( q. gjenstander , punkt )
}
func ( q * Kø ) Sett av kø ( ) grensesnitt { } {
hvis bare ( q. gjenstander ) == 0 {
komme tilbake null
}
punkt := q. gjenstander [ 0 ]
q. gjenstander = q. gjenstander [ 1 : ]
komme tilbake punkt
}
func ( q * Kø ) Er tom ( ) bool {
komme tilbake bare ( q. gjenstander ) == 0
}
func ( q * Kø ) Størrelse ( ) int {
komme tilbake bare ( q. gjenstander )
}
func main ( ) {
kø := & Kø { gjenstander : gjøre ( [ ] grensesnitt { } , 0 ) }
kø. Kø ( 'Engelsk' )
kø. Kø ( 'urdu' )
kø. Kø ( 'matte' )
punkt := kø. Sett av kø ( )
fmt. Println ( punkt )
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 koden ovenfor legges et element til elementets stykke via Enqueue() metode, som flytter den til slutten av kø . Følger Først inn, først ut (FIFO) prinsippet, det Dequeue() metoden tar et element ut av forsiden av kø og returnerer den. Lengden på elementets skive kontrolleres som en del av Er tom() metoden sjekk for å se om kø er tom. Ved å returnere lengden på vareskiven, vil den Størrelse() metoden returnerer gjeldende halens størrelse.
Main()-funksjonen bruker Køstruktur å lage en ny kø , legg til elementer i den, fjern elementer fra den, avgjør om kø er tom, og beregn størrelsen.
Produksjon
4: Kanaler
I Go kan den innebygde kanaltypen brukes til å implementere en kø data struktur. Kanalen kan opprettes med en bufferstørrelse for å begrense antall elementer som kan settes i kø til enhver tid. For å legge til et element i kø , kan den sendes til kanalen ved hjelp av <- operatør, mens for å fjerne et element fra køen, kan det mottas fra kanalen med samme operatør.
Denne tilnærmingen kan være ganske nyttig i situasjoner der samtidig tilgang til kø er påkrevd, siden kanaler er iboende trygge for samtidig bruk.
Det er viktig å huske at Go-kanaler er skrevet. Dette betyr at du kun kan sende verdier av en bestemt type gjennom en kanal, og du kan bare motta verdier av samme type fra kanalen.
Dette er en illustrasjon av hvordan man bruker en kanal til å konstruere en kø datastruktur i Go.
hovedpakkeimport (
'fmt'
'tid'
)
skriv inn kø struktur {
elementer kanalgrensesnitt { }
}
funcNewQueue ( ) * Kø {
q := & Kø {
gjenstander : gjøre ( chan-grensesnitt { } ) ,
}
gå q. prosesselementer ( )
komme tilbake q
}
func ( q * Kø ) prosesselementer ( ) {
til punkt := rekkevidde q. gjenstander {
hvis punkt == 'Engelsk' {
fmt. Println ( 'Utsatt kø:' , punkt )
}
}
}
func ( q * Kø ) Kø ( elementgrensesnitt { } ) {
q. gjenstander <- punkt
}
funcmain ( ) {
kø := Nykø ( )
kø. Kø ( 'Engelsk' )
kø. Kø ( 'urdu' )
kø. Kø ( 'matte' )
tid . Sove ( 2 * tid . Sekund )
}
Koden ovenfor oppretter en Køstruktur med ett enkelt felt gjenstander som er en kanal av grensesnitt{} type. De NewQueue() funksjonen oppretter en ny forekomst av Kø og initialiserer den 'varer' felt med en ny ubufret kanal. Den starter også en ny goroutine for å behandle elementene som legges til i køen ved hjelp av processItems() funksjon. De processItems() funksjon sjekker om den mottatte varen er lik 'Engelsk' og skriver ut en melding til konsollen for bare det elementet. De Enqueue() funksjonen brukes til å legge til nye elementer i køen.
Produksjon
Konklusjon
Køen er en viktig datastruktur i Go som brukes til å lagre og hente elementer i en bestemt rekkefølge. Gjennomføringen av en kø in Go er trådsikre, noe som gjør dem til et ideelt valg for implementering av samtidighet i programmer. Det kan implementeres ved hjelp av skiver, koblede lister, strukturer og kanaler. De fullstendige detaljene er allerede gitt i retningslinjene ovenfor.