[Powered by Google Translate] [Queue] [Chris Gerber, Universitas Harvard] Ini adalah CS50, CS50.TV] Satu berguna struktur data untuk menyimpan koleksi memerintahkan unsur adalah antrian. Hal ini digunakan ketika elemen perlu dihapus dalam urutan yang sama seperti mereka menambahkan. Konsep ini disebut sebagai FIFO, yang merupakan singkatan pertama, keluar pertama. Untuk membantu memvisualisasikan ini, mungkin berguna untuk gambar checkout line di toko. Sebagai orang tiba, mereka menunggu di belakang garis. Kasir kemudian bergiliran melayani pelanggan di depan, yang kemudian keluar dari satu baris pada satu waktu. Dalam ilmu komputer, kita lihat ke depan antrian sebagai kepala dan kembali sebagai ekor. Sebuah contoh ketika kita dapat menggunakan ini dalam aplikasi adalah daftar tunggu untuk pendaftaran kelas. Seperti kursi menjadi tersedia di kelas, orang di kepala daftar tunggu disediakan kesempatan untuk mendaftar di kelas. 

Sebuah antrian dapat dibangun menggunakan setiap koleksi yang menyimpan data dalam rangka, seperti array atau linked list. Seiring dengan koleksi untuk menyimpan item dalam antrian, kita juga perlu sebuah metode untuk menambahkan item pada akhir antrian, yang disebut enqueuing, dan lain untuk menghapus item dari kepala antrian, yang disebut dequeuing. Hal ini sering berguna untuk menyertakan metode lain untuk mengembalikan panjang saat antrian serta metode untuk memeriksa apakah antrian kosong. Mari kita lihat bagaimana kita bisa menerapkan antrian bilangan bulat di C, menggunakan array untuk koleksi elemen. Pertama, kita membuat struktur yang disebut antrian untuk memegang variabel kita. Kami akan menggunakan fixed-size 0 indeks array bilangan bulat untuk menyimpan elemen. Kami juga akan menyertakan kepala disebut variabel yang menyimpan indeks dari elemen yang saat ini di kepala antrian. Sebuah variabel ketiga, yang disebut panjang, akan digunakan untuk melacak jumlah elemen dalam array. Sebagai alternatif, Anda bisa mempertimbangkan untuk menggunakan ekor disebut variabel untuk menunjuk ke elemen field terakhir dalam array. Sebelum kita menulis kode lagi, mari kita mencoba desain kami. Mari kita mulai dengan array kosong dengan panjang 0, dengan kepala set ke 0. Sekarang mari kita enqueue 4 nilai - 6, 2, 3, dan 1. Panjang sekarang akan 4, dan kepala akan tinggal di 0. 

Apa yang terjadi jika kita dequeue nilai? Kami akan mengurangi panjang ke 3, mengatur kepala ke 1, dan mengembalikan nilai 6. Kode yang mungkin terlihat seperti ini. Di sini kita memiliki fungsi dequeue, yang membutuhkan pointer ke antrian - q - dan pointer ke elemen, yang merupakan tipe int. Pertama kita memeriksa panjang antrian untuk memastikan itu lebih dari 0, untuk memastikan bahwa ada elemen yang akan dequeued. Kemudian kita lihat dalam elemen array, di posisi kepala, dan menetapkan nilai elemen menjadi nilai di posisi itu. Kemudian kita mengubah kepala menjadi indeks berikutnya % Kapasitas. Kami kemudian mengurangi panjang antrian dengan 1. Akhirnya, kita kembali benar untuk menunjukkan bahwa dequeue itu berhasil. Jika kita dequeue lagi, panjangnya akan menjadi 2, kepala juga akan menjadi 2, dan nilai kembali akan 2. 

Apa yang terjadi jika kita enqueue nilai lain seperti 7? Ketika kami berada di ujung antrian, kita perlu membungkus dan menyimpan nilai dalam 0 elemen dari array. Secara matematis, hal ini dapat direpresentasikan dengan menambahkan panjang ke indeks kepala dan melakukan modulus menggunakan kapasitas antrian. Berikut yaitu 2 +2, yaitu 4% 4, yaitu 0. Menerjemahkan ide ini untuk kode kita memiliki fungsi ini. Di sini kita lihat fungsi enqueue, yang membutuhkan pointer ke antrian - q - dan mengambil elemen yang akan enqueued, yang merupakan integer. Kami selanjutnya periksa untuk memastikan bahwa kapasitas antrian masih lebih besar dari panjang saat antrian. Selanjutnya, kita menyimpan elemen dalam array elemen pada indeks yang ditentukan oleh kepala + panjang% kapasitas antrian. Kami kemudian meningkatkan panjang antrian oleh 1, dan kemudian kembali benar untuk menunjukkan bahwa fungsi enqueue berhasil. 

Selain dua fungsi yang telah kami sebutkan, ada dua fungsi tambahan. Pertama adalah fungsi isEmpty, yang membutuhkan pointer ke antrian dan memverifikasi bahwa panjangnya adalah 0. Yang kedua adalah fungsi panjang, yang juga membutuhkan pointer ke antrian dan mengembalikan panjang arus dari struct. Ini gambaran singkat telah menunjukkan salah satu kemungkinan pelaksanaan antrian. Salah satu keterbatasan implementasi ini adalah bahwa antrian memiliki ukuran maksimum tetap. Jika kita mencoba untuk menambahkan elemen lebih dari antrian dapat memegang, kita mungkin perlu untuk mengabaikan permintaan dan drop elemen, atau kita dapat memilih untuk kembali beberapa jenis kesalahan. Menggunakan linked list bukan array akan membuat lebih mudah untuk ukuran dinamis antrian. Namun, karena kita tidak memiliki akses langsung ke elemen linked list, jika kita tidak melacak ekor, kita harus memindai seluruh linked list untuk sampai ke akhir setiap kali. Kita juga bisa mempertimbangkan untuk menggunakan sebuah array dari jenis lain data, seperti structs, untuk menciptakan antrian elemen yang lebih kompleks. Berpikir kembali ke contoh kita dari daftar tunggu kelas, struktur ini dapat mewakili masing-masing siswa. 

Nama saya Chris Gerber, dan ini adalah CS50. [CS50.TV] Dan kembali - >> Sekali lagi. Dan kembali benar untuk menunjukkan bahwa - antrian berhasil. -% Kapasitas antrian - Ini akan menyenangkan di edit. [Tertawa]