Apa itu Antrian?
Ekor adalah struktur data yang digunakan untuk menyimpan dan mengambil elemen dalam urutan yang telah ditentukan. Ini adalah struktur data linier yang menyerupai tumpukan dan melekat pada FIFO (Masuk Pertama, Keluar Pertama) aturan. Ini dapat dibandingkan dengan daftar tunggu atau antrean di mana orang pertama yang tiba dilayani terlebih dahulu. Komponen yang ada dijatuhkan dari bagian depan antre , dan elemen baru ditambahkan ke belakang.
Implementasi Antrian di Golang
Pelaksanaan a antre in Go sederhana dan efisien dan dapat diimplementasikan menggunakan empat metode berikut.
1: Irisan
Di Go, a mengiris adalah array dinamis yang dapat berubah ukurannya. Untuk menerapkan a antre menggunakan sebuah mengiris , kita dapat menambahkan elemen ke belakang mengiris menggunakan fungsi append bawaan dan menghapus elemen dari depan mengiris menggunakan irisan.
Pendekatan ini mudah dibuat dan menawarkan kinerja yang baik untuk operasi penambahan dan pemotongan berkat irisan bawaan Go. Namun, metode pemotongan, yang mencakup penyalinan elemen ke larik dasar baru bisa menjadi tidak efisien jika antre memperluas dan memerlukan operasi dequeuing berulang.
Kode berikut mendefinisikan antre implementasi menggunakan slice di Go.
paket utama
impor 'fmt'
fungsi utama ( ) {
antre := membuat ( [ ] antarmuka { } , 0 )
antre = menambahkan ( antre , 'bahasa inggris' )
antre = menambahkan ( antre , 'urdu' )
antre = menambahkan ( antre , 'matematika' )
jika hanya ( antre ) > 0 {
barang := antre [ 0 ]
antre = antre [ 1 : ]
fmt. Println ( barang )
}
jika hanya ( antre ) == 0 {
fmt. Println ( 'Antrian kosong' )
} kalau tidak {
fmt. Println ( antre )
}
}
Kode Go di atas menggunakan sebuah slice untuk mengkonstruksi secara langsung antre struktur data. Itu menambahkan() fungsi digunakan untuk membuat elemen enqueue ke dalam antre slice, dan operasi slice yang menghapus elemen awal digunakan untuk mengeluarkannya. Dengan fmt.Println() , elemen yang di-dequeued akan dicetak. Kode kemudian menggunakan hanya() berfungsi untuk menentukan apakah antrian kosong, dan jika kosong, tulis “ Antre kosong” menggunakan fungsi fmt.Println().
Keluaran
2: Daftar Tertaut
Node yang membawa nilai dan penunjuk ke node berikut dalam daftar membentuk daftar tertaut. Dengan dua penunjuk, satu menunjuk ke depan (kepala) daftar dan yang lainnya menunjuk ke belakang (ekor), kita dapat mengimplementasikan antre menggunakan linked list. Menghapus item dari antrian (dequeuing) melibatkan penghapusan node di depan daftar sementara menambahkan item ke antrian (enqueuing) melibatkan penambahan node baru ke belakang daftar.
Metode ini memungkinkan operasi enqueuing dan dequeuing yang efisien karena hanya pointer kepala dan ekor yang perlu diubah, berbeda dengan solusi berbasis irisan di mana elemen perlu disalin.
Gunakan daftar tertaut untuk menerapkan a antre dengan menggunakan kode yang disediakan di bawah ini:
paket utamaimpor 'fmt'
ketik Node struct {
antarmuka nilai { }
Berikutnya * Node
}
ketik Antrian struct {
kepala * Node
ekor * Node
}
fungsi utama ( ) {
antre := & Antre { kepala : nol , ekor : nol }
newNode := & Node { nilai : 'bahasa inggris' , Berikutnya : nol }
antre. ekor = newNode
antre. kepala = newNode
newNode = & Node { nilai : 'urdu' , Berikutnya : nol }
antre. ekor . Berikutnya = newNode
antre. ekor = newNode
newNode = & Node { nilai : 'matematika' , Berikutnya : nol }
antre. ekor . Berikutnya = newNode
antre. ekor = newNode
jika antre. kepala != nol {
barang := antre. kepala . nilai
antre. kepala = antre. kepala . Berikutnya
fmt. Println ( barang )
}
jika antre. kepala == nol {
fmt. Println ( 'Antrian kosong' )
}
}
Struktur Node mewakili setiap item dalam antrean dan berisi dua bidang: bidang nilai untuk menyimpan nilai item, dan bidang selanjutnya untuk menunjuk ke item berikutnya dalam antrean. Struktur Queue menggunakan properti head dan tail untuk melacak masing-masing bagian depan dan belakang antrian. Itu ekor item pertama dilambangkan dengan properti head, sedangkan item terakhir dilambangkan dengan properti tail.
Parameter kepala dan ekor pada awalnya diatur ke nol ketika baru antre ditetapkan dalam fungsi main(). Pointer kepala dan ekor diperbarui untuk menambahkan tiga node ke antre dengan nilai-nilai “bahasa inggris”, “urdu”, Dan 'matematika'. Itu 'bahasa inggris' item kemudian “dequeued” (dihapus) dari depan antre dengan menampilkan nilainya dan memajukan penunjuk kepala ke simpul berikut di antre . Setelah dequeuing, jika head menjadi null, berarti antrian kosong, dan muncul pesan “ Antre kosong” dicetak.
Keluaran
3: Struktur
Di Go, Anda dapat membuat struktur data khusus yang disebut a struct untuk mewakili a antre . Ini struct dapat memiliki bidang untuk menyimpan antre elemen dan metode untuk menambah dan menghapus item, periksa apakah antrean kosong, dan dapatkan ukuran antrean saat ini.
Cara membuat a antre in Go menawarkan implementasi yang nyaman dan dikemas dengan metode yang mudah digunakan yang dapat diperluas dan disesuaikan dengan lebih banyak fitur. Ini adalah pendekatan fleksibel yang memungkinkan perubahan dilakukan pada implementasi atau untuk menambah kemampuan baru kapan pun diperlukan.
Membuat kebiasaan struct dengan metode melibatkan penulisan kode tambahan dibandingkan dengan dua cara lainnya, yang dapat meningkatkan kompleksitas. Namun, ini juga memberikan lebih banyak fleksibilitas dan kontrol atas penerapannya antre .
Contoh berikut menunjukkan pembuatan struktur data untuk mewakili a antre di Pergi.
paket utamaimpor 'fmt'
ketik Antrian struct {
item [ ] antarmuka { }
}
fungsi ( Q * Antre ) Enqueue ( antarmuka barang { } ) {
Q. item = menambahkan ( Q. item , barang )
}
fungsi ( Q * Antre ) Dequeue ( ) antarmuka { } {
jika hanya ( Q. item ) == 0 {
kembali nol
}
barang := Q. item [ 0 ]
Q. item = Q. item [ 1 : ]
kembali barang
}
fungsi ( Q * Antre ) Kosong ( ) bool {
kembali hanya ( Q. item ) == 0
}
fungsi ( Q * Antre ) Ukuran ( ) int {
kembali hanya ( Q. item )
}
fungsi utama ( ) {
antre := & Antre { item : membuat ( [ ] antarmuka { } , 0 ) }
antre. Enqueue ( 'bahasa inggris' )
antre. Enqueue ( 'urdu' )
antre. Enqueue ( 'matematika' )
barang := antre. Dequeue ( )
fmt. Println ( barang )
jika antre. Kosong ( ) {
fmt. Println ( 'Antrian kosong' )
}
ukuran := antre. Ukuran ( )
fmt. Println ( 'Ukuran antrian:' , ukuran )
}
Pada kode di atas, item ditambahkan ke irisan item melalui Enqueue() metode, yang memindahkannya ke akhir antre . Mengikuti Masuk Pertama, Keluar Pertama (FIFO) prinsip, yang Dequeue() metode mengambil item dari depan antre dan mengembalikannya. Panjang irisan item diperiksa sebagai bagian dari Kosong() pemeriksaan metode untuk melihat apakah antre kosong. Dengan mengembalikan panjang potongan item, the Ukuran() metode mengembalikan arus ekor ukuran.
Fungsi main() menggunakan Struktur antrian untuk membuat yang baru antre , tambahkan elemen ke dalamnya, hapus item darinya, tentukan apakah antre kosong, dan hitung ukurannya.
Keluaran
4: Saluran
Di Go, tipe saluran bawaan dapat digunakan untuk mengimplementasikan a antre struktur data. Saluran dapat dibuat dengan ukuran buffer untuk membatasi jumlah elemen yang dapat diantrekan pada waktu tertentu. Untuk menambahkan elemen ke antre , itu dapat dikirim ke saluran menggunakan <- operator, sedangkan untuk menghapus elemen dari antrian, dapat diterima dari saluran menggunakan operator yang sama.
Pendekatan ini bisa sangat berguna dalam situasi di mana akses bersamaan ke antre diperlukan, karena saluran secara inheren aman untuk penggunaan bersamaan.
Sangat penting untuk diingat bahwa saluran Go diketik. Ini berarti bahwa Anda hanya dapat mengirim nilai dengan jenis tertentu melalui saluran, dan Anda hanya dapat menerima nilai dengan jenis yang sama dari saluran.
Ini adalah ilustrasi bagaimana menggunakan saluran untuk membangun a antre struktur data di Go.
paket utamaimpor (
'fmt'
'waktu'
)
ketik Antrian struct {
item chaninterface { }
}
funcNewQueue ( ) * Antre {
Q := & Antre {
item : membuat ( antarmuka chan { } ) ,
}
pergi q. processItems ( )
kembali Q
}
fungsi ( Q * Antre ) processItems ( ) {
untuk barang := rentang q. item {
jika barang == 'bahasa inggris' {
fmt. Println ( 'Dihapus:' , barang )
}
}
}
fungsi ( Q * Antre ) Enqueue ( antarmuka barang { } ) {
Q. item <- barang
}
funcmain ( ) {
antre := Antrean Baru ( )
antre. Enqueue ( 'bahasa inggris' )
antre. Enqueue ( 'urdu' )
antre. Enqueue ( 'matematika' )
waktu . Tidur ( 2 * waktu . Kedua )
}
Kode di atas membuat a Struktur antrian dengan satu bidang item yang merupakan saluran dari antarmuka{} jenis. Itu Antrean Baru() fungsi membuat instance baru dari Antre dan menginisialisasi nya “barang” bidang dengan saluran tanpa buffer baru. Itu juga memulai goroutine baru untuk memproses item yang ditambahkan ke antrean menggunakan processItems() fungsi. Itu processItems() fungsi memeriksa apakah barang yang diterima sama dengan 'bahasa inggris' dan mencetak pesan ke konsol hanya untuk item itu. Itu Enqueue() fungsi digunakan untuk menambahkan item baru ke antrian.
Keluaran
Kesimpulan
Antrean adalah struktur data penting dalam Go yang digunakan untuk menyimpan dan mengambil elemen dalam urutan tertentu. Pelaksanaan a antre in Go adalah thread-safe, menjadikannya pilihan ideal untuk mengimplementasikan konkurensi dalam program. Itu dapat diimplementasikan menggunakan irisan, daftar tertaut, struktur, dan saluran. Rincian lengkap sudah disediakan dalam pedoman yang diberikan di atas.