Wat is een wachtrij?
Staarten zijn gegevensstructuren die worden gebruikt om elementen in een vooraf bepaalde volgorde op te slaan en op te halen. Het is een lineaire gegevensstructuur die lijkt op een stapel en zich houdt aan de FIFO (eerst in, eerst uit) regel. Het kan worden vergeleken met een wachtlijst of een rij waar de eerste persoon die arriveert als eerste wordt geholpen. Bestaande componenten vallen vanaf de voorkant van de wachtrij , en er zijn nieuwe elementen aan de achterkant toegevoegd.
Implementatie van een wachtrij in Golang
De uitvoering van een wachtrij in Go is eenvoudig en efficiënt en kan worden geïmplementeerd met behulp van de volgende vier methoden.
1: plakjes
In Ga, een plak is een dynamische array die in grootte kan veranderen. Implementeren van een wachtrij gebruik maken van een plak , kunnen we elementen toevoegen aan de achterkant van de plak met behulp van de ingebouwde append-functie en verwijder elementen van de voorkant van de plak snijden gebruiken.
Deze aanpak is eenvoudig te bouwen en biedt goede prestaties voor het toevoegen en snijden van bewerkingen dankzij de ingebouwde plakjes van Go. De slicing-methode, waarbij elementen naar een nieuwe onderliggende array worden gekopieerd, kan echter inefficiënt worden als de wachtrij breidt zich uit en maakt herhaalde wachtrijbewerkingen noodzakelijk.
De volgende code definieert de wachtrij implementatie met behulp van een slice in Go.
pakket belangrijkste
importeren 'fmt'
func hoofd ( ) {
wachtrij := maken ( [ ] koppel { } , 0 )
wachtrij = toevoegen ( wachtrij , 'Engels' )
wachtrij = toevoegen ( wachtrij , 'Urdu' )
wachtrij = toevoegen ( wachtrij , 'wiskunde' )
als alleen ( wachtrij ) > 0 {
item := wachtrij [ 0 ]
wachtrij = wachtrij [ 1 : ]
fmt. Println ( item )
}
als alleen ( wachtrij ) == 0 {
fmt. Println ( 'Wachtrij is leeg' )
} anders {
fmt. Println ( wachtrij )
}
}
De bovenstaande Go-code gebruikt een slice om een straight te construeren wachtrij data structuur. De toevoegen() functie wordt gebruikt om elementen in de wachtrij te plaatsen wachtrij slice, en een slice-bewerking die het eerste element verwijdert, wordt gebruikt om ze uit de wachtrij te halen. Met fmt.Println() , wordt het uit de wachtrij verwijderde element afgedrukt. De code gebruikt dan de alleen() functie om te bepalen of de wachtrij leeg is, en als dat zo is, schrijft het ' Wachtrij is leeg” met de functie fmt.Println().
Uitgang
2: gekoppelde lijsten
Knooppunten met een waarde en een verwijzing naar het volgende knooppunt in de lijst vormen een gekoppelde lijst. Met twee aanwijzers, één naar de voorkant (kop) van de lijst en de andere naar de achterkant (staart), kunnen we een wachtrij met behulp van een gekoppelde lijst. Het verwijderen van een item uit de wachtrij (dequeuing) omvat het verwijderen van het knooppunt aan de voorkant van de lijst, terwijl het toevoegen van een item aan de wachtrij (enqueuing) het toevoegen van een nieuw knooppunt aan de achterkant van de lijst inhoudt.
Deze methode maakt efficiënte in- en uitwachtrijen mogelijk, omdat alleen de kop- en staartaanwijzers hoeven te worden gewijzigd, in tegenstelling tot de op segmenten gebaseerde oplossing waarbij elementen moeten worden gekopieerd.
Gebruik een gekoppelde lijst om een wachtrij door onderstaande code te gebruiken:
pakket belangrijksteimporteren 'fmt'
typ Knooppunt structuur {
waarde-interface { }
volgende * Knooppunt
}
typ Wachtrij structuur {
hoofd * Knooppunt
staart * Knooppunt
}
func hoofd ( ) {
wachtrij := & Wachtrij { hoofd : nihil , staart : nihil }
nieuwNode := & Knooppunt { waarde : 'Engels' , volgende : nihil }
wachtrij. staart = nieuwNode
wachtrij. hoofd = nieuwNode
nieuwNode = & Knooppunt { waarde : 'Urdu' , volgende : nihil }
wachtrij. staart . volgende = nieuwNode
wachtrij. staart = nieuwNode
nieuwNode = & Knooppunt { waarde : 'wiskunde' , volgende : nihil }
wachtrij. staart . volgende = nieuwNode
wachtrij. staart = nieuwNode
als wachtrij. hoofd != nihil {
item := wachtrij. hoofd . waarde
wachtrij. hoofd = wachtrij. hoofd . volgende
fmt. Println ( item )
}
als wachtrij. hoofd == nihil {
fmt. Println ( 'Wachtrij is leeg' )
}
}
De Node-structuur vertegenwoordigt elk item in de wachtrij en bevat twee velden: een waardeveld voor het opslaan van de waarde van het item en het volgende veld om naar het volgende item in de wachtrij te verwijzen. De wachtrijstructuur gebruikt kop- en staarteigenschappen om respectievelijk de voor- en achterkant van de wachtrij bij te houden. De staart eerste item wordt aangegeven door de eigenschap head, terwijl het laatste item wordt aangegeven door de eigenschap tail.
De kop- en staartparameters zijn aanvankelijk ingesteld op nihil wanneer een nieuwe wachtrij wordt vastgelegd in de functie main(). De kop- en staartwijzers zijn bijgewerkt om drie knooppunten toe te voegen aan het wachtrij met de waarden 'Engels', 'urdu', En 'wiskunde'. De 'Engels' artikel is dan 'uit de wachtrij gehaald' (verwijderd) van de voorkant van de wachtrij door de waarde ervan weer te geven en de hoofdaanwijzer naar het volgende knooppunt in het wachtrij . Als de kop na het uit de wachtrij plaatsen null wordt, betekent dit dat de wachtrij leeg is en het bericht ' Wachtrij is leeg” wordt afgedrukt.
Uitgang
3: Structuren
In Go kunt u een aangepaste gegevensstructuur maken met de naam a structuur vertegenwoordigen een wachtrij . Dit structuur kan velden hebben om de op te slaan wachtrij elementen en methoden om items toe te voegen en te verwijderen, te controleren of de wachtrij leeg is en de huidige wachtrijgrootte op te halen.
Deze manier van het creëren van een wachtrij in Go biedt een handige en ingekapselde implementatie met gebruiksvriendelijke methoden die kunnen worden uitgebreid en aangepast met meer functies. Het is een flexibele aanpak waarmee wijzigingen in de implementatie kunnen worden aangebracht of nieuwe mogelijkheden kunnen worden toegevoegd wanneer dat nodig is.
Een gewoonte maken structuur met methoden omvat het schrijven van aanvullende code in vergelijking met de andere twee manieren, wat de complexiteit kan vergroten. Het biedt echter ook meer flexibiliteit en controle over de implementatie van de wachtrij .
In het volgende voorbeeld ziet u hoe u een gegevensstructuur maakt om een wachtrij in Gaan.
pakket belangrijksteimporteren 'fmt'
typ Wachtrij structuur {
artikelen [ ] koppel { }
}
func ( Q * Wachtrij ) Wachtrij ( item-interface { } ) {
Q. artikelen = toevoegen ( Q. artikelen , item )
}
func ( Q * Wachtrij ) Wachtrij ( ) koppel { } {
als alleen ( Q. artikelen ) == 0 {
opbrengst nihil
}
item := Q. artikelen [ 0 ]
Q. artikelen = Q. artikelen [ 1 : ]
opbrengst item
}
func ( Q * Wachtrij ) Is leeg ( ) boel {
opbrengst alleen ( Q. artikelen ) == 0
}
func ( Q * Wachtrij ) Maat ( ) int {
opbrengst alleen ( Q. artikelen )
}
func hoofd ( ) {
wachtrij := & Wachtrij { artikelen : maken ( [ ] koppel { } , 0 ) }
wachtrij. Wachtrij ( 'Engels' )
wachtrij. Wachtrij ( 'Urdu' )
wachtrij. Wachtrij ( 'wiskunde' )
item := wachtrij. Wachtrij ( )
fmt. Println ( item )
als wachtrij. Is leeg ( ) {
fmt. Println ( 'Wachtrij is leeg' )
}
maat := wachtrij. Maat ( )
fmt. Println ( 'Grootte van de wachtrij:' , maat )
}
In de bovenstaande code wordt een item toegevoegd aan de slice van het item via de Wachtrij() methode, die het naar het einde van de wachtrij . Volgens de First-in, first-out (FIFO) principe, de Wachtrij() methode haalt een item uit de voorkant van de wachtrij en geeft het terug. De lengte van het segment van het item wordt gecontroleerd als onderdeel van de Is leeg() methode om te zien of de wachtrij is leeg. Door de lengte van het itemsegment te retourneren, wordt de Maat() methode retourneert de stroom staart maat.
De functie main() gebruikt de Wachtrij structuur om een nieuwe te creëren wachtrij , voeg er elementen aan toe, verwijder er items uit, bepaal of de wachtrij is leeg en bereken de grootte.
Uitgang
4: Kanalen
In Go kan het ingebouwde kanaaltype worden gebruikt om een wachtrij data structuur. Het kanaal kan worden gemaakt met een buffergrootte om het aantal elementen te beperken dat op een bepaald moment in de wachtrij kan worden geplaatst. Om een element toe te voegen aan de wachtrij , kan het naar het kanaal worden verzonden met behulp van de <- operator, terwijl om een element uit de wachtrij te verwijderen, het met dezelfde operator van het kanaal kan worden ontvangen.
Deze aanpak kan heel nuttig zijn in situaties waarin gelijktijdige toegang tot de wachtrij is vereist, aangezien kanalen inherent veilig zijn voor gelijktijdig gebruik.
Het is cruciaal om te onthouden dat Go-kanalen getypt zijn. Dit betekent dat u alleen waarden van een bepaald type via een kanaal kunt verzenden en dat u alleen waarden van datzelfde type van het kanaal kunt ontvangen.
Dit is een illustratie van hoe je een kanaal gebruikt om een wachtrij gegevensstructuur in Go.
pakket belangrijksteimporteren (
'fmt'
'tijd'
)
typ Wachtrij structuur {
items chaninterface { }
}
funcNewQueue ( ) * Wachtrij {
Q := & Wachtrij {
artikelen : maken ( chan-interface { } ) ,
}
ga q. procesItems ( )
opbrengst Q
}
func ( Q * Wachtrij ) procesItems ( ) {
voor item := bereik q. artikelen {
als item == 'Engels' {
fmt. Println ( 'Uit wachtrij:' , item )
}
}
}
func ( Q * Wachtrij ) Wachtrij ( item-interface { } ) {
Q. artikelen <- item
}
functie ( ) {
wachtrij := Nieuwe wachtrij ( )
wachtrij. Wachtrij ( 'Engels' )
wachtrij. Wachtrij ( 'Urdu' )
wachtrij. Wachtrij ( 'wiskunde' )
tijd . Slaap ( 2 * tijd . Seconde )
}
De bovenstaande code maakt een Wachtrij structuur met een enkel veld artikelen dat is een kanaal van koppel{} type. De nieuwewachtrij() functie maakt een nieuw exemplaar van de Wachtrij en initialiseert zijn 'items' veld met een nieuw ongebufferd kanaal. Het start ook een nieuwe goroutine om de items die aan de wachtrij zijn toegevoegd te verwerken met behulp van de procesItems() functie. De procesItems() functie controleert of het ontvangen item gelijk is aan 'Engels' en drukt alleen voor dat item een bericht af naar de console. De Wachtrij() functie wordt gebruikt om nieuwe items aan de wachtrij toe te voegen.
Uitgang
Conclusie
De wachtrij is een essentiële gegevensstructuur in Go die wordt gebruikt om elementen in een specifieke volgorde op te slaan en op te halen. De uitvoering van een wachtrij in Go is thread-safe, waardoor ze een ideale keuze zijn voor het implementeren van gelijktijdigheid in programma's. Het kan worden geïmplementeerd met behulp van segmenten, gekoppelde lijsten, structuren en kanalen. De volledige details zijn al gegeven in de hierboven gegeven richtlijnen.