Apakah itu Queue?
Ekor ialah struktur data yang digunakan untuk menyimpan dan mendapatkan semula elemen dalam susunan yang telah ditetapkan. Ia adalah struktur data linear yang menyerupai tindanan dan mematuhi FIFO (Masuk Dahulu, Keluar Dahulu) peraturan. Ia boleh dibandingkan dengan senarai menunggu atau barisan di mana orang pertama yang tiba diservis terlebih dahulu. Komponen sedia ada digugurkan dari hadapan beratur , dan elemen baharu ditambahkan pada bahagian belakang.
Pelaksanaan Beratur di Golang
Pelaksanaan a beratur dalam Go adalah mudah dan cekap dan boleh dilaksanakan menggunakan empat kaedah berikut.
1: Kepingan
Dalam Go, a hirisan ialah tatasusunan dinamik yang boleh berubah dalam saiz. Untuk melaksanakan a beratur menggunakan a hirisan , kita boleh menambah elemen pada bahagian belakang hirisan menggunakan fungsi tambah terbina dalam dan keluarkan elemen dari bahagian hadapan hirisan menggunakan penghirisan.
Pendekatan ini mudah dibina dan menawarkan prestasi yang baik untuk operasi menambah dan menghiris terima kasih kepada kepingan terbina dalam Go. Walau bagaimanapun, kaedah penghirisan, yang termasuk menyalin elemen ke tatasusunan asas baharu boleh menjadi tidak cekap jika beratur mengembang dan memerlukan operasi nyah gilir berulang.
Kod berikut mentakrifkan beratur pelaksanaan menggunakan kepingan dalam Go.
pakej utama
import 'fmt'
fungsi utama ( ) {
beratur := buat ( [ ] antara muka { } , 0 )
beratur = tambahkan ( beratur , 'bahasa Inggeris' )
beratur = tambahkan ( beratur , 'urdu' )
beratur = tambahkan ( beratur , 'matematik' )
jika sahaja ( beratur ) > 0 {
item := beratur [ 0 ]
beratur = beratur [ 1 : ]
fmt. Println ( item )
}
jika sahaja ( beratur ) == 0 {
fmt. Println ( 'Barisan kosong' )
} lain {
fmt. Println ( beratur )
}
}
Kod Go di atas menggunakan hirisan untuk membina yang mudah beratur struktur data. The tambah() fungsi digunakan untuk memasukkan elemen ke dalam beratur slice, dan operasi hirisan yang mengalih keluar elemen awal digunakan untuk menyah gilir mereka. Dengan fmt.Println() , elemen dequeued dicetak. Kod itu kemudian menggunakan sahaja() berfungsi untuk menentukan sama ada baris gilir kosong, dan jika ia kosong, ia menulis ' Beratur kosong” menggunakan fungsi fmt.Println().
Pengeluaran
2: Senarai Berpaut
Nod yang membawa nilai dan penunjuk ke nod berikut dalam senarai membentuk senarai terpaut. Dengan dua penunjuk, satu menunjuk ke hadapan (kepala) senarai dan satu lagi menunjuk ke belakang (ekor), kita boleh melaksanakan beratur menggunakan senarai terpaut. Mengalih keluar item daripada baris gilir (menyah gilir) melibatkan mengalih keluar nod di hadapan senarai manakala menambah item pada baris gilir (enqueuing) melibatkan penambahan nod baharu ke bahagian belakang senarai.
Kaedah ini membolehkan operasi enqueuing dan dequeuing yang cekap kerana hanya penunjuk kepala dan ekor yang perlu ditukar, berbanding penyelesaian berasaskan kepingan di mana elemen perlu disalin.
Gunakan senarai terpaut untuk melaksanakan a beratur dengan menggunakan kod yang disediakan di bawah:
pakej utamaimport 'fmt'
taip Node struct {
antara muka nilai { }
seterusnya * Nod
}
taip Baris struct {
kepala * Nod
ekor * Nod
}
fungsi utama ( ) {
beratur := & Beratur { kepala : tiada , ekor : tiada }
newNode := & Nod { nilai : 'bahasa Inggeris' , seterusnya : tiada }
beratur. ekor = newNode
beratur. kepala = newNode
newNode = & Nod { nilai : 'urdu' , seterusnya : tiada }
beratur. ekor . seterusnya = newNode
beratur. ekor = newNode
newNode = & Nod { nilai : 'matematik' , seterusnya : tiada }
beratur. ekor . seterusnya = newNode
beratur. ekor = newNode
jika beratur. kepala != tiada {
item := beratur. kepala . nilai
beratur. kepala = beratur. kepala . seterusnya
fmt. Println ( item )
}
jika beratur. kepala == tiada {
fmt. Println ( 'Barisan kosong' )
}
}
Struktur Nod mewakili setiap item dalam baris gilir dan mengandungi dua medan: medan nilai untuk menyimpan nilai item, dan medan seterusnya untuk menunjuk ke item seterusnya dalam baris gilir. Struktur Queue menggunakan sifat kepala dan ekor untuk menjejaki bahagian depan dan belakang baris gilir, masing-masing. The ekor item pertama ditunjukkan oleh harta kepala, manakala item terakhirnya ditunjukkan oleh sifat ekor.
Parameter kepala dan ekor pada mulanya ditetapkan kepada tiada apabila baru beratur ditubuhkan dalam fungsi main(). Penunjuk kepala dan ekor dikemas kini untuk menambah tiga nod pada beratur dengan nilai “bahasa Inggeris”, “urdu”, dan “matematik”. The “bahasa Inggeris” item adalah kemudian 'ditunda' (dialihkan) dari hadapan beratur dengan memaparkan nilainya dan memajukan penuding kepala ke nod berikut dalam beratur . Selepas nyah gilir, jika kepala menjadi batal, ini bermakna baris gilir kosong, dan mesej ' Beratur kosong” dicetak.
Pengeluaran
3: Struktur
Dalam Go, anda boleh membuat struktur data tersuai yang dipanggil a struct untuk mewakili a beratur . ini struct boleh mempunyai medan untuk menyimpan beratur elemen dan kaedah untuk menambah dan mengalih keluar item, semak sama ada baris gilir kosong dan dapatkan saiz baris gilir semasa.
Cara ini mencipta a beratur in Go menawarkan pelaksanaan yang mudah dan terkapsul dengan kaedah yang mudah digunakan yang boleh dikembangkan dan disesuaikan dengan lebih banyak ciri. Ia merupakan pendekatan fleksibel yang membolehkan perubahan dibuat pada pelaksanaan atau menambah keupayaan baharu apabila diperlukan.
Mencipta adat struct dengan kaedah melibatkan penulisan kod tambahan berbanding dengan dua cara lain, yang mungkin meningkatkan kerumitan. Walau bagaimanapun, ia juga menyediakan lebih fleksibiliti dan kawalan ke atas pelaksanaan beratur .
Contoh berikut menunjukkan mencipta struktur data untuk mewakili a beratur dalam Go.
pakej utamaimport 'fmt'
taip Baris struct {
barang [ ] antara muka { }
}
fungsi ( q * Beratur ) Beratur ( antara muka item { } ) {
q. barang = tambahkan ( q. barang , item )
}
fungsi ( q * Beratur ) Dequeue ( ) antara muka { } {
jika sahaja ( q. barang ) == 0 {
kembali tiada
}
item := q. barang [ 0 ]
q. barang = q. barang [ 1 : ]
kembali item
}
fungsi ( q * Beratur ) Kosong ( ) bool {
kembali sahaja ( q. barang ) == 0
}
fungsi ( q * Beratur ) Saiz ( ) int {
kembali sahaja ( q. barang )
}
fungsi utama ( ) {
beratur := & Beratur { barang : buat ( [ ] antara muka { } , 0 ) }
beratur. Beratur ( 'bahasa Inggeris' )
beratur. Beratur ( 'urdu' )
beratur. Beratur ( 'matematik' )
item := beratur. Dequeue ( )
fmt. Println ( item )
jika beratur. Kosong ( ) {
fmt. Println ( 'Barisan kosong' )
}
saiz := beratur. Saiz ( )
fmt. Println ( 'Saiz baris gilir:' , saiz )
}
Dalam kod di atas, item dilampirkan pada kepingan item melalui Enqueue() kaedah, yang menggerakkannya ke penghujung beratur . Mengikuti Mula-mula Masuk, Mula-mula Keluar (FIFO) prinsip, yang Dequeue() kaedah mengeluarkan item dari hadapan beratur dan mengembalikannya. Panjang kepingan item ditandakan sebagai sebahagian daripada Kosong() kaedah semak untuk melihat sama ada beratur kosong. Dengan mengembalikan panjang kepingan item, Saiz() kaedah mengembalikan arus ekor saiz.
Fungsi utama() menggunakan Struktur baris gilir untuk mencipta yang baru beratur , tambah elemen padanya, alih keluar item daripadanya, tentukan sama ada beratur kosong, dan hitung saiznya.
Pengeluaran
4: Saluran
Dalam Go, jenis saluran terbina dalam boleh digunakan untuk melaksanakan a beratur struktur data. Saluran boleh dibuat dengan saiz penimbal untuk mengehadkan bilangan elemen yang boleh dimasukkan pada bila-bila masa. Untuk menambah elemen pada beratur , ia boleh dihantar ke saluran menggunakan <- operator, manakala untuk mengalih keluar elemen daripada baris gilir, ia boleh diterima daripada saluran menggunakan operator yang sama.
Pendekatan ini boleh menjadi agak berguna dalam situasi di mana akses serentak ke beratur diperlukan, kerana saluran sememangnya selamat untuk kegunaan serentak.
Adalah penting untuk diingat bahawa saluran Go ditaip. Ini bermakna anda hanya boleh menghantar nilai jenis tertentu melalui saluran dan anda hanya boleh menerima nilai jenis yang sama daripada saluran.
Ini adalah ilustrasi cara menggunakan saluran untuk membina a beratur struktur data dalam Go.
pakej utamaimport (
'fmt'
'masa'
)
taip Baris struct {
item chaninterface { }
}
funcNewQueue ( ) * Beratur {
q := & Beratur {
barang : buat ( antara muka chan { } ) ,
}
pergi q. processItems ( )
kembali q
}
fungsi ( q * Beratur ) processItems ( ) {
untuk item := julat q. barang {
jika item == 'bahasa Inggeris' {
fmt. Println ( 'Dihentikan giliran:' , item )
}
}
}
fungsi ( q * Beratur ) Beratur ( antara muka item { } ) {
q. barang <- item
}
funcmain ( ) {
beratur := NewQueue ( )
beratur. Beratur ( 'bahasa Inggeris' )
beratur. Beratur ( 'urdu' )
beratur. Beratur ( 'matematik' )
masa . tidur ( 2 * masa . Kedua )
}
Kod di atas mencipta a Struktur baris gilir dengan satu bidang barang yang merupakan saluran daripada antara muka{} taip. The NewQueue() fungsi mencipta contoh baharu bagi Beratur dan memulakannya “barangan” medan dengan saluran tidak buffer baharu. Ia juga memulakan goroutine baharu untuk memproses item yang ditambahkan pada baris gilir menggunakan processItems() fungsi. The processItems() fungsi menyemak sama ada item yang diterima adalah sama dengan “bahasa Inggeris” dan mencetak mesej kepada konsol untuk item itu sahaja. The Enqueue() fungsi digunakan untuk menambah item baru pada baris gilir.
Pengeluaran
Kesimpulan
Baris gilir ialah struktur data penting dalam Go yang digunakan untuk menyimpan dan mendapatkan semula elemen dalam susunan tertentu. Pelaksanaan a beratur in Go adalah thread-safe, menjadikannya pilihan ideal untuk melaksanakan konkurensi dalam program. Ia boleh dilaksanakan menggunakan kepingan, senarai terpaut, struktur dan saluran. Butiran penuh sudah disediakan dalam garis panduan yang diberikan di atas.