[Powered by Google Translate] [Queue] [Chris Gerber, Universiti Harvard] Ini adalah CS50, CS50.TV] Salah berguna data struktur untuk menyimpan koleksi diperintahkan unsur adalah barisan. Ia digunakan apabila unsur-unsur perlu dibuang dalam perintah yang sama kerana mereka telah ditambah. Konsep ini disebut sebagai FIFO, yang merupakan singkatan bagi pertama dalam, mula-mula keluar. Untuk membantu menggambarkan ini, ia mungkin berguna untuk gambar garis checkout di kedai. Sebagai orang tiba, mereka menunggu di belakang garisan. Juruwang kemudian mengambil giliran berkhidmat pelanggan di bahagian hadapan, yang kemudian keluar satu baris pada satu masa. Dalam bidang sains komputer, kita merujuk kepada hadapan barisan sebagai ketua dan belakang sebagai ekor. Satu contoh apabila kita mungkin menggunakan ini dalam permohonan adalah senarai tunggu untuk pendaftaran kelas. Sebagai tempat duduk menjadi didapati di dalam kelas, orang di kepala senarai menunggu disediakan peluang untuk mendaftar di dalam kelas. 

Beratur boleh dibina menggunakan mana-mana koleksi yang menyimpan data dalam perintah, seperti pelbagai atau senarai berpaut. Bersama-sama dengan koleksi untuk menyimpan item dalam barisan, kita juga memerlukan satu kaedah untuk menambah item pada akhir barisan, yang dipanggil enqueuing, dan satu lagi untuk membuang item dari kepala barisan, yang dipanggil dequeuing. Ia sering berguna untuk memasukkan kaedah lain untuk mengembalikan panjang semasa barisan serta kaedah untuk memeriksa jika barisan kosong. Mari kita melihat bagaimana kita boleh melaksanakan beratur integer dalam C, menggunakan array untuk koleksi unsur. Pertama, kita mewujudkan satu struktur yang dipanggil beratur untuk memegang pembolehubah kami. Kami akan menggunakan saiz tetap 0 indeks pelbagai integer untuk menyimpan unsur-unsur. Kami juga akan termasuk kepala ubah yang dipanggil yang menyimpan indeks unsur yang kini berada di kepala barisan. Satu pembolehubah ketiga, dipanggil panjang, akan digunakan menjejaki bilangan elemen dalam array. Sebagai alternatif, anda boleh mempertimbangkan untuk menggunakan ekor pembolehubah yang dipanggil untuk menunjukkan elemen bidang terakhir dalam array. Sebelum kita menulis kod apa-apa lagi, mari kita mencuba reka bentuk kami. Mari kita mulakan dengan pelbagai kosong 0 panjang, dengan kepala disetkan kepada 0. Sekarang mari kita enqueue 4 nilai - 6, 2, 3, dan 1. Panjang sekarang akan menjadi 4, dan kepala akan kekal pada 0. 

Apakah yang akan berlaku jika kita dequeue nilai? Kami akan mengurangkan panjang hingga 3, tetapkan kepala 1, dan memulangkan nilai 6. Kod yang mungkin kelihatan seperti ini. Di sini kita mempunyai fungsi dequeue, yang mengambil penunjuk beratur - q - dan penunjuk kepada elemen, yang merupakan jenis int. Mula-mula kita memeriksa panjang barisan untuk pastikan ia adalah lebih daripada 0, untuk memastikan bahawa terdapat elemen untuk dequeued. Kemudian kita lihat dalam pelbagai unsur, di kepala kedudukan, dan menetapkan nilai unsur untuk menjadi nilai pada kedudukan itu. Kemudian kita menukar kepala menjadi indeks seterusnya % Kapasiti. Kami kemudian mengurangkan panjang baris gilir oleh 1. Akhirnya, kita kembali benar untuk menunjukkan bahawa dequeue berjaya. Jika kita dequeue lagi, panjang akan menjadi 2, kepala juga akan menjadi 2, dan nilai pulangan akan 2. 

Apakah yang akan berlaku jika kita enqueue nilai lain seperti 7? Seperti yang kita berada di akhir barisan, kita akan perlu untuk membalut di sekitar dan menyimpan nilai 0 elemen array. Secara matematik, ini boleh diwakili oleh menambah panjang indeks kepala dan melaksanakan modulus menggunakan kapasiti beratur. Di sini bahawa 2 +2, yang merupakan 4% 4, yang adalah 0. Menterjemahkan idea ini kod kita mempunyai fungsi ini. Di sini kita lihat fungsi enqueue, yang mengambil penunjuk beratur - q - dan mengambil unsur enqueued, yang merupakan integer. Kami seterusnya periksa untuk memastikan bahawa kapasiti barisan adalah masih lebih besar daripada panjang semasa beratur. Seterusnya, kami menyimpan unsur dalam pelbagai elemen pada indeks yang ditentukan oleh ketua + panjang% kapasiti barisan. Kami kemudian meningkatkan panjang baris gilir sebanyak 1, dan kemudian kembali kenyataan untuk menunjukkan bahawa fungsi enqueue berjaya. 

Di samping itu kepada dua fungsi yang kami telah sebutkan, terdapat dua fungsi tambahan. Pertama adalah fungsi isempty, yang mengambil penunjuk beratur dan mengesahkan bahawa panjang adalah 0. Kedua ialah fungsi panjang, yang juga mengambil penunjuk beratur dan mengembalikan panjang semasa dari struct. Ini gambaran singkat telah menunjukkan satu pelaksanaan kemungkinan barisan. Satu batasan pelaksanaan ini adalah bahawa barisan mempunyai saiz maksimum tetap. Jika kita cuba untuk menambah lebih banyak unsur-unsur daripada barisan boleh memegang, kita mungkin perlu untuk mengabaikan permintaan dan menggugurkan elemen, atau kita boleh memilih untuk mengembalikan beberapa jenis kesilapan. Menggunakan senarai dikaitkan bukannya array akan membuat ia lebih mudah kepada saiz dinamik barisan. Walau bagaimanapun, kerana kita tidak mempunyai akses langsung kepada unsur-unsur senarai berkaitan, jika kita tidak menjejaki ekor, kita akan perlu untuk mengimbas senarai keseluruhan dikaitkan untuk sampai ke akhir setiap kali. Kita juga boleh mempertimbangkan untuk menggunakan pelbagai jenis data yang lain, itu sebagai structs, untuk mewujudkan barisan unsur-unsur yang lebih kompleks. Memikirkan kembali contoh senarai tunggu kelas kami, struktur ini boleh mewakili pelajar individu. 

Nama saya Chris Gerber, dan ini adalah CS50. [CS50.TV] Dan pulangan - >> Satu masa yang lebih. Dan kembalilah benar untuk menunjukkan bahawa barisan berjaya. -% Kapasiti barisan - Ia akan menjadi menyeronokkan di sunting. [Ketawa]