Doug LLOYD: Jadi jika Anda sudah menonton video di stack, ini mungkin akan merasa seperti sedikit deja vu dari. Ini akan konsep yang sangat mirip, hanya dengan sedikit twist di atasnya. Kita akan bicara sekarang tentang antrian. Jadi antrian, mirip dengan tumpukan, adalah jenis lain dari struktur data yang bisa kita gunakan untuk mempertahankan Data secara terorganisasi. Mirip dengan tumpukan, dapat diimplementasikan sebagai array atau linked list. Tidak seperti tumpukan, aturan yang kita gunakan untuk menentukan ketika hal-hal akan ditambahkan dan dihapus dari antrian yang sedikit berbeda. Tidak seperti stack, yang adalah struktur LIFO, bertahan di, keluar pertama, antrian adalah FIFO struktur, FIFO, pertama, keluar pertama. Sekarang antrian, Anda mungkin memiliki analogi antrian. Jika Anda pernah berada di baris di sebuah taman hiburan atau di bank, ada semacam keadilan yang menerapkan struktur. Orang pertama di baris di bank adalah orang pertama siapa yang akan berbicara dengan teller. 

Ini akan menjadi semacam perlombaan ke bawah jika satu-satunya cara Anda harus berbicara dengan teller di Bank adalah untuk menjadi orang terakhir di line. Semua orang selalu ingin menjadi orang terakhir di line, dan orang yang ada di sana pertama yang telah menunggu untuk sementara waktu, bisa berada di sana selama berjam-jam, dan jam, dan jam sebelum mereka memiliki kesempatan untuk benar-benar menarik uang di bank. Dan jadi antrian semacam itu keadilan menerapkan struktur. Tapi itu tidak berarti yang tumpukan adalah hal yang buruk, hanya yang antrian adalah cara lain untuk melakukannya. Jadi sekali lagi antrian pertama di, pertama keluar, versus tumpukan yang berlangsung di, pertama keluar. Mirip dengan tumpukan, kita memiliki dua operasi bahwa kita dapat melakukan pada antrian. Nama-nama yang enqueue, yang menambahkan elemen baru ke akhir antrian, dan dequeue, yang untuk menghapus tertua elemen dari depan antrian. Jadi kita akan menambahkan elemen ke akhir antrian, dan kita akan menghapus elemen dari depan antrian. Sekali lagi, dengan tumpukan, kami menambahkan elemen ke atas tumpukan dan menghapus elemen dari puncak stack. Jadi dengan enqueue, itu menambah akhir, menghapus dari depan. Jadi hal tertua di sana selalu hal berikutnya untuk keluar jika kita mencoba dan dequeue sesuatu. 

Jadi sekali lagi, dengan antrian, kita bisa implementasi array berbasis dan terkait-daftar implementasi berbasis. Kita akan mulai lagi dengan implementasi berbasis array. Definisi struktur terlihat sangat mirip. Kami memiliki array lain ada tipe data nilai, sehingga dapat menahan tipe data yang sewenang-wenang. Kami lagi akan menggunakan bilangan bulat dalam contoh ini. 

Dan seperti dengan kami implementasi tumpukan berbasis array, karena kita menggunakan array, kita tentu memiliki keterbatasan bahwa C jenis dari memaksa kita, yang kita tidak memiliki dinamika di kami kemampuan untuk tumbuh dan menyusut array. Kita harus memutuskan di awal apa jumlah maksimum hal bahwa kita dapat dimasukkan ke dalam ini antrian, dan dalam hal ini, Kapasitas akan beberapa pound didefinisikan konstan dalam kode kita. Dan untuk tujuan ini video, kapasitas akan menjadi 10. 

Kita perlu untuk melacak bagian depan antrian jadi kita tahu mana elemen kami ingin dequeue, dan kita juga perlu melacak sesuatu else-- jumlah elemen yang kita miliki dalam antrian kami. Perhatikan kita tidak melacak dari akhir antrian, hanya ukuran antrian. Dan alasan untuk itu akan mudah-mudahan menjadi sedikit lebih jelas dalam sekejap. Setelah kami telah menyelesaikan definisi jenis ini, kami memiliki tipe data baru disebut antrian, yang sekarang kita bisa mendeklarasikan variabel dari jenis data. Dan agak membingungkan, saya telah memutuskan untuk memanggil antrian q ini, surat itu q bukan tipe data q. 

Jadi di sini adalah antrian kami. Ini adalah struktur. Ini berisi tiga anggota atau tiga bidang, array ukuran KAPASITAS. Dalam hal ini, KAPASITAS adalah 10. Dan array ini adalah akan terus bilangan bulat. Hijau adalah depan antrian kami, Unsur berikutnya yang akan dihapus, dan merah akan menjadi ukuran antrian, berapa banyak elemen saat ini ada dalam antrian. Jadi jika kita mengatakan equals q.front 0, dan ukuran q.size sama 0-- kami menempatkan 0s ke bidang-bidang. Dan pada titik ini, kami cukup banyak siap untuk mulai bekerja dengan antrian kami. 

Jadi operasi pertama kita bisa melakukan adalah untuk enqueue sesuatu, untuk menambahkan elemen baru untuk akhir antrian. Nah apa yang kita butuhkan untuk lakukan dalam kasus umum? Nah fungsi ini enqueue kebutuhan untuk menerima pointer ke antrian kami. Sekali lagi, jika kita telah menyatakan antrian kami secara global, kita tidak perlu melakukan hal ini tentu, tetapi secara umum, kami harus menerima pointer untuk struktur data seperti ini, karena jika tidak, kita lewat value-- kami lewat di salinan antrian, dan jadi kita tidak benar-benar berubah antrian yang kami berniat untuk berubah. 

Hal lain yang perlu dilakukan adalah menerima elemen data jenis yang sesuai. Sekali lagi, dalam kasus ini, itu akan menjadi bilangan bulat, tapi Anda bisa sewenang-wenang mendeklarasikan tipe data sebagai nilai dan menggunakan ini lebih umum. Itulah unsur kita ingin enqueue, kita ingin menambahkan ke akhir antrian. Kemudian kita benar-benar ingin menempatkan data yang dalam antrian. Dalam hal ini, menempatkannya di lokasi yang benar dari array kita, dan kemudian kita ingin mengubah ukuran antrian, berapa banyak elemen yang kita saat ini. 

Jadi mari kita mulai. Berikut ini adalah, sekali lagi, yang umum Fungsi bentuk deklarasi untuk apa enqueue mungkin terlihat seperti. Dan di sini kita pergi. Mari enqueue nomor 28 ke dalam antrian. Jadi apa yang akan kita lakukan? Nah, bagian depan antrian kami adalah pada 0, dan ukuran antrian kami adalah pada 0, dan jadi kita mungkin ingin menempatkan jumlah 28 jumlah elemen array 0, kan? Jadi sekarang kami telah ditempatkan bahwa dalam sana. Jadi sekarang apa yang kita perlu mengubah? Kami tidak ingin mengubah bagian depan antrian, karena kita ingin tahu apa elemen kita mungkin perlu dequeue nanti. Jadi alasan kita harus depan ada adalah semacam indikator apa hal tertua di array. Nah hal tertua di array-- dalam Bahkan, satu-satunya hal dalam array yang tepat sekarang-- adalah 28, yang merupakan di berbagai lokasi 0. Jadi kita tidak ingin mengubah nomor hijau, karena itulah unsur tertua. Sebaliknya, kita ingin mengubah ukuran. Jadi dalam hal ini, kita akan kenaikan ukuran 1. 

Sekarang semacam umum ide di mana Elemen berikutnya akan masuk antrian adalah untuk menambahkan dua angka bersama-sama, depan dan ukuran, dan yang akan memberitahu Anda di mana selanjutnya elemen dalam antrian akan pergi. Jadi sekarang mari kita enqueue nomor lain. Mari enqueue 33. Jadi 33 akan masuk ke Array lokasi 0 ditambah 1. Jadi dalam hal ini, itu akan untuk pergi ke dalam array lokasi 1, dan sekarang ukuran antrian kami adalah 2. 

Sekali lagi, kita tidak mengubah bagian depan antrian kami, karena 28 masih elemen tertua, dan kami ingin to-- ketika kita akhirnya mendapatkan untuk dequeuing, menghapus elemen dari antrian ini, kami ingin tahu di mana unsur tertua adalah. Dan jadi kita selalu perlu untuk mempertahankan beberapa indikator mana yang. Jadi itulah yang 0 ada untuk. Itulah yang depan sana untuk. 

Mari di enqueue satu elemen, 19. Saya yakin Anda bisa menebak di mana 19 akan pergi. Ini akan masuk ke Array lokasi nomor 2. Itu 0 ditambah 2. Dan sekarang ukuran antrian kami adalah 3. Kami memiliki 3 elemen di dalamnya. Jadi jika kita, dan kita tidak akan untuk sekarang, enqueue elemen lain, itu akan masuk ke lokasi array yang nomor 3, dan ukuran antrian kami akan 4. Jadi kita sudah enqueued beberapa elemen sekarang. Sekarang mari kita mulai untuk menghapusnya. Mari kita dequeue mereka dari antrian. 

Jadi mirip dengan pop, yang merupakan semacam dari analog ini untuk tumpukan, dequeue perlu menerima pointer ke queue-- lagi, kecuali jika dinyatakan secara global. Sekarang kita ingin mengubah lokasi dari depan antrian. Ini adalah di mana ia semacam datang ke dalam bermain, bahwa variabel depan, karena sekali kita hapus elemen, kita ingin untuk memindahkannya ke elemen tertua berikutnya. 

Kemudian kita ingin menurunkan ukuran antrian, dan kemudian kita ingin mengembalikan nilai yang telah dihapus dari antrian. Sekali lagi, kita tidak ingin hanya membuangnya. Kami mungkin penggalian itu dari queue-- kami dequeuing itu karena kami peduli tentang hal itu. Jadi kita ingin fungsi ini untuk kembali elemen data jenis nilai. Sekali lagi, dalam kasus ini, nilai adalah bilangan bulat. 

Jadi sekarang mari kita dequeue sesuatu. Mari kita menghapus elemen dari antrian. Jika kita mengatakan int x sama & q, ampersand q-- lagi itu pointer ke data yang q ini structure-- apa elemen adalah akan dequeued? Dalam hal ini, karena merupakan pertama , keluar pertama struktur data, FIFO, hal pertama yang kita dimasukkan ke dalam ini antrian adalah 28, dan dalam hal ini, kita akan mengambil 28 dari antrian, tidak 19, yang adalah apa yang kita akan dilakukan jika ini adalah stack. Kita akan mengambil 28 dari antrian. 

Mirip dengan apa yang kita lakukan dengan stack, kami tidak benar-benar akan menghapus 28 dari antrian itu sendiri, kami hanya akan jenis dari berpura-pura itu tidak ada. Jadi itu akan tinggal di sana dalam memori, tapi kami hanya akan jenis mengabaikannya dengan memindahkan dua bidang lain data q kami struktur. Kita akan mengubah bagian depan. Q.front sekarang akan menjadi 1, karena yang sekarang unsur tertua yang kita miliki di kami antrian, karena kita sudah dihapus 28, yang merupakan mantan unsur tertua. 

Dan sekarang, kami ingin mengubah ukuran antrian dua elemen bukannya tiga. Sekarang ingat sebelumnya saya katakan ketika kita ingin menambahkan elemen ke antrian, kita meletakkannya di lokasi array yang yang merupakan jumlah dari depan dan ukuran. Jadi dalam hal ini, kami masih menempatkan itu, elemen berikutnya dalam antrian, ke dalam array lokasi 3, dan kita akan melihat bahwa dalam satu detik. 

Jadi kita sekarang sudah dequeued kami elemen pertama dari antrian. Mari kita melakukannya lagi. Mari kita hapus lain elemen dari antrian. Dalam kasus ini, saat tertua elemen Array lokasi 1. Itulah yang q.front memberitahu kita. Kotak hijau memberitahu kita bahwa itulah unsur tertua. Dan sebagainya, x akan menjadi 33. Kami akan hanya jenis lupa yang 33 ada di array, dan kami akan mengatakan bahwa saat ini, Unsur tertua baru dalam antrian di berbagai lokasi 2, dan ukuran antrian, jumlah elemen kita miliki dalam antrian, adalah 1. Sekarang mari kita enqueue sesuatu, dan saya semacam memberikan ini pergi kedua lalu, tetapi jika kita ingin menempatkan 40 ke antrian, di mana yang 40 akan pergi? Nah kita sudah menempatkan di q.front ditambah antrian ukuran, dan sehingga masuk akal untuk sebenarnya untuk menempatkan 40 di sini. Sekarang perhatikan bahwa pada beberapa titik, kita akan untuk sampai ke akhir array kita dalam q, tapi itu memudar keluar 28 dan 33-- mereka sebenarnya, secara teknis ruang terbuka, kan? Dan, kita dapat eventually-- bahwa aturan menambahkan dua together-- kita mungkin akhirnya perlu mod dengan ukuran kapasitas sehingga kita bisa membungkus. 

Jadi jika kita mendapatkan elemen nomor 10, jika kita menggantinya jumlahnya elemen 10, kami akan benar-benar menempatkan itu dalam array lokasi 0. Dan jika kita akan Array yang lokasi permisi, jika kita menambahkan mereka bersama-sama, dan kita harus nomor 11 akan di mana kita harus menempatkan itu, yang tidak ada di array-- ini itu akan terjadi di luar batas. Kita bisa mod 10 dan menempatkan itu dalam array lokasi 1. Jadi itulah cara antrian bekerja. Mereka akan selalu pergi dari kiri ke kanan dan mungkin membungkus. Dan Anda tahu bahwa mereka penuh jika ukuran, kotak merah, menjadi sama dengan kapasitas. Dan setelah kami telah menambahkan 40 ke antrian, baik apa yang perlu kita lakukan? Nah, elemen tertua dalam antrian masih 19, jadi kami tidak ingin mengubah bagian depan antrian, tapi sekarang kami memiliki dua elemen dalam antrian, dan jadi kami ingin meningkatkan ukuran kami 1-2. 

Itu cukup banyak itu dengan bekerja dengan antrian berbasis array, dan mirip dengan stack, ada juga cara untuk menerapkan antrian sebagai linked list. Sekarang jika ini jenis struktur data tampak akrab bagi Anda, itu. Ini bukan daftar sendiri-sendiri terkait, itu daftar ganda terkait. Dan sekarang, sebagai samping, itu adalah sebenarnya mungkin untuk mengimplementasikan antrian sebagai daftar tunggal terkait, tapi Saya pikir dalam hal visualisasi, itu benar-benar dapat membantu untuk melihat ini sebagai daftar ganda terkait. Tapi pasti mungkin untuk melakukan hal ini sebagai daftar tunggal terkait. 

Jadi mari kita lihat apa ini mungkin terlihat seperti. Jika kita ingin enquue-- jadi sekarang, lagi kami beralih ke-linked list Model berbasis di sini. Jika kita ingin enqueue, kami ingin untuk menambahkan elemen baru, baik apa yang perlu kita lakukan? Yah, pertama-tama, karena kita menambahkan sampai akhir dan menghapus dari mulai, kita mungkin ingin mempertahankan pointer ke kedua kepala dan ekor dari linked list? Ekor menjadi istilah lain untuk akhir linked list, elemen terakhir dalam linked list. Dan mungkin ini akan, lagi, bermanfaat bagi kami jika mereka adalah variabel global. Tapi sekarang jika kita ingin menambahkan baru unsur apa yang harus kita lakukan? Apa yang kita hanya [? malak?] atau dinamis mengalokasikan simpul baru kami untuk diri kita sendiri. Dan kemudian, sama seperti ketika kita menambahkan elemen ke ganda terkait daftar kami, hanya perlu memilah of-- tiga langkah terakhir di sini hanya semua tentang memindahkan pointer dalam cara yang benar sehingga elemen akan ditambahkan ke rantai tanpa melanggar rantai atau membuat semacam kesalahan atau memiliki semacam kecelakaan terjadi dimana kami sengaja yatim beberapa elemen dari antrian kami. Inilah yang ini mungkin terlihat seperti. Kita ingin menambahkan elemen 10 sampai akhir antrian ini. Jadi unsur tertua di sini diwakili oleh kepala. Itulah hal pertama yang kita menempatkan ke dalam antrian hipotetis ini di sini. Dan ekor, 13, adalah yang paling baru-baru ini menambahkan elemen. Dan jika kita ingin enqueue 10 ke antrian ini, kita ingin menempatkan setelah 13. Dan kita akan dinamis mengalokasikan ruang untuk node baru dan memeriksa null untuk memastikan kita tidak memiliki kegagalan memori. Kemudian kita akan menempatkan 10 ke simpul itu, dan sekarang kita harus berhati-hati tentang bagaimana kita mengatur pointer jadi kami tidak memutuskan rantai. 

Kita dapat mengatur bidang 10 sebelumnya untuk menunjuk kembali ke ekor tua, dan karena '10 akan menjadi ekor baru di beberapa titik pada saat semua ini rantai yang terhubung, tidak ada yang akan datang setelah 10 sekarang. Dan 10 untuk pointer berikutnya akan menunjuk ke null, dan kemudian setelah kami melakukan hal ini, setelah kami sudah Koneksi 10 belakang untuk rantai, kita dapat mengambil kepala tua, atau, alasan saya, ekor lama antrian. Akhir lama antrian, 13, dan membuatnya menunjuk ke 10. Dan sekarang, pada titik ini, kita memiliki enqueued nomor 10 ke dalam antrian ini. Semua yang perlu kita lakukan sekarang adalah hanya memindahkan ekor untuk menunjuk ke 10 bukan ke 13. 

Dequeuing sebenarnya sangat mirip dengan bermunculan dari tumpukan yang diimplementasikan sebagai linked list jika Anda pernah melihat tumpukan video. Semua yang perlu kita lakukan adalah mulai di mulai, menemukan elemen kedua, membebaskan elemen pertama, dan kemudian memindahkan kepala untuk menunjuk ke elemen kedua. Mungkin lebih baik untuk memvisualisasikan itu hanya untuk menjadi tambahan yang jelas tentang hal itu. Jadi, inilah antrian kami lagi. 12 adalah unsur tertua dalam antrian kami, kepala. 10 adalah elemen terbaru dalam antrian kami, ekor kami. 

Dan ketika kita ingin untuk dequeue elemen, kita ingin menghapus elemen tertua. Jadi apa yang kita lakukan? Baik kita menetapkan pointer traversal yang dimulai di kepala, dan kami memindahkannya sehingga menunjuk ke elemen kedua ini queue-- sesuatu dengan mengatakan trav sama trav panah berikutnya, misalnya, akan pindah trav ada untuk menunjuk ke 15, yang, setelah kami dequeue 12, atau setelah kita menghapus 12, akan menjadi elemen kemudian tertua. 

Sekarang kita punya pegangan pada pertama Unsur melalui kepala pointer dan elemen kedua melalui trav pointer. Kita bisa kepala sekarang bebas, dan kemudian kita bisa mengatakan tidak ada yang datang sebelum 15 lagi. Jadi kita dapat mengubah 15 sebelumnya pointer untuk menunjuk ke null, dan kami hanya memindahkan kepala lebih. Dan di sana kita pergi. Sekarang kita telah berhasil dequeued 12, dan sekarang kami memiliki antrian lain 4 elemen. Itu cukup banyak semua ada untuk antrian, baik-array berbasis dan terkait-daftar berbasis. Aku Doug Lloyd. Ini adalah CS 50.