Doug LLOYD: Pekala, sen bu noktada öylesine Muhtemelen oldukça tanıdık diziler ve bağlantılı listelerle İki primer hangi veri yapıları biz ettik kümelerini tutmak için konuştuk benzer veri türleri veri düzenledi. Şimdi konuşmak için gidiyoruz varyasyonların bir çift hakkında diziler ve bağlantılı listelerde. Bu videoda gidiyoruz yığınları hakkında konuşmak için. Özellikle biz konuşacağız Bir veri yapısı bir yığın çağırdı. Önceki tartışmalardan hatırlayın işaretçiler ve bellek hakkında, istifi de olduğu bellek segment için isim Statik ilan nerede memory-- hafıza size Eğer isim değişkenler, isim, et saire ve fonksiyon kare olan, ayrıca Çağrı yığını çerçeveleri var. Yani bu bir yığın veri yapısıdır bellek değil yığın segmenti. TAMAM. 

Ama yığını nedir? Yani bu sadece bir oldukça çok var Yapının özel bir tür Bu organize bir şekilde verileri korur. Ve iki çok var Ortak yolları uygulamak İki veri yapılarını kullanarak yığınlarının biz zaten aşina olduğunuzu, diziler ve bağlantılı listeler. Ne bir yığın özel yapar Biz bilgileri koymak hangi yolu yığını ve yol biz içine yığından bilgileri siler. Yığınları ile özellikle de kural sadece en çok en son eklenen eleman çıkarılabilir. 

Bir yığın var sanki Yani düşün. Biz bilgi kazık ediyoruz kendisi üstünde, üstünde ve tek şey yığının çıkarılabilir. Biz altında bir şey çıkaramazsınız her şey olur, çünkü daraltmak ve düşmenize. Yani biz gerçekten bir yığın inşa ediyoruz biz sonra parça parça çıkarmak zorunda. Bu nedenle biz bunlara atıfta Bir LIFO yapı olarak bir yığına, , İlk out sürer. LIFO, ilk ortaya sürer. 

Yani çünkü bu kısıtlama on bilgilerin eklenebildiğini ve bir yığından kaldırılır, orada gerçekten sadece iki şey bir yığın yapabilir. Biz hangi zorlayabilir biz eklemek için kullanın terim üstüne yeni bir unsur yığını, ya da eğer yığın yok ve biz, sıfırdan yaratıyoruz ilk etapta yığını oluşturarak iterek olacaktır. Ve sonra pop, o CS çeşit terim biz en son kaldırmak için kullanın yığının üst elemanı ekledi. 

Yani biz hem de bakmak için gidiyoruz uygulamalar, hem dizi bazlı ve bağlantılı liste tabanlı. Ve biz gidiyoruz tabanlı dizi ile başlar. Yani burada temel fikir nedir Dizi tabanlı yığın veri yapısı gibi görünecektir. Biz burada bir yazılı tanımı var. Bunun İçinde iki üyemiz var yapısının veya alanları. Biz bir dizi var. Ve yine ben kullanıyorum keyfi veri türü değeri. 

Yani bu herhangi bir veri türü olabilir, int char veya başka bir veri Eğer daha önce oluşturduğunuz yazın. Bu yüzden boyut kapasitesinin bir dizi var. Kapasite kiloluk sabit tanımlandığı belki başka bir yerde bizim dosyada. Yani bu özel zaten fark Biz sınırlayıcı olan uygulama kendimizi tipik olarak oldu Dizilerle durum, dinamik olarak yeniden boyutlandırmak olamaz ki, nerede belli bir numara var elemanlarının en fazla olduğu Bizim yığın koyabilirsiniz. Bu durumda kapasite elemanları var. 

Biz de takip yığının üst. En neler unsurdur Son zamanlarda yığına eklendi? Ve böylece biz o takip Değişken olarak adlandırılan üst. Ve bu arada sarılmış olur Bir yığın olarak adlandırılan yeni bir veri türü içine. Ve biz oluşturulan konum kez Bu yeni veri türü biz gibi davranabilirsiniz Başka bir veri türü. Biz gibi, yığın s bildirebilirsiniz Biz int x, y veya karakter yapabilirdi. Ve biz yığın dediğim zaman s, iyi ne olur Biz bir dizi olsun bir Hafıza bizim için kenara koyun. 

Bu durumda kapasitesi Ben görünüşe göre karar verdim Ben bir var, çünkü 10 tipi yığının tek değişken hangi iki alan hatırlamak içerir. Bu durumda bir dizi, gidiyor tamsayılar dizisi olmaya benim örneklerin çoğu böyledir. Ve başka bir tamsayı değişken üst depolayabilen, en son eklenen yığına element. Yani tek bir yığın ne Sadece bu gibi görünüyor tanımlanmış. Bu içeren bir kutu var 10 bir dizi nedir Bu durumda tamsayı ve yeşil orada başka bir tamsayı değişken yığının üst gösterir. 

Üst ayarlamak için Yığın biz sadece s.top demek. Yani biz bir erişim nasıl Bir yapı hatırlama alanı. s.top etkin bir 0'a eşittir Bizim yığına yapar. Yani yine biz iki operasyonları var Şimdi gerçekleştirebilirsiniz. Biz itebilir ve biz pop olabilir. Push ile başlayalım. Yine, yeni ekliyor bastırıyor yığının üstüne öğesi. 

Peki ne yapmak gerekiyor Bu dizi tabanlı uygulama? Peki genel The itme fonksiyonu gidiyor Bir kabul etmek gerekir yığına işaretçisi. Şimdi bir saniyenizi ayırın ve bunu bir düşün. Neden kabul etmek isteyeyim yığına bir işaretçi? Önceki videolar hatırlayın Değişken kapsamı ve işaretçileri, biz sadece gönderirse ne olur yığın, bir parametre olarak oldukça s? Aslında orada ne geçti ki? Biz bir kopyasını oluştururken hatırla Biz bir işleve geçmesi zaman sürece biz işaretçileri kullanmak. Ve böylece bu fonksiyon ihtiyaçlarını itmek yığına bir işaretçi kabul etmek biz aslında değişen konum, böylece Yığın biz değiştirmek niyetinde. 

Başka bir şey itme muhtemelen istiyor kabul türü değeri veri elemanıdır. Bu durumda, yine bir tamsayıdır bu Biz yığının üstüne eklemek için gidiyoruz. Bu yüzden bizim iki parametre var. Biz ne yapacağız Şimdi itme içinde do? Peki, sadece, sadece eklemek için gidiyoruz yığının üstüne unsuru ve daha sonra burada üst değiştirme Yığın o üst değer nokta s vardır. Peki bu ne bir işlevdir itme bildirimi Bir de gibi görünebilir dizi tabanlı uygulama. 

Yine bu sert ve hızlı bir kural değil Bunu değiştirmek olabileceğini Bu farklı şekillerde değişir. Belki s küresel ilan edilir. Ve böylece bile gerek yok Bir parametre olarak pass etmek. Bu yine sadece bir itme genel durum. Ve farklı vardır yolları uygulamak için. Ancak bu durumda bizim itme alacak İki argüman, bir yığın bir işaretçi ve türü değeri tamsayı veri elemanı bu durumda. 

Bu yüzden biz, s beyan s.top 0'a eşittir söyledi. Şimdi basalım yığına sayısı 28. Peki bu ne anlama geliyor? Peki şu anda yığınının üst 0'dır. Ve böylece temelde ne var ne olacak olan Biz numarayı sopa gidiyoruz Dizi konumu 0 28.. Oldukça basit, doğru, o üst oldu ve şimdi biz gitmek için iyi bir konum. Ve sonra ne değiştirmeniz gerekir yığının üstünde olacak. Bir dahaki sefere Böylece Biz bir element itin, Biz bunu saklamak için gidiyoruz Dizi konumu, muhtemelen 0. Biz üzerine istemiyoruz Biz sadece orada ne koymak. Ve böylece biz sadece üst 1 hareket edeceğiz. Muhtemelen mantıklı. 

Şimdi başka bir eleman koymak istiyorsanız yığına, biz 33 itmek istiyor demek de şimdi biz sadece 33 almaya gidiyoruz ve dizi konum numarasına koydu 1 ve daha sonra üst değiştirmek bizim Dizi yeri iki numara olmak yığını. Yani bir dahaki sefere biz istiyoruz yığına bir elemanı itmek, bu dizi bir konumda 2 koymak olacak. Ve en olduğunu bir kez daha yapalım. Biz yığınlarının kapalı 19 itmek gerekir. Biz dizi konumda 2 19 takacağım ve bizim yığının üst değiştirme Dizi yeri 3 olmak böylece bir dahaki sefere biz eğer biz gitmek için iyi bir konum, bir itme yapmak gerekir. 

Tamam, böylece Özetle itiyor. Ne haşhaş dersiniz? Yani haşhaş çeşit iterek meslektaşı. Biz yığından verileri kaldırmak nasıl. Ve genel pop ihtiyaçları aşağıdakileri yapmak. Bu bir işaretçi kabul etmek gerekiyor genel durumda tekrar yığını. Diğer bazı durumda olabilir küresel yığın ilan ettiler, bu durumda onu geçmek gerekmez Çünkü o zaten erişimi olan Bir global değişken olarak. Ama başka sonra ne yapmamız gerekiyor? Peki biz artan edildi push yığının üst bu yüzden biz muhtemelen istediğiniz gidiyoruz yığının üst azaltma pop, değil mi? Ve sonra tabii ki biz de istediğiniz gidiyoruz Biz kaldırmak değer döndürmek için. Biz öğeleri ekleyerek ediyorsanız, biz istiyoruz Daha sonra unsurları çıkmak, Muhtemelen aslında Onları bu yüzden saklamak istediğiniz Sadece onları silmeyin üste sonra onlarla bir şey yapmak. Genellikle biz eğer itme ve burada haşhaş Bu saklamak istediğiniz anlamlı bir şekilde bilgi ve bu yüzden yapmaz duygusu sadece atmak. Yani bu fonksiyon gerekir Muhtemelen bize bir değer döndürür. 

Peki bu pop için ne bir beyan olduğunu sol üst kısmında orada gibi görünebilir. Bu işlev döndürür türü değerinin veri. Yine kullanılarak oldum tamsayılar boyunca. Ve bir yığın olarak bir işaretçi kabul tamamen kendi argümanı ya da tek bir parametre. Peki pop yapacak? En şimdi istiyoruz diyelim s kapalı bir unsuru pop. Yani yığınları son olduğunu söyledi hatırlıyorum ilk önce, LIFO veri yapıları içinde. Hangi eleman gidiyor istiften çıkarılabilir? Eğer 19 tahmin mü? Eğer haklı olurdunuz çünkü. 19 Biz eklenen son eleman oldu biz öğeleri iterek zaman yığını, ve bu yüzden ilk gidiyor kaldırılırsa unsur. Biz 28 dedi sanki, ve o zaman biz, bunun üstüne koymak 33 ve biz bunun üstüne 19 koydu. Biz çıkarabilirsin tek unsur 19'dur. 

Şimdi, burada şemada ne yaptığımı tür diziden 19 silinir. Aslında değil ne yapacağız. Biz sadece tür gidiyoruz bir o orada yokmuş gibi davranırız. O orada hala bellek konumu, ama biz sadece bunu görmezden için gidiyoruz Bizim yığının üst değiştirerek 2 3 olmaktan. Biz eğer öyleyse şimdi itin yığına başka unsur, Bitti 19 yazardı. 

Ama sorun değil üzerinden gidelim yığından 19 silme. Biz sadece orada değil iddia edebilir. Yığının amaçları için, eğer gitti Biz 2 yerine 3 olmak üzere üst değiştirin. Pekâlâ, bu oldukça fazlaydı bu yüzden. Yani yapmamız gereken tek şey bir öğe kapalı pop. Hadi bir daha yapalım. Yani burada kırmızı bunu vurguladık biz başka bir çağrı yapıyoruz gösteriyor. Biz de aynı şeyi yapacağız. 

Peki ne olacak? Peki, biz saklamak için gidiyoruz X 33 ve biz gidiyoruz 1 yığının üst değiştirmek için. Biz itmek şimdi olsaydı Böylece Biz konum yığına element Şu anda yapacaksın, ne olacak Biz yazma gidiyoruz olduğunu Dizi yeri 1 numara. Sıralama bırakıldı olduğu 33 Böylece arkasında biz sadece davrandı artık orada değil, biz sadece gidiyoruz Bunu clobber ve orada yerine 40 koymak. Ve sonra tabii ki, Biz bir itme yaptı beri, Biz artırmak için gidiyoruz 1 ila 2 yığının üst bu yüzden şimdi eklerseniz o Başka bir öğesi olacak Dizi yeri iki numaralı gidin. 

Şimdi bağlantılı listeler başka vardır yığınları uygulamak için bir yol. Ve bu tanım ise Ekran burada, size tanıdık görünüyor neredeyse görünüyor çünkü bu kadar aynı, aslında, hemen hemen tam olarak Bir tek tek bağlantılı liste olarak aynı, Eğer bizim tartışmasından hatırlayacak olursak tek başına başka bir videoda listeleri bağlantılı. Buradaki tek kısıtlama , programcılar olarak bizim için biz izin yok eklemek veya rasgele silme tek başına bağlantılı listeden Daha önce yapabilirdi ki. Biz şimdi sadece takın ve gelen silebilirsiniz Ön veya bağlı üst listesi. Bu gerçekten sadece var Fark olsa. Bu başka türlü bir tek başına bağlantılı listesidir. Bu tek sınırlama, bu Kendimize değiştirilmesi programcılar olarak bu bir yığın haline dönüşür. 

Burada kural her zaman bir muhafaza etmektir Bir bağlantılı liste başına işaretçisi. Bu tabii bir genellikle ilk önemli kural. Tek başına size liste zaten bağlanmış İçin Sadece kafasına bir işaretçi gerek Bu sahip olmak için Zincir başvurmak mümkün Her diğer elemana bağlantılı liste. Ama özellikle iyi Bir yığın önemli. Ve böylece genellikle sen Aslında istediğiniz olacak Bu işaretçi küresel değişken olduğu. Muhtemelen gidiyor daha kolay bu şekilde olacak. Yani itme ve pop analogları nelerdir? Sağ. Yani yine bastırıyor ekliyor yığına yeni bir unsur. Bağlantılı bir listede olduğunu biz gidiyoruz demektir Biz konum yeni bir düğüm oluşturmak için Bağlantılı liste halinde eklemek için gidiyoruz, ve daha sonra dikkatli adımları izleyin Daha önce açıkladık olduğunu tek başına bağlantılı listeler bunu eklemek zincir kırılmadan zincir ve kaybetme ya da herhangi bir orphaning bağlantılı liste elemanları. Ve bu temelde ne anlama var Metnin küçük blob var özetlemektedir. Ve en bir göz atalım Bir diyagram olarak en. 

Yani burada bizim bağlantılı liste var. Bu aynı anda dört element içerir. Ve daha mükemmel burada var Dört unsuru içeren yığın. Ve en şimdi istiyoruz diyelim Bu yığına yeni bir öğe itin. Ve biz yeni itmek istiyor kimin veri değeri öğesi 12'dir. Peki biz yapacağız ne? Peki ilk biz gidiyoruz dinamik malloc alanı, yeni bir düğüm için yer tahsis eder. Ve tabii ki hemen sonra biz her zaman biz malloc arama yapmak null kontrol etmek için emin olun biz geri boş var çünkü eğer sorun bir çeşit oldu. Biz boş inceleyebilirsiniz istemiyorum işaretçi veya bir seg hatası yaşayacaktır. Bu iyi değil. Bu yüzden düğümün malloced ettik. Biz burada başarı elde ettik kabul edeceğiz. Biz içine 12 koymak için gidiyoruz Bu düğümün veri alanı. Şimdi hatırlamak yapmak bizim işaretçileri olan bu yüzden zinciri kırmak istemem sonraki hamle? Burada birkaç seçenek var ama Güvenli olacak tek işaretçi yanındaki haber ayarlamak için Listenin eski başkanı gelin ya da yakında ne olacağını Listenin eski başkanı. Ve şimdi tüm bu bizim elemanları bir araya zincirleme, biz sadece işaret listesini taşıyabilirsiniz Yeni yapar aynı yere. Ve biz şimdi etkili itti bir yığının önünde üzerine yeni bir eleman. 

Biz pop sadece istiyorum ilk elemanı silin. Ve böylece temelde ne Biz burada yapmak zorunda iyi ikinci eleman bulmak zorundayız. Sonunda yeni olacak Biz ilkini sildikten sonra baş. Yani biz sadece başlamak gerekir başında, tek ileri hareket ettirin. Biz bir bir tutun var sonra nerede biz ileri halen biz güvenle ilkini silebilirsiniz vardır ve o zaman biz sadece baş taşıyabilirsiniz ne işaret etmek Şimdi ikinci dönem ve Bundan sonra ilk düğüm silindi. 

Yani yine bir göz alarak ona bir diyagram olarak biz Şimdi bir pop istiyorum Bu yığının kapalı öğesi. Peki ne yapacağız? Peki biz ilk oluşturmak için gidiyoruz gidiyor, yeni bir işaretçi başkanı olarak aynı noktaya işaret etmek. Biz bunu bir konum taşımak için gidiyoruz ileri trav eşittir diyerek örneğin, aşağıdaki trav hangi trav işaretçi bir ilerleme olur forward pozisyonu. Şimdi elimizdeki bir İlk öğe üzerinde tutun işaretçi olarak adlandırılan listede ve içinden denilen bir işaretçi üzerinden ikinci unsur trav, biz güvenle o silebilirsiniz yığının ilk elemanı dinlenme kaybetmeden Zincirin çünkü biz başvurmak için bir yol var ikinci elemana yoluyla ileri pointer trav çağırdı. 

Yani şimdi bu düğümü ücretsiz yapabilirsiniz. Biz Listeyi ücretsiz yapabilirsiniz. Ve sonra biz şimdi yapmamız gereken tek şey aynı yerde noktaya taşımak Listeyi Bu trav yapar ve biz geri çeşit konum Biz 12 itti önce başladığımız yere ilk etapta üzerine doğru. Nerede kalmıştık bu tam olarak budur. Bu dört elemanlı bir yığını vardı. Biz beşinci ekledi. Biz beşinci itti elemanı üzerine, sonra attı en güncel olanı geri çekil elemanı ekledi. 

Bu hemen hemen gerçekten tüm yığınlarının orada. Sen diziler olarak uygulayabilirsiniz. Sen bağlantılı listeler olarak uygulayabilirsiniz. Diğer, tabii ki, daha vardır yolları da bunları uygulamak için. Biz kullanmak istiyorsunuz Temelde nedeni yığınları şekilde verileri korumak için en son eklenen bu eleman we 'ilk şey geri almak isteyecektir. Ben Doug Lloyd değilim, bu CS50 olduğunu.