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.