DOUG LLOYD: Baiklah, supaya oleh titik ini anda mungkin cukup biasa dengan pameran dan senarai berkaitan yang manakah utama kedua-dua struktur data yang kita ada bercakap tentang untuk menyimpan set data jenis data yang sama yang dianjurkan. Sekarang kita akan bercakap kira-kira beberapa variasi pada tatasusunan dan senarai berkaitan. Dalam video ini kita akan untuk bercakap mengenai susunan. Secara khusus kita akan bercakap mengenai struktur data dipanggil timbunan. Ingat dari perbincangan sebelum tentang petunjuk dan ingatan, bahawa timbunan juga menamakan untuk segmen memori mana statik diisytiharkan memori memory-- anda nama, pembolehubah yang anda namakan, et sebagainya dan fungsi bingkai yang kita juga bingkai tindanan panggilan wujud. Jadi ini adalah satu struktur data stack bukan segmen timbunan ingatan. OKAY. 

Tetapi apa yang timbunan? Jadi ia adalah cukup banyak hanya sejenis khas struktur yang mengekalkan data dalam cara yang dianjurkan. Dan ada dua sangat cara yang biasa untuk melaksanakan susunan menggunakan dua struktur data yang kita sudah biasa dengan, tatasusunan dan senarai berkaitan. Apa yang membuatkan khas timbunan adalah cara di mana kita meletakkan maklumat ke dalam timbunan, dan cara kita mengeluarkan maklumat dari timbunan. Khususnya dengan susunan peraturan adalah hanya yang paling baru-baru ini menambah unsur boleh dikeluarkan. 

Jadi berfikir tentang hal itu seolah-olah ia adalah timbunan. Kami cerucuk maklumat di atas dengan sendirinya, dan hanya perkara yang di atas longgokan boleh dikeluarkan. Kita tidak boleh mengeluarkan perkara yang di bawah kerana segala-galanya akan runtuh dan goyang. Oleh itu, kita benar-benar sedang membina timbunan yang kita kemudian perlu mengeluarkan sekeping oleh sekeping. Oleh kerana itu kita biasa merujuk kepada timbunan sebagai struktur LIFO, bertahan dalam, dahulu. LIFO, bertahan, keluar dahulu. 

Demikian kerana sekatan ini di bagaimana maklumat boleh ditambah kepada dan dikeluarkan daripada timbunan, ada benar-benar hanya dua perkara yang boleh kita lakukan dengan timbunan. Kami boleh menolak, yang merupakan jangka kita gunakan untuk menambah elemen baru ke bahagian atas timbunan, atau jika timbunan tidak wujud dan kami membuatnya dari awal, mewujudkan timbunan di tempat pertama akan menolak. Dan kemudian pop, itu jenis CS jangka yang kami gunakan untuk membuang yang paling baru elemen ditambah dari bahagian atas timbunan. 

Jadi, kita akan melihat kepada kedua-dua pelaksanaan, kedua-dua lokasi berdasarkan dan senarai dikaitkan berasaskan. Dan kita akan mulakan dengan lokasi berasaskan. Jadi di sini adalah idea asas apa struktur data tindanan pelbagai berdasarkan akan kelihatan seperti. Kami mempunyai definisi ditaip di sini. Di dalam yang kita ada dua orang ahli atau medan struktur. Kami mempunyai array. Dan sekali lagi saya menggunakan sewenang-wenangnya Nilai jenis data. 

Jadi ini boleh menjadi apa-apa jenis data, int char atau beberapa data lain jenis yang anda dibuat sebelum ini. Oleh itu, kita mempunyai pelbagai kapasiti saiz. Kapasiti sedang paun ditakrifkan berterusan, mungkin di tempat lain dalam fail kami. Jadi notis sudah dengan khusus ini pelaksanaan kita bounding diri kita sendiri seperti yang biasanya kes dengan array, yang kita tidak boleh secara dinamik mengubah saiz, di mana ada sebilangan unsur-unsur maksimum yang kita boleh dimasukkan ke dalam timbunan kami. Dalam kes ini ia adalah elemen keupayaan. 

Kami juga mengesan bahagian atas timbunan. Apa unsur adalah yang paling Baru-baru ini ditambah kepada timbunan? Dan dengan itu kita mengesan bahawa dalam bahagian pembolehubah dipanggil. Dan semua ini mendapat dibungkus bersama-sama ke dalam jenis data baru yang dikenali sebagai timbunan. Dan sekali kita dicipta jenis data baru ini kita boleh memperlakukannya seperti apa-apa jenis data yang lain. Kita boleh mengisytiharkan timbunan s, sama seperti kita boleh melakukan int x, atau char y. Dan apabila kita katakan timbunan s, juga apa yang berlaku adalah kita akan mendapat satu set memori yang diperuntukkan untuk kita. 

Dalam kapasiti kes ini Saya telah nampaknya telah memilih adalah 10 kerana saya telah mendapat satu pembolehubah tunggal jenis timbunan yang mengandungi dua medan ingat. Pelbagai, dalam kes ini akan menjadi pelbagai integer seperti yang berlaku di kebanyakan contoh saya. Dan satu lagi pembolehubah integer mampu menyimpan bahagian atas, yang paling baru ditambah elemen untuk timbunan. Jadi, satu timbunan tunggal daripada apa yang kita hanya ditakrifkan kelihatan seperti ini. Ia adalah sebuah kotak yang mengandungi pelbagai 10 apa akan menjadi bilangan bulat dalam kes ini dan satu lagi pembolehubah integer terdapat dalam hijau untuk menunjukkan bahagian atas timbunan. 

Untuk menetapkan bahagian atas timbunan kita hanya mengatakan s.top. Itulah bagaimana kita mengakses bidang penarikan balik struktur. s.top sama dengan 0 berkesan melakukan ini untuk timbunan kami. Jadi sekali lagi kita mempunyai dua operasi yang kita boleh lakukan sekarang. Kami boleh menolak dan kita boleh pop. Mari kita mulakan dengan push. Sekali lagi, menolak adalah menambah yang baru elemen ke atas timbunan. 

Jadi apa yang perlu kita lakukan dalam pelbagai ini pelaksanaan berasaskan? Baik dalam umum fungsi push akan untuk perlu menerima penunjuk kepada timbunan. Oleh sebab itu, kedua dan berfikir mengenainya. Mengapa kita akan mahu menerima penunjuk kepada tindanan? Balik dari video sebelumnya skop pembolehubah dan petunjuk, apa yang akan berlaku jika kita hanya menghantar timbunan, s sebaliknya dalam sebagai parameter? Apa yang sebenarnya akan diluluskan di sana? Ingat kami mewujudkan satu salinan apabila kita lulus ke fungsi kecuali kita menggunakan petunjuk. Dan supaya fungsi ini menolak keperluan untuk menerima penunjuk kepada timbunan supaya kita benar-benar ingin berubah timbunan kami berhasrat untuk berubah. 

Perkara push lain mungkin mahu terima ialah elemen data nilai jenis. Dalam kes ini, sekali lagi, integer yang kita akan menambah bahagian atas timbunan. Jadi kami mempunyai dua parameter kami. Apa yang kita akan sekarang lakukan dalam tolak? Nah, hanya, kami hanya akan menambah bahawa elemen ke atas timbunan dan kemudian menukar mana bahagian atas tindanan adalah, bahawa s dot nilai tertinggi. Jadi ini adalah apa fungsi pengisytiharan untuk menolak mungkin kelihatan seperti dalam berdasarkan pelbagai pelaksanaan. 

Sekali lagi ia tidak peraturan keras dan cepat bahawa anda boleh menukar ini dan mempunyai ia berbeza dalam cara yang berbeza. Mungkin s diisytiharkan di peringkat global. Dan supaya anda tidak perlu untuk lulus ia adalah sebagai parameter. Ini sekali lagi hanya kes umum untuk menolak. Dan ada yang berbeza cara-cara untuk melaksanakannya. Tetapi dalam kes ini kami push akan mengambil dua hujah, penunjuk kepada timbunan dan elemen data nilai jenis, integer dalam kes ini. 

Oleh itu, kita mengisytiharkan s, kita berkata s.top sama dengan 0. Sekarang mari kita menolak nombor 28 ke dalam tindanan. Baik apa maksudnya? Baik pada masa ini atas timbunan adalah 0. Dan supaya apa yang pada dasarnya akan berlaku adalah kita akan melekat jumlah 28 ke dalam pelbagai lokasi 0. Cukup mudah, betul, bahawa adalah bahagian atas dan sekarang kita baik untuk pergi. Dan maka kita perlu mengubah apa yang bahagian atas timbunan akan. Supaya masa akan datang kita menolak unsur dalam, kita akan menyimpannya di lokasi mudah, mungkin tidak 0. Kami tidak mahu menulis ganti apa yang kita hanya meletakkan di sana. Dan dengan itu kita hanya akan bergerak bahagian atas untuk 1. Yang mungkin masuk akal. 

Sekarang jika kita mahu meletakkan elemen lain ke dalam tindanan, mengatakan bahawa kita mahu untuk menolak 33, baik sekarang kami hanya akan mengambil 33 dan meletakkannya di nombor lokasi mudah 1, dan kemudian menukar bahagian atas kami stack menjadi array beberapa lokasi dua. Jadi, jika pada masa akan datang kita mahu menolak unsur ke dalam tindanan, ia akan dimasukkan ke dalam pelbagai lokasi 2. Dan mari kita buat satu masa yang lanjut. Kami akan menolak 19 off dari susunan. Kami akan meletakkan 19 dalam pelbagai lokasi 2 dan menukar bahagian atas timbunan kami menjadi lokasi mudah 3 jadi jika kali kita seterusnya perlu membuat push kita baik untuk pergi. 

OK, jadi yang yang menolak secara ringkas. Bagaimana pula muncul? Jadi pop adalah jenis rakan untuk menolak. Ia adalah bagaimana kita mengeluarkan data dari timbunan. Dan dalam keperluan pop umum untuk melakukan yang berikut. Ia perlu menerima penunjuk kepada timbunan, sekali lagi dalam kes umum. Dalam beberapa kes lain yang anda mungkin telah mengisytiharkan timbunan di peringkat global, di mana anda tidak perlu untuk lulus kerana ia telah mempunyai akses kepada maklumat itu sebagai pembolehubah global. Tetapi apa lagi yang perlu kita lakukan? Baik kita menokok bahagian atas timbunan di tolak, jadi kita mungkin akan mahu untuk susutan bahagian atas timbunan dalam pop, bukan? Dan kemudian tentu kami juga akan mahu untuk mengembalikan nilai yang kita keluarkan. Jika kita menambah unsur-unsur, kita mahu untuk mendapatkan unsur-unsur di kemudian hari, kita mungkin sebenarnya mahu menyimpan mereka, maka Kami jangan hanya memadam mereka dari stack dan kemudian berbuat apa-apa dengan mereka. Secara umumnya jika kita menolak dan muncul di sini kami ingin menyimpan ini maklumat dengan cara yang bermakna dan supaya ia tidak membuat masuk akal untuk hanya membuangnya. Jadi fungsi ini perlu mungkin mengembalikan nilai kepada kami. 

Jadi ini adalah apa deklarasi untuk pop mungkin kelihatan seperti terdapat di sebelah kiri atas. Fungsi ini pulangan data nilai jenis. Sekali lagi kita telah menggunakan bilangan bulat di seluruh. Dan ia menerima penunjuk kepada timbunan sebagai hujah bicaranya atau parameter tunggal. Jadi apa yang pop akan lakukan? Katakan kita mahu sekarang pop unsur luar s. Jadi ingat saya berkata bahawa susunan yang terakhir , keluar dahulu, LIFO data struktur. Unsur yang akan dikeluarkan daripada timbunan? Adakah anda rasa 19? Kerana anda akan menjadi betul. 19 adalah elemen terakhir kami menambah kepada stack apabila kita telah menolak unsur-unsur di atas, dan sebagainya ia akan yang pertama elemen yang akan dikeluarkan. Ia seolah-olah kita berkata 28, dan kemudian kita meletakkan 33 di atas itu, dan kami meletakkan 19 di atas itu. Satu-satunya elemen yang boleh kita ambil kira ialah 19. 

Sekarang dalam rajah di sini apa yang saya lakukan umpama dipadam 19 dari array. Bukan itu sebenarnya apa yang kita akan lakukan. Kami hanya akan jenis daripada berpura-pura ia tidak ada. Ia masih terdapat dalam bahawa lokasi memori, tetapi kami hanya akan mengabaikannya dengan menukar bahagian atas timbunan kami daripada menjadi 3-2. Jadi jika kita kini menolak unsur lain ke dalam tindanan, ia lebih akan menulis 19. 

Tetapi jangan kita pergi melalui masalah untuk memotong 19 dari timbunan. Kami hanya boleh berpura-pura ia tidak ada. Untuk tujuan timbunan ia pergi jika kita menukar bahagian atas untuk menjadi 2 bukan 3. Baiklah, jadi yang cukup banyak ia. Itu sahaja yang perlu kita lakukan pop unsur luar. Mari kita buat sekali lagi. Jadi saya telah menekankan dalam merah di sini untuk menunjukkan kami membuat panggilan lain. Kami akan melakukan perkara yang sama. 

Jadi apa yang akan berlaku? Nah, kita akan menyimpan 33 dalam x dan kita akan untuk menukar bahagian atas timbunan untuk 1. Supaya jika kita sekarang untuk menolak satu elemen ke dalam timbunan yang kami nak buat sekarang, apa yang akan berlaku adalah kita akan menulis ganti pelbagai nombor lokasi 1. Supaya 33 yang semacam dibiarkan belakang yang kita hanya berpura-pura tidak ada lagi, kami hanya akan untuk memukul berkali-kali dan meletakkan 40 sana. Kemudian sudah tentu, sejak kami membuat tolakan, kita akan kenaikan yang atas tindanan 1-2 supaya jika kita menambah elemen lain IA AKAN pergi ke dalam pelbagai lokasi nombor dua. 

Sekarang senarai berkaitan adalah satu lagi cara untuk melaksanakan susunan. Dan jika definisi ini ke atas skrin di sini kelihatan biasa kepada anda, ia adalah kerana ia kelihatan hampir betul-betul sama, sebenarnya, ia cukup banyak betul-betul sama sebagai satu senarai secara tunggal berkaitan, jika anda ingat dari perbincangan kita tentang secara tunggal dikaitkan senarai dalam video lain. Satu-satunya sekatan di sini adalah untuk kita sebagai pengaturcara, kami tidak dibenarkan memasukkan atau memadam secara rawak dari senarai secara tunggal dikaitkan mana kita sebelum ini boleh lakukan. Hanya sekarang kita boleh memasukkan dan memotong daripada depan atau bahagian atas berkaitan senarai. Itu benar-benar satu-satunya perbezaan walaupun. Ini adalah sebaliknya senarai secara tunggal berkaitan. Ia hanya sekatan menggantikan pada diri kita sendiri sebagai pengaturcara yang perubahan ke dalam timbunan. 

Peraturan di sini adalah untuk sentiasa mengekalkan penunjuk kepada ketua senarai berpaut. Ini sudah tentu yang secara umumnya peraturan penting pertama. Untuk senarai secara tunggal dikaitkan bagaimanapun anda hanya perlu penunjuk kepada kepala untuk mempunyai yang rantaian dapat merujuk kepada setiap elemen lain dalam senarai yang dipautkan. Tetapi ia adalah terutamanya penting dengan timbunan. Dan jadi secara amnya anda akan benar-benar mahu penunjuk ini menjadi berubah-ubah global. Ia mungkin akan menjadi lebih mudah dengan cara itu. Jadi apakah analog tolak dan pop? Betul. Jadi menolak lagi menambah elemen baru ke dalam tindanan. Dalam senarai berpaut yang bermakna kita akan mempunyai untuk mewujudkan nod baru bahawa kita akan menambah ke dalam senarai berkaitan, dan kemudian ikuti langkah-langkah berhati-hati yang kami telah menjelaskan sebelum ini dalam senarai secara tunggal dikaitkan dengan menambah kepada rantaian tanpa melanggar rantai dan kehilangan atau anak yatim-mana unsur-unsur senarai berkaitan. Dan itu pada dasarnya apa yang sedikit tompok teks terdapat meringkaskan. Dan mari kita lihat ia sebagai gambar rajah. 

Jadi di sini adalah senarai berpaut kami. Ia serentak mengandungi empat elemen. Dan yang lebih sempurna di sini adalah kami timbunan yang mengandungi empat elemen. Dan mari kita mengatakan bahawa kita kini mahu menolak item baru ke dalam tindanan ini. Dan kami ingin menolak yang baru barang yang nilai data adalah 12. Baik apa yang kita akan lakukan? Well pertama kita akan ruang malloc, dinamik memperuntukkan ruang untuk nod baru. Dan sudah tentu serta-merta selepas kita membuat panggilan malloc kita sentiasa pastikan untuk memeriksa null, kerana jika kami mendapat null kembali terdapat beberapa jenis masalah. Kami tidak mahu dereference null yang penunjuk atau anda akan mengalami kesalahan seg. Yang tidak baik. Oleh itu, kita malloced nod. Kita akan menganggap kita telah mempunyai kejayaan di sini. Kami akan meletakkan 12 ke dalam medan data nod itu. Sekarang jangan kamu ingat yang mana satu petunjuk kami bergerak yang akan datang supaya kita tidak memecahkan rantai? Kami mempunyai beberapa pilihan di sini tetapi satu-satunya yang akan selamat adalah untuk menetapkan berita penunjuk sebelah mata kepada kepala lama dalam senarai atau apa yang tidak lama lagi akan menjadi kepala lama senarai. Dan kini bahawa semua kami unsur-unsur yang dirantai bersama-sama, kita hanya boleh bergerak senarai untuk menunjukkan ke tempat yang sama yang tidak baru. Dan kami kini berkesan ditolak yang elemen baru ke hadapan timbunan. 

Pop kami hanya mahu memadam bahawa unsur pertama. Dan sebagainya pada dasarnya apa kita perlu lakukan di sini, juga kita perlu mencari elemen kedua. Akhirnya yang akan menjadi baru kepala selepas kami memadam yang pertama. Oleh itu, kita hanya perlu bermula dari mulanya, bergerak satu ke hadapan. Apabila kami telah mendapat memegang pada satu ke hadapan di mana kita kini kita boleh memadam yang pertama dengan selamat dan kemudian kita boleh menggerakkan kepala untuk menunjukkan bagaimana akibat penggal kedua dan kemudian sekarang adalah yang pertama selepas itu nod telah dipadam. 

Jadi sekali lagi, mengambil melihat ia sebagai gambar rajah kita mahu sekarang pop yang unsur off timbunan ini. Jadi, apa yang kita lakukan? Well kita pertama akan mewujudkan penunjuk baru yang akan untuk menghala ke tempat yang sama sebagai kepala. Kami akan bergerak satu kedudukan ke hadapan dengan berkata setaraf trav Trav berikut sebagai contoh, yang akan memajukan satu penunjuk trav kedudukan ke hadapan. Sekarang kita telah mendapat berpegang elemen pertama melalui senarai penunjuk dipanggil, dan Elemen kedua melalui penunjuk yang dipanggil trav, kita boleh memadam yang Elemen pertama dari timbunan tanpa kehilangan yang lain rantai kerana kita mempunyai cara untuk merujuk untuk elemen kedua hadapan dengan cara yang penunjuk dipanggil trav. 

Jadi sekarang kita boleh bebas nod tersebut. Kita boleh bebas senarai. Dan kemudian semua yang perlu kita lakukan sekarang ialah menggerakkan senarai ke titik ke tempat yang sama trav yang tidak, dan kami semacam kembali di mana kita bermula sebelum kita menolak 12 pada di tempat pertama, betul. Ini betul-betul di mana kita berada. Kami mempunyai ini timbunan empat unsur. Kami telah menambah kelima. Kami menolak kelima elemen pada, dan kemudian kita muncul yang baru elemen ditambah kembali off. 

Itu benar-benar cukup banyak semua ada susunan. Anda boleh melaksanakannya kerana tatasusunan. Anda boleh melaksanakannya kerana senarai berkaitan. Terdapat, sudah tentu, lain cara-cara untuk melaksanakannya juga. Pada asasnya sebab kita akan menggunakan susunan adalah untuk mengekalkan data dalam apa-apa cara bahawa yang paling baru-baru ini berkata elemen adalah perkara pertama yang kami akan mahu kembali. Saya Doug Lloyd, ini adalah cs50.