Doug LLOYD: Baiklah, sehingga pada titik ini Anda mungkin cukup familiar dengan array dan daftar terkait yang merupakan dua utama struktur data kita sudah berbicara tentang untuk menjaga set Data dari jenis data yang sama terorganisir. Sekarang kita akan berbicara tentang beberapa variasi pada array dan daftar terkait. Dalam video ini kita akan untuk berbicara tentang tumpukan. Secara khusus kita akan berbicara tentang struktur data yang disebut stack. Ingat dari diskusi sebelumnya tentang pointer dan memori, bahwa tumpukan juga nama untuk segmen memori mana statis dideklarasikan memori memory-- yang Anda nama, variabel yang Anda nama, et sebagainya dan fungsi frame yang kami juga tumpukan frame panggilan ada. Jadi ini adalah struktur data stack tidak segmen tumpukan memori. OKE. 

Tapi apa stack? Sehingga cukup banyak hanya jenis khusus dari struktur yang mempertahankan data dalam cara yang terorganisir. Dan ada dua yang sangat cara umum untuk melaksanakan tumpukan menggunakan dua struktur data bahwa kita sudah akrab dengan, array dan daftar terkait. Apa yang membuat tumpukan khusus adalah cara di mana kita menaruh informasi ke dalam stack, dan cara kita menghapus informasi dari stack. Khususnya dengan tumpukan Aturan ini hanya yang paling baru-baru ini elemen ditambahkan dapat dihapus. 

Jadi pikirkan tentang hal itu seolah-olah itu stack. Kami menumpuk informasi di atas itu sendiri, dan hanya hal di atas tumpukan dapat dihapus. Kita tidak dapat menghapus hal di bawahnya karena segala sesuatu yang lain akan runtuh dan jatuh. Jadi kita benar-benar sedang membangun tumpukan yang kita kemudian harus menghapus sepotong demi sepotong. Karena ini kita sering merujuk untuk stack sebagai struktur LIFO, bertahan di, keluar pertama. LIFO, bertahan, keluar pertama. 

Jadi karena pembatasan ini pada bagaimana informasi dapat ditambahkan ke dan dihapus dari tumpukan, ada benar-benar hanya ada dua hal yang dapat kita lakukan dengan tumpukan. Kita dapat mendorong, yang merupakan istilah yang kita gunakan untuk menambahkan elemen baru ke atas tumpukan, atau jika stack tidak ada dan kami menciptakan dari awal, menciptakan tumpukan di tempat pertama akan mendorong. Dan kemudian pop, itulah semacam CS istilah yang kita gunakan untuk menghapus yang paling baru menambahkan elemen dari puncak stack. 

Jadi kita akan melihat kedua implementasi, baik array yang berdasarkan dan daftar link berbasis. Dan kita akan mulai dengan berbagai berbasis. Jadi, inilah ide dasar dari apa yang struktur data stack array yang berdasarkan akan terlihat seperti. Kami memiliki definisi diketik di sini. Dalam bahwa kita memiliki dua anggota atau bidang struktur. Kami memiliki sebuah array. Dan lagi aku menggunakan sewenang-wenang nilai tipe data. 

Jadi ini bisa menjadi jenis data, int Char atau beberapa data lainnya ketik sebelumnya Anda buat. Jadi kita memiliki sebuah array ukuran kapasitas. Kapasitas yang pon didefinisikan konstan, mungkin di tempat lain dalam file kami. Jadi melihat sudah dengan khusus ini implementasi kita berlari diri seperti biasanya kasus dengan array, yang kita tidak bisa mengubah ukuran dinamis, di mana ada sejumlah elemen maksimum yang kita bisa dimasukkan ke dalam tumpukan kami. Dalam hal ini itu unsur kapasitas. 

Kami juga melacak bagian atas tumpukan. Apa elemen yang paling baru-baru ini ditambahkan ke stack? Dan jadi kami melacak yang dalam variabel yang disebut atas. Dan semua ini akan dibungkus bersama-sama menjadi tipe data baru yang disebut stack. Dan setelah kita buat tipe data baru kita bisa memperlakukannya seperti jenis data lainnya. Kita dapat mendeklarasikan tumpukan s, seperti kita bisa melakukan int x, y atau arang. Dan ketika kita mengatakan tumpukan s, baik apa yang terjadi adalah kita mendapatkan satu set memori disisihkan bagi kita. 

Dalam kapasitas hal ini Saya tampaknya telah memutuskan adalah 10 karena saya punya variabel tunggal jenis tumpukan yang berisi dua bidang ingat. Array, dalam hal ini akan menjadi sebuah array bilangan bulat seperti halnya di sebagian besar contoh saya. Dan variabel integer lain mampu menyimpan atas, paling baru ditambahkan elemen ke stack. Jadi satu tumpukan tunggal apa yang kita hanya didefinisikan terlihat seperti ini. Ini sebuah kotak yang berisi array 10 apa akan bilangan bulat dalam kasus ini dan variabel lain bilangan bulat ada di green untuk menunjukkan bagian atas tumpukan. 

Untuk mengatur atas tumpukan kita hanya mengatakan s.top. Itulah cara kita mengakses bidang penarikan struktur. s.top sama dengan 0 efektif melakukan hal ini untuk tumpukan kami. Jadi sekali lagi kita memiliki dua operasi bahwa kita dapat melakukan sekarang. Kita dapat mendorong dan kita bisa pop. Mari kita mulai dengan push. Sekali lagi, mendorong adalah menambahkan baru elemen ke atas tumpukan. 

Jadi apa yang perlu kita lakukan di array ini pelaksanaan berdasarkan? Baik di umum fungsi push akan perlu untuk menerima pointer ke stack. Sekarang mengambil kedua dan berpikir tentang hal itu. Mengapa kita ingin menerima pointer ke stack? Ingat dari video sebelumnya pada lingkup variabel dan petunjuk, apa yang akan terjadi jika kita hanya mengirim stack, s lebih dalam sebagai parameter? Apa yang sebenarnya akan berlalu di dalam sana? Ingat kita sedang menciptakan salinan ketika kita lulus ke fungsi kecuali kita menggunakan pointer. Dan fungsi ini mendorong kebutuhan untuk menerima pointer ke stack sehingga kita benar-benar mengubah stack kami berniat untuk berubah. 

Push Hal lain mungkin ingin menerima adalah elemen data jenis nilai. Dalam hal ini, sekali lagi, integer yang kita akan menambah atas tumpukan. Jadi kita punya dua parameter kami. Apa yang akan kita sekarang lakukan dalam mendorong? Nah, sederhana, kami hanya akan menambahkan bahwa unsur ke atas tumpukan dan kemudian mengubah mana bagian atas stack adalah, bahwa s dot nilai atas. Jadi ini adalah apa fungsi deklarasi untuk push mungkin terlihat seperti dalam -array berbasis implementasi. 

Sekali lagi ini bukan aturan keras dan cepat Anda bisa mengubah ini dan memiliki itu bervariasi dalam cara yang berbeda. Mungkin s dinyatakan secara global. Dan sehingga Anda bahkan tidak perlu untuk lulus itu sebagai parameter. Ini lagi hanya kasus umum untuk push. Dan ada yang berbeda cara untuk menerapkannya. Tapi dalam kasus ini kami push akan mengambil dua argumen, pointer ke stack dan elemen data nilai jenis, integer pada kasus ini. 

Jadi kami menyatakan, kami kata s.top sama dengan 0. Sekarang mari kita mendorong nomor 28 ke stack. Nah apa artinya? Nah saat ini atas tumpukan adalah 0. Dan jadi apa dasarnya akan terjadi adalah kita akan tetap nomor 28 ke dalam array lokasi 0. Cukup sederhana, tepat, yang adalah atas dan sekarang kami baik untuk pergi. Dan kemudian kita perlu mengubah apa bagian atas tumpukan akan. Sehingga waktu berikutnya kami mendorong elemen di, kita akan menyimpannya dalam Lokasi array, mungkin tidak 0. Kami tidak ingin menimpa apa yang baru saja kita diletakkan di sana. Dan jadi kami hanya akan memindahkan atas ke 1. Itu mungkin masuk akal. 

Sekarang jika kita ingin menempatkan elemen lain ke stack, mengatakan kami ingin mendorong 33, nah sekarang kita hanya akan mengambil 33 dan meletakkannya di nomor lokasi array yang 1, dan kemudian mengubah atas kami tumpukan menjadi berbagai lokasi nomor dua. Jadi jika lain kali kita ingin mendorong elemen ke stack, itu akan dimasukkan dalam array lokasi 2. Dan mari kita melakukan itu sekali lagi. Kami akan mendorong 19 off dari tumpukan. Kami akan menempatkan 19 dalam array lokasi 2 dan mengubah atas tumpukan kami menjadi berbagai lokasi 3 jadi jika waktu kita selanjutnya perlu membuat dorongan kami baik untuk pergi. 

OK, jadi yang mendorong singkatnya. Bagaimana bermunculan? Jadi popping adalah semacam mitra untuk mendorong. Ini bagaimana kita menghapus data dari stack. Dan dalam kebutuhan pop umum untuk melakukan hal berikut. Ini perlu menerima pointer ke tumpukan, lagi dalam kasus umum. Dalam beberapa kasus lain Anda mungkin telah menyatakan stack global, dalam hal ini Anda tidak perlu lulus di karena sudah memiliki akses ke sana sebagai variabel global. Tapi kemudian apa lagi yang perlu kita lakukan? Yah kami incrementing bagian atas tumpukan di push, jadi kita mungkin akan ingin untuk pengurangan atas tumpukan di pop, kan? Dan tentu saja kami juga akan ingin untuk mengembalikan nilai yang kita keluarkan. Jika kita menambahkan elemen, kita ingin untuk mendapatkan elemen keluar nanti, kita mungkin benar-benar ingin menyimpannya sehingga kita tidak hanya menghapus mereka dari stack dan kemudian melakukan apa-apa dengan mereka. Umumnya jika kita mendorong dan muncul di sini kita ingin menyimpan ini informasi dalam cara yang berarti dan sehingga tidak membuat akal untuk hanya membuangnya. Jadi fungsi ini harus mungkin mengembalikan nilai kepada kami. 

Jadi ini adalah apa deklarasi untuk pop mungkin terlihat seperti ada di bagian kiri atas. Fungsi kembali ini data jenis nilai. Sekali lagi kami sudah menggunakan bilangan bulat seluruh. Dan ia menerima pointer ke stack sebagai argumen sendiri atau parameter tunggal. Jadi apa yang pop akan lakukan? Katakanlah kita ingin sekarang pop elemen off s. Jadi ingat saya mengatakan bahwa tumpukan yang lalu , keluar pertama, LIFO struktur data. Yang elemen akan dihapus dari stack? Apakah Anda menebak 19? Karena Anda akan benar. 19 adalah elemen terakhir kami ditambahkan ke tumpukan ketika kami mendorong elemen pada, dan itu akan pertama elemen yang akan dihapus. Seolah-olah kita mengatakan 28, dan maka kita menempatkan 33 di atasnya, dan kami menempatkan 19 di atas itu. Satu-satunya elemen yang bisa kita ambil off 19. 

Sekarang dalam diagram di sini apa yang telah saya lakukan adalah semacam dihapus 19 dari array. Itu tidak benar-benar apa yang akan kita lakukan. Kami hanya akan jenis dari berpura-pura itu tidak ada. Itu masih ada di lokasi memori, tapi kami hanya akan mengabaikannya dengan mengubah atas tumpukan kami dari menjadi 3-2. Jadi jika kita sekarang mendorong elemen lain ke stack, itu lebih akan menulis 19. 

Tapi mari kita tidak pergi melalui kesulitan menghapus 19 dari stack. Kami hanya bisa berpura-pura itu tidak ada. Untuk tujuan tumpukan itu hilang jika kita mengubah atas menjadi 2 bukan 3. Baiklah, jadi itu cukup banyak itu. Itu semua yang perlu kita lakukan pop elemen off. Mari kita melakukannya lagi. Jadi saya sudah disorot dalam warna merah di sini untuk menunjukkan kita membuat panggilan lain. Kami akan melakukan hal yang sama. 

Jadi apa yang akan terjadi? Nah, kita akan menyimpan 33 di x dan kita akan untuk mengubah atas tumpukan untuk 1. Sehingga jika kita sekarang untuk mendorong sebuah elemen ke stack yang kami akan lakukan sekarang, apa yang akan terjadi adalah kita akan menimpa Array lokasi nomor 1. Sehingga 33 yang semacam tersisa balik bahwa kita hanya berpura-pura sudah tidak ada lagi, kita hanya akan untuk mengalahkan itu dan menempatkan 40 di sana sebagai gantinya. Dan tentu saja, karena kami membuat dorongan, kita akan kenaikan atas tumpukan 1-2 sehingga jika kita sekarang menambahkan elemen lain itu akan pergi ke berbagai lokasi nomor dua. 

Sekarang daftar terkait yang lain cara untuk menerapkan tumpukan. Dan jika definisi ini pada Layar sini tampak akrab bagi Anda, itu karena terlihat hampir persis sama, pada kenyataannya, itu cukup banyak adalah persis sama seperti daftar tunggal terkait, jika Anda ingat dari diskusi kami tunggal terkait daftar di video lain. Satu-satunya batasan di sini adalah bagi kita sebagai programmer, kita tidak diperbolehkan untuk memasukkan atau menghapus secara acak dari daftar sendiri-sendiri terkait yang kita sebelumnya bisa melakukan. Hanya sekarang kita dapat menyisipkan dan menghapus dari bagian depan atau bagian atas terkait daftar. Itu benar-benar satu-satunya Perbedaan sekalipun. Ini adalah jika daftar tunggal terkait. Ini hanya pembatasan mengganti pada diri kita sendiri sebagai programmer yang perubahan ke stack. 

Aturan di sini adalah untuk selalu menjaga pointer ke kepala linked list. Hal ini tentu saja umumnya aturan penting pertama. Untuk tunggal linked list tetap Anda hanya perlu pointer ke kepala dalam rangka untuk memiliki rantai dapat merujuk untuk setiap elemen lain dalam linked list. Tapi itu sangat penting dengan stack. Dan umumnya Anda akan benar-benar ingin pointer ini menjadi variabel global. Ini mungkin akan menjadi lebih mudah seperti itu. Jadi apa yang analog push dan pop? Benar. Jadi mendorong lagi adalah menambahkan elemen baru ke stack. Dalam daftar link yang berarti kita akan memiliki untuk membuat node baru yang kami akan menambahkan ke dalam daftar link, dan kemudian ikuti langkah-langkah hati-hati yang telah diuraikan sebelumnya kami dalam daftar sendiri-sendiri terkait dengan menambahkannya ke rantai tanpa melanggar rantai dan kehilangan atau orphaning setiap elemen dari linked list. Dan itu pada dasarnya apa yang sedikit gumpalan teks ada merangkum. Dan mari kita lihat itu sebagai sebuah diagram. 

Jadi, inilah daftar link kami. Ini bersamaan berisi empat elemen. Dan lebih sempurna inilah kami tumpukan mengandung empat unsur. Dan katakanlah kita sekarang ingin mendorong item baru ke stack ini. Dan kami ingin mendorong baru Item yang nilainya data 12. Nah apa yang akan kita lakukan? Yah pertama kita akan ruang malloc, dinamis mengalokasikan ruang untuk node baru. Dan tentu saja segera setelah kami membuat panggilan ke malloc kami selalu pastikan untuk memeriksa null, karena jika kita punya nol kembali ada semacam masalah. Kami tidak ingin dereference nol bahwa pointer atau Anda akan menderita kesalahan seg. Itu tidak baik. Jadi kita sudah malloced dari node. Kami akan menganggap kita sudah sukses di sini. Kita akan dimasukkan ke dalam 12 bidang data simpul tersebut. Sekarang Anda ingat yang pointer kami bergerak berikutnya sehingga kita tidak memutuskan rantai? Kami memiliki beberapa pilihan di sini tapi satu-satunya yang akan menjadi aman adalah untuk mengatur berita pointer di sebelah arahkan ke kepala lama daftar atau apa yang akan segera menjadi Kepala lama daftar. Dan sekarang bahwa semua kita elemen dirantai bersama-sama, kita hanya dapat memindahkan daftar ke titik ke tempat yang sama yang melakukan baru. Dan kita sekarang secara efektif mendorong elemen baru ke depan tumpukan. 

Pop kita hanya ingin menghapus elemen pertama. Dan pada dasarnya apa yang harus kita lakukan di sini, baik kita harus menemukan elemen kedua. Akhirnya yang akan menjadi baru kepala setelah kami hapus yang pertama. Jadi kita hanya perlu mulai dari awalnya, bergerak maju satu. Setelah kita punya pegangan pada satu maju dari mana kita saat ini kita dapat menghapus yang pertama aman dan kemudian kita bisa bergerak kepala untuk menunjuk ke apa adalah jabatan kedua dan kemudian sekarang adalah yang pertama setelah itu simpul telah dihapus. 

Jadi sekali lagi, mengambil melihat itu sebagai sebuah diagram kita ingin sekarang pop Unsur off dari tumpukan ini. Jadi apa yang kita lakukan? Yah kita pertama akan menciptakan pointer baru yang akan untuk menunjuk ke tempat yang sama sebagai kepala. Kami akan memindahkannya satu posisi maju dengan mengatakan equals trav trav berikutnya misalnya, yang akan memajukan satu trav pointer posisi depan. Sekarang kita punya berpegang pada elemen pertama melalui pointer disebut daftar, dan Elemen kedua melalui pointer disebut trav, kita dapat menghapus yang elemen pertama dari stack tanpa kehilangan sisanya rantai karena kita memiliki cara untuk merujuk untuk elemen kedua meneruskan dengan cara dari pointer disebut trav. 

Jadi sekarang kita bisa membebaskan simpul tersebut. Kita bisa membebaskan daftar. Dan kemudian semua yang perlu kita lakukan sekarang adalah memindahkan daftar ke titik ke tempat yang sama trav yang tidak, dan kami semacam kembali di mana kita mulai sebelum kita mendorong 12 pada di tempat pertama, tepat. Ini adalah persis di mana kita berada. Kami memiliki empat elemen ini stack. Kami menambahkan gol kelima. Kami mendorong kelima elemen, dan kemudian kita muncul yang paling baru menambahkan elemen mundur. 

Itu benar-benar cukup banyak semua yang ada untuk tumpukan. Anda dapat menerapkannya sebagai array. Anda dapat menerapkan mereka sebagai daftar terkait. Ada, tentu saja, lainnya cara untuk menerapkan mereka juga. Pada dasarnya alasan kita akan menggunakan tumpukan adalah untuk memelihara data sedemikian rupa yang paling baru ditambahkan Unsur adalah hal pertama yang kami akan ingin untuk kembali. Aku Doug Lloyd, ini CS50.