Ano ang isang Queue?
Mga buntot ay mga istruktura ng data na ginagamit upang mag-imbak at kumuha ng mga elemento sa isang paunang natukoy na pagkakasunud-sunod. Ito ay isang linear na istraktura ng data na kahawig ng isang stack at sumusunod sa FIFO (First-In, First-Out) tuntunin. Ito ay maaaring ihambing sa isang listahan ng naghihintay o isang linya kung saan ang unang taong dumating ay unang nagseserbisyo. Ang mga kasalukuyang bahagi ay ibinabagsak mula sa harap ng pila , at ang mga bagong elemento ay idinagdag sa likod.
Pagpapatupad ng isang Queue sa Golang
Ang pagpapatupad ng a pila sa Go ay simple at mahusay at maaaring ipatupad gamit ang sumusunod na apat na pamamaraan.
1: Mga hiwa
Sa Go, a hiwain ay isang dynamic na array na maaaring magbago sa laki. Upang ipatupad ang a pila gamit ang hiwain , maaari tayong magdagdag ng mga elemento sa likod ng hiwain gamit ang built-in na append function at alisin ang mga elemento mula sa harap ng hiwain gamit ang paghiwa.
Ang diskarte na ito ay madaling gawin at nag-aalok ng mahusay na pagganap para sa pagsasama at paghiwa ng mga operasyon salamat sa mga built-in na slice ni Go. Gayunpaman, ang paraan ng paghiwa, na kinabibilangan ng pagkopya ng mga elemento sa isang bagong pinagbabatayan na hanay ay maaaring maging hindi epektibo kung ang pila nagpapalawak at nangangailangan ng paulit-ulit na pagpapatakbo ng dequeuing.
Ang sumusunod na code ay tumutukoy sa pila pagpapatupad gamit ang isang slice sa Go.
pangunahing pakete
angkat 'fmt'
func main ( ) {
pila := gumawa ( [ ] interface { } , 0 )
pila = dugtungan ( pila , 'Ingles' )
pila = dugtungan ( pila , 'urdu' )
pila = dugtungan ( pila , 'math' )
kung lamang ( pila ) > 0 {
aytem := pila [ 0 ]
pila = pila [ 1 : ]
fmt. Println ( aytem )
}
kung lamang ( pila ) == 0 {
fmt. Println ( 'Walang laman ang pila' )
} iba pa {
fmt. Println ( pila )
}
}
Gumagamit ng slice ang Go code sa itaas upang makabuo ng diretso pila istraktura ng data. Ang dugtungan() Ang function ay ginagamit upang i-enqueue ang mga elemento sa pila slice, at isang slice operation na nag-aalis ng paunang elemento ay ginagamit upang i-dequeue ang mga ito. Sa fmt.Println() , ang na-dequeued na elemento ay naka-print. Pagkatapos ay ginagamit ng code ang lamang() function upang matukoy kung ang pila ay walang laman, at kung ito ay, ito ay nagsusulat ng ' Nakapila ay walang laman” gamit ang fmt.Println() function.
Output
2: Mga Naka-link na Listahan
Ang mga node na nagdadala ng isang halaga at isang pointer sa sumusunod na node sa listahan ay bumubuo ng isang naka-link na listahan. Sa pamamagitan ng dalawang pointer, ang isa ay tumuturo sa harap (ulo) ng listahan at ang isa ay tumuturo sa likuran (buntot), maaari tayong magpatupad ng isang pila gamit ang isang naka-link na listahan. Ang pag-alis ng isang item mula sa queue (pag-dequeuing) ay kinabibilangan ng pag-alis ng node sa harap ng listahan habang ang pagdaragdag ng isang item sa queue (enqueuing) ay nagsasangkot ng pagdaragdag ng bagong node sa likuran ng listahan.
Ang pamamaraang ito ay nagbibigay-daan para sa mahusay na enqueuing at dequeuing na mga operasyon dahil ang head at tail pointer lang ang kailangang baguhin, kumpara sa slice-based na solusyon kung saan ang mga elemento ay kailangang kopyahin.
Gumamit ng naka-link na listahan upang ipatupad ang a pila sa pamamagitan ng paggamit ng ibinigay na code sa ibaba:
pangunahing paketeangkat 'fmt'
i-type ang Node struct {
interface ng halaga { }
susunod * Node
}
i-type ang Queue struct {
ulo * Node
buntot * Node
}
func main ( ) {
pila := at Nakapila { ulo : wala , buntot : wala }
bagongNode := at Node { halaga : 'Ingles' , susunod : wala }
pila. buntot = bagongNode
pila. ulo = bagongNode
bagongNode = at Node { halaga : 'urdu' , susunod : wala }
pila. buntot . susunod = bagongNode
pila. buntot = bagongNode
bagongNode = at Node { halaga : 'math' , susunod : wala }
pila. buntot . susunod = bagongNode
pila. buntot = bagongNode
kung pila. ulo != wala {
aytem := pila. ulo . halaga
pila. ulo = pila. ulo . susunod
fmt. Println ( aytem )
}
kung pila. ulo == wala {
fmt. Println ( 'Walang laman ang pila' )
}
}
Kinakatawan ng Node struct ang bawat item sa queue at naglalaman ng dalawang field: isang value field para sa pag-iimbak ng value ng item, at ang susunod na field para sa pagturo sa susunod na item sa queue. Ang Queue struct ay gumagamit ng mga katangian ng ulo at buntot upang subaybayan ang harap at likod ng pila, ayon sa pagkakabanggit. Ang buntot ang unang item ay ipinahiwatig ng ari-arian ng ulo, habang ang huling item nito ay ipinahiwatig ng katangian ng buntot.
Ang mga parameter ng ulo at buntot ay unang nakatakda sa wala kapag bago pila ay itinatag sa main() function. Ang mga head at tail pointer ay ina-update upang magdagdag ng tatlong node sa pila kasama ang mga halaga “english”, “urdu”, at “matematika”. Ang 'Ingles' item ay pagkatapos 'na-dequeued' (inalis) mula sa harapan ng pila sa pamamagitan ng pagpapakita ng halaga nito at pagsulong ng head pointer sa sumusunod na node sa pila . Pagkatapos ng dequeuing, kung ang ulo ay naging null, nangangahulugan ito na ang pila ay walang laman, at ang mensahe ay ' Nakapila ay walang laman” ay nakalimbag.
Output
3: Mga istruktura
Sa Go, maaari kang gumawa ng custom na istraktura ng data na tinatawag na a struct upang kumatawan sa a pila . Ito struct maaaring magkaroon ng mga patlang upang iimbak ang pila mga elemento at pamamaraan para magdagdag at mag-alis ng mga item, tingnan kung walang laman ang pila, at kunin ang kasalukuyang laki ng pila.
Ang ganitong paraan ng paglikha ng a pila in Go ay nag-aalok ng isang maginhawa at naka-encapsulated na pagpapatupad na may madaling gamitin na mga pamamaraan na maaaring palawakin at i-customize na may higit pang mga tampok. Ito ay isang flexible na diskarte na nagbibigay-daan para sa mga pagbabago na gawin sa pagpapatupad o magdagdag ng mga bagong kakayahan kapag kinakailangan.
Paglikha ng custom struct Kasama sa mga pamamaraan ang pagsulat ng karagdagang code kumpara sa iba pang dalawang paraan, na maaaring magpapataas ng pagiging kumplikado. Gayunpaman, nagbibigay din ito ng higit na kakayahang umangkop at kontrol sa pagpapatupad ng pila .
Ang sumusunod na halimbawa ay nagpapakita ng paglikha ng isang istraktura ng data upang kumatawan sa a pila sa Go.
pangunahing paketeangkat 'fmt'
i-type ang Queue struct {
mga bagay [ ] interface { }
}
func ( q * Nakapila ) Enqueue ( interface ng item { } ) {
q. mga bagay = dugtungan ( q. mga bagay , aytem )
}
func ( q * Nakapila ) Dequeue ( ) interface { } {
kung lamang ( q. mga bagay ) == 0 {
bumalik wala
}
aytem := q. mga bagay [ 0 ]
q. mga bagay = q. mga bagay [ 1 : ]
bumalik aytem
}
func ( q * Nakapila ) Walang laman ( ) bool {
bumalik lamang ( q. mga bagay ) == 0
}
func ( q * Nakapila ) Sukat ( ) int {
bumalik lamang ( q. mga bagay )
}
func main ( ) {
pila := at Nakapila { mga bagay : gumawa ( [ ] interface { } , 0 ) }
pila. Enqueue ( 'Ingles' )
pila. Enqueue ( 'urdu' )
pila. Enqueue ( 'math' )
aytem := pila. Dequeue ( )
fmt. Println ( aytem )
kung pila. Walang laman ( ) {
fmt. Println ( 'Walang laman ang pila' )
}
laki := pila. Sukat ( )
fmt. Println ( 'Laki ng pila:' , laki )
}
Sa code sa itaas, ang isang item ay idinagdag sa slice ng item sa pamamagitan ng Enqueue() paraan, na naglilipat nito sa dulo ng pila . Kasunod ng First-In, First-Out (FIFO) prinsipyo, ang Dequeue() ang pamamaraan ay naglalabas ng isang item sa harap ng pila at ibinabalik ito. Ang haba ng slice ng item ay nilagyan ng check bilang bahagi ng IsEmpty() pamamaraan ng pagsusuri upang makita kung ang pila ay walang laman. Sa pamamagitan ng pagbabalik ng haba ng mga item slice, ang Sukat() ibinabalik ng pamamaraan ang kasalukuyang buntot laki.
Ang pangunahing() function ay gumagamit ng Istruktura ng pila upang lumikha ng bago pila , magdagdag ng mga elemento dito, alisin ang mga item mula dito, tukuyin kung ang pila ay walang laman, at kalkulahin ang laki nito.
Output
4: Mga Channel
Sa Go, ang uri ng built-in na channel ay maaaring gamitin upang ipatupad ang a pila istraktura ng data. Ang channel ay maaaring gawin gamit ang laki ng buffer upang limitahan ang bilang ng mga elemento na maaaring i-enqueued sa anumang oras. Upang magdagdag ng elemento sa pila , maaari itong ipadala sa channel gamit ang <- operator, habang upang alisin ang isang elemento mula sa pila, maaari itong matanggap mula sa channel gamit ang parehong operator.
Ang diskarte na ito ay maaaring maging kapaki-pakinabang sa mga sitwasyon kung saan ang sabay-sabay na pag-access sa pila ay kinakailangan, dahil ang mga channel ay likas na ligtas para sa sabay-sabay na paggamit.
Mahalagang tandaan na ang mga Go channel ay tina-type. Nangangahulugan ito na maaari ka lamang magpadala ng mga halaga ng isang partikular na uri sa pamamagitan ng isang channel, at maaari ka lamang makatanggap ng mga halaga ng parehong uri mula sa channel.
Ito ay isang paglalarawan kung paano gumamit ng isang channel upang bumuo ng isang pila istraktura ng data sa Go.
pangunahing paketeangkat (
'fmt'
'oras'
)
i-type ang Queue struct {
item chaninterface { }
}
funcNewQueue ( ) * Nakapila {
q := at Nakapila {
mga bagay : gumawa ( chan interface { } ) ,
}
pumunta q. prosesoItem ( )
bumalik q
}
func ( q * Nakapila ) prosesoItem ( ) {
para sa aytem := saklaw q. mga bagay {
kung aytem == 'Ingles' {
fmt. Println ( 'Na-dequeue:' , aytem )
}
}
}
func ( q * Nakapila ) Enqueue ( interface ng item { } ) {
q. mga bagay <- aytem
}
funcmain ( ) {
pila := NewQueue ( )
pila. Enqueue ( 'Ingles' )
pila. Enqueue ( 'urdu' )
pila. Enqueue ( 'math' )
oras . Matulog ( 2 * oras . Pangalawa )
}
Ang code sa itaas ay lumilikha ng a Istruktura ng pila na may iisang field mga bagay na isang channel ng interface{} uri. Ang NewQueue() Ang function ay lumilikha ng isang bagong instance ng Nakapila at pinasimulan nito 'mga item' field na may bagong hindi na-buffer na channel. Nagsisimula rin ito ng bagong goroutine upang iproseso ang mga item na idinagdag sa pila gamit ang processItems() function. Ang processItems() sinusuri ng function kung ang natanggap na item ay katumbas ng 'Ingles' at nagpi-print ng mensahe sa console para lang sa item na iyon. Ang Enqueue() Ang function ay ginagamit upang magdagdag ng mga bagong item sa queue.
Output
Konklusyon
Ang queue ay isang mahalagang istraktura ng data sa Go na ginagamit upang mag-imbak at kumuha ng mga elemento sa isang partikular na pagkakasunud-sunod. Ang pagpapatupad ng a pila in Go ay thread-safe, na ginagawa silang perpektong pagpipilian para sa pagpapatupad ng concurrency sa mga programa. Maaari itong ipatupad gamit ang mga hiwa, naka-link na listahan, istruktura, at channel. Ang buong detalye ay ibinigay na sa ibinigay na mga alituntunin sa itaas.