DOUG LLOYD: Jadi jika anda telah menonton video pada timbunan, ini mungkin akan berasa seperti sedikit deja vu. Ia akan konsep yang hampir sama, hanya dengan sentuhan sedikit di atasnya. Kami akan bercakap kini kira-kira beratur. Jadi barisan, sama dengan timbunan, satu lagi jenis struktur data yang boleh kita gunakan untuk mengekalkan data dengan cara yang teratur. Sama seperti timbunan, ia boleh dilaksanakan sebagai pelbagai atau senarai berpaut. Tidak seperti timbunan, peraturan yang kita gunakan untuk menentukan apabila perkara yang ditambah dan dikeluarkan daripada barisan yang sedikit berbeza. Tidak seperti timbunan, yang adalah struktur LIFO, bertahan dalam, dahulu, barisan adalah FIFO yang struktur, FIFO, masuk dahulu, keluar dahulu. Sekarang beratur, anda mungkin mempunyai analogi untuk beratur. Jika anda pernah berada dalam talian di taman hiburan atau di bank, ada jenis keadilan yang melaksanakan struktur. Orang pertama dalam talian di bank adalah orang yang pertama siapa yang boleh bercakap dengan juruwang. 

Ia akan menjadi jenis perlumbaan ke bawah jika satu-satunya cara anda mendapat untuk bercakap dengan juruwang di bank adalah untuk menjadi orang yang terakhir dalam barisan. Semua orang akan sentiasa mahu untuk menjadi orang yang terakhir di dalam talian, dan orang yang berada di sana pertama yang telah menunggu untuk seketika, boleh berada di sana selama berjam-jam, dan jam, dan jam sebelum mereka mempunyai peluang untuk benar-benar mengeluarkan apa-apa wang di bank. Dan supaya beratur adalah jenis yang keadilan melaksanakan struktur. Tetapi itu tidak bermakna yang susunan adalah satu perkara yang buruk, hanya yang beratur adalah satu lagi cara untuk melakukannya. Jadi sekali lagi beratur adalah masuk dahulu, keluar, berbanding timbunan yang bertahan dalam, pertama keluar. Sama seperti timbunan, kita mempunyai dua operasi yang kita boleh melakukan pada beratur. Nama-nama yang enqueue, iaitu untuk menambah elemen baru ke akhir barisan, dan dequeue, yang untuk membuang tertua unsur dari depan barisan. Jadi, kita akan menambah elemen ke akhir barisan, dan kita akan membuang unsur-unsur dari bahagian depan barisan. Sekali lagi, dengan timbunan, kita telah menambah unsur-unsur untuk bahagian atas timbunan dan membuang unsur-unsur dari bahagian atas timbunan. Jadi dengan enqueue, ia menambah kepada Akhirnya, mengeluarkan dari hadapan. Jadi perkara yang paling tua di sana sentiasa perkara yang akan datang untuk keluar jika kita cuba dan dequeue sesuatu. 

Jadi sekali lagi, dengan beratur, kita boleh pelaksanaan berdasarkan lokasi- dan dihubungkan-senarai pelaksanaan berasaskan. Kami akan bermula sekali lagi dengan pelaksanaan berdasarkan lokasi. Takrif struktur kelihatan agak sama. Kami mempunyai pelbagai lain terdapat nilai jenis data, sehingga dapat memegang jenis data yang sewenang-wenangnya. Kami sekali lagi akan menggunakan bilangan bulat dalam contoh ini. 

Dan seperti dengan kami pelaksanaan timbunan berdasarkan lokasi-, kerana kita menggunakan pelbagai, kita semestinya mempunyai batasan yang bahawa C jenis daripada menguatkuasakan kepada kita, yang kita tidak mempunyai dinamisme dalam kita keupayaan untuk berkembang dan mengecut array. Kita perlu membuat keputusan pada permulaan apa yang bilangan maksimum perkara bahawa kita boleh dimasukkan ke dalam ini barisan, dan dalam hal ini, kapasiti akan menjadi beberapa pound ditakrifkan berterusan dalam kod kami. Dan bagi maksud ini video, kapasiti akan menjadi 10. 

Kita perlu untuk mengesan bahagian depan barisan supaya kita tahu mana elemen kita mahu dequeue, dan kita juga perlu untuk mengesan sesuatu else-- bilangan elemen yang kita ada dalam barisan kami. Perhatikan kami tidak mengesan akhir barisan, hanya saiz barisan. Dan sebab yang akan diharapkan menjadi sedikit lebih jelas dalam seketika. Setelah kami selesai ini definisi jenis, kita mempunyai jenis data baru dipanggil barisan, yang kita kini boleh mengisytiharkan pembolehubah yang jenis data. Dan agak mengelirukan, saya telah membuat keputusan untuk memanggil barisan q ini, surat itu q bukannya jenis data q. 

Jadi di sini adalah giliran kami. Ia adalah struktur. Ia mengandungi tiga anggota atau tiga telah disiapkan, pelbagai saiz KEUPAYAAN. Dalam kes ini, KEUPAYAAN adalah 10. Dan lokasi ini adalah akan mengadakan integer. Dalam hijau hadapan barisan kita, Elemen seterusnya yang akan dikeluarkan, dan merah akan menjadi saiz barisan, berapa banyak elemen kini yang sedia ada dalam barisan. Jadi, jika kita katakan setaraf q.front 0, dan saiz q.size sama 0-- kita meletakkan 0-an dalam bidang-bidang. Dan pada ketika ini, kami cukup banyak bersedia untuk mula bekerja dengan barisan kami. 

Jadi operasi pertama kita boleh melaksanakan adalah untuk enqueue sesuatu, untuk menambah elemen baru untuk akhir barisan. Baik apa yang perlu kita lakukan dalam kes umum? Well fungsi ini enqueue keperluan untuk menerima penunjuk kepada barisan kami. Sekali lagi, jika kita telah mengisytiharkan giliran kami di seluruh dunia, kita tidak perlu untuk melakukan ini semestinya, tetapi secara umum, kita perlu menerima petunjuk kepada struktur data seperti ini, kerana jika tidak, kita lulus oleh value-- kami lulus dalam salinan barisan, dan sebagainya kita tidak benar-benar berubah barisan yang kami berhasrat untuk berubah. 

Perkara lain yang diperlukan untuk lakukan ialah menerima elemen data dari jenis yang sesuai. Sekali lagi, dalam kes ini, ia akan menjadi bilangan bulat, tetapi anda boleh sewenang-wenangnya mengisytiharkan jenis data sebagai nilai dan menggunakan ini amnya. Itulah elemen yang kita mahu enqueue, kita mahu menambah hingga akhir barisan. Maka kita benar-benar ingin meletakkan data yang dalam barisan. Dalam kes ini, penempatannya dalam lokasi yang betul pelbagai kami, dan kemudian kita mahu menukar saiz barisan, berapa banyak elemen kita kini mempunyai. 

Jadi mari kita mulakan. Di sini, sekali lagi, bahawa umum pengisytiharan fungsi bentuk untuk apa enqueue mungkin kelihatan seperti. Dan di sini kita pergi. Mari kita enqueue jumlah 28 ke dalam barisan. Jadi apa yang kita akan lakukan? Nah, hadapan barisan kita pada 0, dan saiz barisan kami adalah pada 0, dan dengan itu kita mungkin mahu meletakkan angka 28 dalam bilangan elemen array 0, bukan? Jadi, sekarang kita telah meletakkan bahawa di sana. Jadi sekarang apa yang kita perlu berubah? Kami tidak mahu berubah bahagian depan barisan, kerana kita ingin tahu apa elemen kita mungkin perlu dequeue kemudian. Jadi sebab kita ada depan terdapat adalah jenis petunjuk apa yang Perkara yang tertua dalam array. Baik perkara yang tertua di array-- dalam Malah, satu-satunya perkara dalam array yang betul sekarang-- adalah 28, yang merupakan di pelbagai lokasi 0. Oleh itu, kita tidak mahu menukar bilangan hijau, kerana itulah elemen yang paling lama. Sebaliknya, kita mahu menukar saiz. Jadi dalam kes ini, kita akan kenaikan saiz 1. 

Sekarang semacam umum idea di mana yang Elemen seterusnya akan pergi dalam barisan adalah untuk menambah kedua-dua nombor bersama-sama, depan dan saiz, dan yang akan memberitahu anda di mana seterusnya elemen dalam barisan akan pergi. Jadi sekarang mari kita enqueue nombor lain. Mari kita enqueue 33. Jadi 33 akan pergi ke dalam pelbagai lokasi 0 tambah 1. Jadi dalam kes ini, ia akan untuk pergi ke lokasi mudah 1, dan sekarang saiz barisan kita 2. 

Sekali lagi, kita tidak akan menukar hadapan barisan kita, kerana 28 masih unsur tertua, dan kami mahu supaya- apabila kita akhirnya mendapatkan untuk dequeuing, mengeluarkan unsur-unsur dari barisan ini, kami ingin tahu mana elemen tertua. Dan dengan itu kita sentiasa perlu untuk mengekalkan beberapa petunjuk mana yang. Jadi itulah yang 0 ada untuk. Itulah yang depan ada untuk. 

Mari kita di enqueue satu lagi elemen, 19. Saya pasti anda boleh meneka di mana 19 akan pergi. Ia akan pergi ke pelbagai nombor lokasi 2. Itulah 0 tambah 2. Dan kini saiz barisan kami ialah 3. Kami mempunyai 3 elemen di dalamnya. Jadi jika kita, dan kita tidak akan untuk sekarang, enqueue unsur lain, ia akan pergi ke lokasi mudah nombor 3, dan saiz barisan kami akan menjadi 4. Oleh itu, kita enqueued beberapa elemen sekarang. Sekarang mari kita mulakan untuk menghapuskan mereka. Mari kita dequeue mereka dari barisan. 

Jadi sama untuk pop, yang merupakan jenis daripada analog ini untuk susunan, dequeue perlu menerima penunjuk kepada queue-- sekali lagi, melainkan jika ia di peringkat global diisytiharkan. Sekarang kita ingin menukar lokasi bahagian depan barisan. Ini adalah di mana ia semacam datang ke dalam bermain, yang berubah-ubah hadapan, kerana sekali kita mengeluarkan elemen, kita mahu untuk bergerak ke elemen tertua depan. 

Kemudian kita mahu untuk mengurangkan saiz barisan, dan kemudian kita mahu kembali nilai yang telah dikeluarkan dari barisan. Sekali lagi, kita tidak mahu hanya membuangnya. Kami mungkin akan mengeluarkan dari queue-- kita berada dequeuing ia kerana kita mengambil berat mengenainya. Oleh itu, kita mahu fungsi ini untuk kembali elemen data nilai jenis. Sekali lagi, dalam kes ini, nilai integer. 

Jadi sekarang mari kita dequeue sesuatu. Mari kita keluarkan unsur dari barisan. Jika kita mengatakan int x sama & q, Ampersand q-- sekali lagi bahawa adalah penunjuk kepada q data ini structure-- apa unsur akan dapat dequeued? Dalam kes ini, kerana ia adalah yang pertama , keluar dahulu struktur data, FIFO, perkara pertama yang kita dimasukkan ke dalam ini barisan adalah 28, dan sebagainya dalam kes ini, kita akan mengambil 28 daripada barisan, tidak 19, iaitu apa yang kita akan lakukan jika ini adalah timbunan. Kami akan mengambil 28 daripada barisan. 

Sama dengan apa yang kita lakukan dengan timbunan, kita tidak benar-benar akan memadam 28 dari barisan itu sendiri, kita hanya akan jenis daripada berpura-pura ia tidak ada. Jadi ia akan tinggal di sana dalam ingatan, tetapi kami hanya akan jenis mengabaikannya dengan menggerakkan kedua-dua bidang lain data q kami struktur. Kami akan menukar bahagian depan. Q.front kini akan 1, kerana itu adalah sekarang unsur tertua kita ada dalam kita barisan, kerana kita telah pun dikeluarkan 28, yang merupakan bekas elemen yang paling lama. 

Dan sekarang, kita ingin menukar saiz barisan dua unsur dan bukannya tiga. Sekarang ingat sebelum ini saya katakan apabila kita ingin menambah unsur-unsur untuk barisan, kami memasukkannya ke dalam lokasi yang mudah yang adalah jumlah depan dan saiz. Jadi dalam kes ini, kami masih meletakkan itu, elemen seterusnya dalam barisan, ke lokasi mudah 3, dan kita akan melihat bahawa dalam satu saat. 

Jadi, sekarang kita telah dequeued kami Elemen pertama dari barisan. Mari kita buat sekali lagi. Mari kita keluarkan lain unsur dari barisan. Dalam kes itu, yang tertua semasa elemen adalah lokasi mudah 1. Itulah yang q.front memberitahu kita. Bahawa kotak hijau memberitahu kita bahawa itulah elemen yang paling lama. Dan sebagainya, x akan menjadi 33. Kami akan hanya jenis lupa bahawa 33 wujud dalam array, dan kami akan mengatakan bahawa sekarang, elemen baru tertua dalam barisan adalah di pelbagai lokasi 2, dan saiz barisan, bilangan unsur kita ada dalam barisan, adalah 1. Sekarang mari kita enqueue sesuatu, dan saya semacam memberikan ini jauh kedua yang lalu, tetapi jika kita mahu meletakkan 40 ke dalam giliran, di mana adalah 40 akan pergi? Baik kita telah meletakkan ia dalam q.front ditambah barisan saiz, dan jadi ia masuk akal untuk sebenarnya untuk meletakkan 40 di sini. Sekarang perhatikan bahawa pada satu ketika, kita akan untuk sampai ke akhir pelbagai kami di dalam q, tetapi itu pudar 28 dan 33-- mereka benar-benar, dari segi teknikal kawasan lapang, bukan? Dan sebagainya, kita boleh eventually-- bahawa peraturan untuk menambah kedua-dua together-- kami mungkin akhirnya perlu arena dengan saiz kapasiti supaya kita boleh membalut di sekitar. 

Jadi, jika kita dapat unsur nombor 10, jika kita menggantikannya dalam bilangan elemen 10, kita akan sebenarnya memasukkannya ke dalam pelbagai lokasi 0. Dan jika kami pergi ke lokasi location-- maafkan saya, Kami tambahi mereka bersama-sama, dan kami mendapat ke nombor 11 adalah di mana kita perlu meletakkan itu, yang tidak wujud dalam array-- ini ia akan keluar dari batas. Kita boleh arena oleh 10 dan meletakkan dalam lokasi mudah 1. Jadi itulah bagaimana beratur bekerja. Mereka sentiasa akan pergi dari kiri ke kanan dan mungkin membungkus. Dan anda tahu bahawa mereka jika saiz penuh, bahawa kotak merah, menjadi sama dengan keupayaan. Dan jadi selepas kami telah menambah 40 kepada giliran, akan apa yang perlu kita lakukan? Nah, elemen yang paling tua dalam barisan masih 19, jadi kami tidak mahu berubah bahagian depan barisan, tetapi kini kita mempunyai dua unsur-unsur dalam barisan, dan dengan itu kita mahu meningkatkan saiz kami 1-2. 

Yang cukup banyak dengan bekerja dengan beratur berdasarkan lokasi-, dan sama dengan timbunan, terdapat juga cara yang untuk melaksanakan satu barisan sebagai senarai berpaut. Sekarang jika jenis struktur data ini kelihatan biasa kepada anda, ia adalah. Ia bukan senarai secara tunggal berkaitan, ia adalah senarai duanya adalah terpakai dikaitkan. Dan kini, sebagai diketepikan, ia adalah sebenarnya mungkin untuk melaksanakan barisan sebagai satu senarai secara tunggal dikaitkan, tetapi Saya rasa dari segi visualisasi, ia sebenarnya mungkin membantu untuk melihat ini sebagai satu senarai duanya adalah terpakai dikaitkan. Tetapi ia pasti mungkin untuk melakukan ini sebagai satu senarai secara tunggal berkaitan. 

Jadi mari kita lihat apa ini mungkin kelihatan seperti. Jika kita mahu enquue-- jadi sekarang, sekali lagi kami beralih kepada berpaut-senarai model berpangkalan di sini. Jika kita mahu enqueue, kita mahu untuk menambah elemen baru, baik apa yang perlu kita lakukan? Well, pertama sekali, kerana kami menambah hingga akhir dan mengeluarkan dari bermula, kita mungkin mahu mengekalkan petunjuk kepada kedua-dua kepala dan ekor senarai dikaitkan? Ekor yang satu lagi istilah untuk akhir senarai berkaitan, elemen terakhir dalam senarai berkaitan. Dan ini akan mungkin, sekali lagi, memberi manfaat kepada kami jika mereka adalah pembolehubah global. Tetapi sekarang jika kita mahu untuk menambah yang baru unsur apa yang kita perlu lakukan? Apa yang kita hanya [? malak?] atau dinamik memperuntukkan nod baru kami untuk diri kita sendiri. Dan kemudian, sama seperti ketika kita menambah apa-apa elemen untuk senarai kita duanya adalah terpakai dikaitkan, hanya perlu menyusun daripada- ketiga-tiga langkah terakhir di sini hanya tentang menggerakkan petunjuk dengan cara yang betul supaya elemen akan ditambah ke rantaian tanpa melanggar rantai atau membuat beberapa jenis kesilapan atau mempunyai beberapa jenis kemalangan berlaku di mana kita tidak sengaja anak yatim beberapa unsur-unsur barisan kami. Berikut adalah apa yang ini mungkin kelihatan seperti. Kami mahu menambah unsur 10 hingga akhir barisan ini. Jadi elemen tertua di sini diwakili oleh kepala. Itu perkara yang pertama kita meletakkan ke dalam barisan andaian ini di sini. Dan ekor, 13, adalah yang paling baru-baru ini menambah unsur. Dan jadi jika kita mahu enqueue 10 ke dalam barisan ini, kita mahu untuk meletakkan ia selepas 13. Dan dengan itu kita akan secara dinamik memperuntukkan ruang untuk nod baru dan periksa null memastikan kita tidak mempunyai kegagalan memori. Kemudian kita akan meletakkan 10 ke nod itu, dan kini kita perlu berhati-hati mengenai cara kami menyusun petunjuk jadi kami tidak memecahkan rantai. 

Kita boleh menetapkan bidang 10 sebelum ini untuk menunjukkan kembali ke ekor yang lama, dan sejak '10 akan menjadi ekor baru pada satu ketika dengan masa yang semua ini rantai yang berkaitan, apa-apa yang akan datang selepas 10 sekarang. Dan sebagainya penunjuk berikut 10 ini akan menunjukkan kepada batal, dan kemudian selepas kita melakukan ini, selepas kami telah disambungkan 10 ke belakang untuk rantai, kita boleh mengambil kepala lama, atau, alasan saya, ekor lama barisan. Hujung lama barisan, 13, dan membuat ia menunjukkan 10. Dan sekarang, pada masa ini, kami mempunyai enqueued nombor 10 ke dalam barisan ini. Apa yang kita perlu lakukan sekarang hanya menggerakkan ekor untuk menghala ke 10 dan bukannya hingga 13. 

Dequeuing sebenarnya hampir sama dengan bermunculan dari timbunan yang dilaksanakan sebagai senarai berpaut jika anda telah melihat video susunan itu. Apa yang kita perlu lakukan adalah bermula pada bermula, cari elemen kedua, membebaskan elemen pertama, dan kemudian bergerak kepala untuk menunjukkan elemen kedua. Mungkin lebih baik untuk menggambarkan ia hanya untuk menjadi tambahan yang jelas mengenainya. Jadi inilah barisan kita lagi. 12 adalah unsur yang paling tua dalam barisan kita, kepala. 10 adalah unsur yang terbaru dalam barisan kami, ekor kami. 

Dan supaya apabila kita hendak untuk dequeue elemen, kita mahu mengeluarkan unsur yang paling lama. Jadi, apa yang kita lakukan? Baik kita menetapkan penunjuk penyusuran yang bermula di kepala, dan kita bergerak ia supaya ia mata kepada elemen kedua ini queue-- sesuatu dengan mengatakan trav sama trav arrow akan datang, sebagai contoh, akan bergerak trav sana untuk menunjukkan 15, yang, selepas kami dequeue 12, atau selepas kita mengeluarkan 12, akan menjadi elemen yang ketika itu yang paling lama. 

Sekarang kami mempunyai pegangan ke atas yang pertama unsur melalui kepala penunjuk dan elemen kedua melalui trav penunjuk. Kita boleh kepala kini bebas, dan kemudian kita boleh berkata apa-apa datang sebelum 15 lagi. Oleh itu, kita boleh menukar 15 yang lepas penunjuk kepada menunjukkan batal, dan kita hanya menggerakkan kepala ke atas. Dan kita pergi. Sekarang kita telah berjaya dequeued 12, dan sekarang kita mempunyai satu lagi barisan 4 elemen. Yang cukup banyak semua ada untuk beratur, kedua-dua lokasi berasaskan dan dihubungkan-senarai berasaskan. Saya Doug Lloyd. Ini adalah CS 50.