DOUG LLOYD: Wszystko w porządku, więc przez ten punkt jesteś chyba dość znajomo z tablicami i powiązanych list która jest dwa podstawowe struktury danych mamy mówił o do przechowywania zestawów Dane podobnych typów danych zorganizowane. Teraz będziemy rozmawiać o kilku wariantach na tablicach i połączonych listach. W tym filmie mamy zamiar mówić o stosach. W szczególności będziemy rozmawiać o strukturę danych zwaną stos. Przypomnijmy, od poprzednich dyskusjach o wskaźniki i pamięci, że stos jest również nazwa dla segmentu pamięci gdzie statycznie oświadczył Pamięć memory--, że cię wymienić, zmienne, że nazwa, i cetera i funkcji ramki, które również istnieją połączenia ramki stosu. Więc jest to struktura danych stos Nie segment stosu pamięci. OK. 

Ale co to jest stos? Więc jest to dość dużo tylko Specjalny rodzaj konstrukcji który utrzymuje dane w sposób zorganizowany. I nie ma dwóch bardzo wspólne sposoby realizacji stosy za pomocą dwóch struktur danych że jesteśmy już znane, tablice i związane listy. Co sprawia, że ​​specjalny stos jest sposób, w jaki możemy umieścić informacje w stos, i sposób, w jaki usunięcia informacji ze stosu. W szczególności w stosy zasada jest tylko najbardziej Ostatnio dodany element może zostać usunięty. 

Więc pomyśl o tym tak, jakby to stos. Jesteśmy palowania informacji na szczycie sobie, i tylko co na górze stosu mogą być usunięte. Nie możemy usunąć coś pod spodem bo wszystko inne będzie zwinąć i przewrócić. Tak naprawdę budują stosu, następnie musimy usunąć kawałek po kawałku. W związku z tym, że często odnoszą do komina jako struktury LIFO trwać, pierwsze wyszło. LIFO, trwać, pierwsze wyszło. 

Tak więc z powodu tego ograniczenia jak informacja może być dodany do i usunięte ze stosu, tam naprawdę tylko dwie rzeczy, które możemy zrobić ze stosem. Możemy wcisnąć, który jest Termin używamy do dodawania Nowym elementem na szczycie stosu lub gdy papier nie istnieją i tworzymy od podstaw, tworząc stos w pierwszej kolejności byłoby pchania. I wtedy pojawiają, to jest coś w rodzaju CS Termin używamy usunąć ostatnio dodatkowy element z górnej części stosu. 

Tak więc mamy zamiar spojrzeć na oba implementacje oparte zarówno tablica i połączone lista oparta. I będziemy początek tablicy opartej. Tak tu jest podstawowa idea tego, co struktura danych Stos układów w oparciu będzie wyglądać. Mamy tu definicję wpisywanych. Wewnątrz, że mamy dwóch członków lub obszary struktury. Mamy tablicę. I znowu Używam dowolna wartość typu danych. 

Więc może to być dowolny typ danych, int char lub inne dane wpisz utworzony wcześniej. Więc mamy tablicę pojemności wielkości. Pojemność jest funt zdefiniowane stała, może gdzieś indziej w naszym pliku. Więc zauważyć już w ten szczególny Realizacja jesteśmy ograniczające sami, jak to zwykle w przypadku tablic, których nie możemy dynamicznie zmieniać rozmiar, gdzie istnieje pewna liczba maksimum elementów, które możemy umieścić w naszym stosie. W tym przypadku jest to elementy pojemności. 

Mamy również śledzić wierzchołek stosu. Element co jest najbardziej Ostatnio dodania do stosu? A więc śledzić, że w zmienną górze. A wszystko to zostanie opakowane razem do nowego typu danych o nazwie stos. A kiedy jesteśmy stworzone ten nowy typ danych możemy traktować jak innego rodzaju danych. Możemy zadeklarować stosu s, podobnie jak możemy zrobić, int lub char x, y. A kiedy mówimy stos s, dobrze, co się dzieje jest dostajemy zestaw Pamięć zarezerwowana dla nas. 

W tym charakterze przypadku Ja najwyraźniej postanowił 10 ponieważ ja dostałem pojedyncza zmienna typu stos która zawiera dwa pola przypomnieć. Tablica, w tym przypadku będzie być tablicą liczb całkowitych jak to jest w przypadku większości moich przykładach. I kolejna zmienna całkowita zdolne do przechowywania górę, ostatnio dodany element stosu. Więc jeden stos, co po prostu zdefiniowane wygląda następująco. Jest to skrzynka tablica 10, co będą liczbami całkowitymi w tym przypadku i kolejna zmienna istnieje liczba całkowita w zielone wskazanie górnej części stosu. 

Aby ustawić górze Stos po prostu powiedzieć, s.top. W ten sposób możemy uzyskać dostęp do pole wycofania struktury. s.top równa 0 skutecznie robi to do naszego stosu. Więc znowu mamy dwie operacje które możemy wykonać teraz. Możemy wcisnąć i możemy pop. Zacznijmy naciśnięciem. Ponownie, spychając jest dodanie nowego Element na górze stosu. 

Więc co trzeba zrobić w Realizacja na podstawie tej tablicy? Cóż w ogóle Funkcja Push będzie potrzebować do zaakceptowania Wskaźnik do stosu. Teraz Poświęć chwilę i pomyśl o tym. Dlatego chcielibyśmy, aby zaakceptować wskaźnik do stosu? Przypomnijmy, od poprzednich filmów na zmienny zakres i wskaźniki, co się stanie, jeśli po prostu wysłany Stos, s, a jako parametr? Co by rzeczywiście być przekazywane tam? Pamiętaj, tworzymy kopię kiedy przekazać go do funkcji chyba że używamy wskazówek. I tak ta funkcja pchania potrzeb przyjąć wskaźnik do stosu tak, że jesteśmy rzeczywiście się zmienia stos zamierzamy zmienić. 

Inna sprawa, Push prawdopodobnie chce zaakceptować to element danych wartości typu. W tym przypadku znowu liczbą całkowitą mamy zamiar dodać do szczytu stosu. Mamy więc nasze dwa parametry. Co my teraz teraz zrobić wewnątrz push? Cóż, po prostu, po prostu zamiar dodać ten element na wierzchu stosu a następnie zmienić w którym góra stos jest, że s dot najwyższą wartość. Więc to jest to, co funkcja zgłoszenie o naciśnięciem może wyglądać w sposób Tablica oparte wdrożenie. 

Znowu nie jest to twardy i szybki przepis że można to zmienić i mieć się zmieniać na różne sposoby. Być może ów jest uznany na całym świecie. A więc nawet nie trzeba przekazać to jako parametr. To znowu tylko Ogólnie przypadku naciśnięciem. I tam są różne sposoby jego realizacji. Ale w tym przypadku nasze Push zajmie dwa argumenty, wskaźnik do stosu i element danych wartości typu, Integer w tym przypadku. 

Więc oświadczył s, możemy powiedział s.top równa 0. Teraz nacisnąć Numer 28 na stos. Cóż, co to znaczy? Cóż obecnie Szczyt stosu jest 0. A więc to, co jest w zasadzie stanie się to będziemy trzymać numer 28 na miejscu tablicy 0. Całkiem proste, prawda, że była najlepiej i teraz jesteśmy dobrze iść. I wtedy musimy zmienić to, co wierzchołek stosu będzie. Tak, że następnym razem my pchamy element w, mamy zamiar przechowywać w położenie tablicy, prawdopodobnie nie 0. Nie chcemy, aby zastąpić co po prostu umieścić tam. A więc musimy po prostu przenieść góry do 1. To chyba ma sens. 

Teraz, jeśli chcemy umieścić kolejny element na stosie, że chcemy wcisnąć 33, a teraz jesteśmy po prostu zajmie 33 i umieścić go na tablicy liczby lokalizacji 1, a następnie zmienić szczycie naszej układać się tablica numer lokalizacji dwóch. Jeśli więc następnym razem chcemy wcisnąć element na stosie to będzie umieścić w miejscu tablicy 2. I zróbmy to jeszcze raz. Będziemy naciskać 19 off stosów. Umieścimy 19 w miejscu tablicy 2 i zmienić na szczyt naszej stosie być lokalizacja tablicy 3 więc jeśli w czasie następnego my trzeba zrobić push jesteśmy dobrze iść. 

OK, tak że pcha w pigułce. Co popping? Więc popping jest to rodzaj odpowiednik pchania. To, w jaki sposób usunąć dane ze stosu. A w ogólnych potrzeb pop wykonać następujące czynności. Trzeba przyjąć wskaźnik do stosu, również w przypadku ogólnym. W innym przypadku może zadeklarowały stos na całym świecie, w takim przypadku nie ma potrzeby, aby go zdać w, bo już ma do niego dostęp jako zmienną globalną. Ale to, co jeszcze musimy zrobić? Cóż my zwiększając wierzchołek stosu w dostarczaniu, więc jesteśmy prawdopodobnie będzie chciał aby zmniejszyć górną stosu w pop, prawda? I wtedy oczywiście jesteśmy również będzie chciał do zwrotu wartości, które usunąć. Jeśli dodajemy elementy, chcemy aby elementy się później, prawdopodobnie w rzeczywistości Aby zapisać je więc nie po prostu usunąć je z stos, a następnie zrobić nic z nimi. Generalnie, jeśli będziemy pchania i popping tutaj chcemy zapisać to Informacje w znaczący sposób i tak to nie ma sensu po prostu wyrzucić. Tak więc funkcja ta powinna Prawdopodobnie zwracają wartość do nas. 

Tak to jest, co do deklaracji dla pop może wyglądać nie w lewym górnym rogu. Ta funkcja zwraca Dane wartości wpisz. Znowu byliśmy przy użyciu liczb całkowitych w całym. I przyjmuje wskaźnik do stosu jako jego jedynym argumentem lub jedynym parametrem. Więc co jest pop zamierza zrobić? Powiedzmy, że chcemy teraz pop element off s. Więc pamiętaj, powiedziałem, że stosy są w zeszłym , pierwsze wyszło, LIFO struktur danych. Który element będzie usunięte ze stosu? Czy domyślasz 19? Dlatego, że masz rację. 19 był ostatnim elementem dodaliśmy do stos, kiedy pchali elementy, na, i tak to będzie pierwszy elementem, który zostanie usunięty. To tak, jakbyśmy powiedział 28 oraz następnie umieścić 33 na nim, i umieścić 19 na dodatek. Jedynym elementem, możemy zdjąć jest 19. 

Teraz w schemacie tutaj co zrobiłem jest rodzajem usunięty 19 z tablicy. To nie jest właściwie co będziemy robić. Jesteśmy po prostu się do rodzaju z udawać, że nie ma. To jeszcze nie w że miejsce w pamięci, ale jesteśmy po prostu będzie go zignorować zmieniając jeszcze wierzchołka stosu z jest od 3 do 2. Więc gdybyśmy teraz wcisnąć kolejny element, na stosie to ponad Napisać 19. 

Ale nie przejść przez kłopotów z usunięciem 19 ze stosu. Możemy udawać, że go tam nie ma. Dla celów stosu go nie ma, jeśli zmieniamy górną się 2 zamiast 3. W porządku, więc to było dość dużo. To wszystko, co musimy zrobić, pop element wyłączony. Zróbmy to jeszcze raz. Więc mam podświetlone na czerwono, to tu wskazują, robimy kolejny telefon. Mamy zamiar zrobić to samo. 

Więc co się stało? Cóż, mamy zamiar przechowywać 33 w x i będziemy zmienić wierzchołek stosu 1. Tak, że gdybyśmy byli teraz, aby popchnąć Element do stosu, które jesteśmy zamierza zrobić w tej chwili, co się stanie jest jedziemy nadpisywania Tablica liczba lokalizacja 1. Tak, że 33, który był jakby w lewo tyle, że po prostu udawał już nie ma, po prostu dzieje do sprać go i umieścić 40 tam zamiast. A potem, oczywiście, od zrobiliśmy push, będziemy zwiększamy Szczyt stosu od 1 do 2 tak, że jeśli teraz dodać kolejny element, to będziesz iść do tablicy liczby lokalizacji dwóch. 

Teraz związane listy są kolejnym sposobem realizacji stosy. A jeśli tej definicji w sprawie Ekran tutaj wygląda znajomo, to dlatego, że wygląda prawie dokładnie takie same, w rzeczywistości to dość dużo jest dokładnie same jako pojedynczo połączonego listy Jeśli pamiętacie z naszej dyskusji pojedynczo związane list w innym filmie. Jedynym ograniczeniem tutaj jest dla nas, jako programiści, nie wolno nam wstawić lub usunąć losowo od pojedynczo połączonej listy które mogliśmy wcześniej zrobić. Możemy tylko teraz wstawiać i usuwać z z przodu lub z góry połączony lista. To naprawdę tylko Różnica jednak. Jest to inaczej pojedynczo połączonej listy. To tylko ograniczenie zastępując na siebie jako programistów zmienia go na stosie. 

Zasadą jest tu zawsze utrzymać wskaźnik na czele połączonej listy. Oczywiście, jest to ogólnie Pierwsza ważna zasada. Dla pojedynczo związane listy i tak ci Wystarczy tylko wskaźnik do głowy w celu uzyskania, że Łańcuch w stanie odnieść do każdego innego elementu w połączonej listy. Ale jest to szczególnie ważne w stos. I tak na ogół jesteś będzie rzeczywiście chcesz Ten wskaźnik jest zmienna globalna. To prawdopodobnie będzie być nawet łatwiej. Więc jakie są analogi naciśnięciem i pop? Dobrze. Więc znów naciska dodaje nowy element na stosie. W połączonej listy oznacza, że ​​będziemy mieć do utworzenia nowego węzła, że ​​jesteśmy zamiar dodać do połączonej listy, a następnie postępuj zgodnie z ostrożne kroki że mamy opisane wcześniej w pojedynczo związane listy, aby dodać go do łańcuch bez zerwania łańcucha oraz utraty lub osierocenia dowolny elementy połączonej listy. I to w zasadzie co to mała kropelka tekstu nie podsumowuje. I rzućmy okiem na to jak na schemacie. 

Więc oto nasza związana lista. To jednocześnie zawiera cztery elementy. I bardziej doskonale Oto nasz stos zawierający cztery elementy. I powiedzmy, że chcemy teraz wcisnąć nowy element na tym stosie. A my chcemy pchnąć nowy element, którego dane wartości to 12. No i co my teraz zrobimy? Cóż pierwszy będziemy Przestrzeń malloc, dynamicznie przydzielić miejsca dla nowego węzła. I oczywiście natychmiast po robimy wywołanie malloc zawsze upewnij się, aby sprawdzić, null, bo jeśli mamy zerowy powrotem to był jakiś rodzaj problemu. Nie chcemy, aby dereference tej wartości null wskaźnik lub będzie cierpieć usterki seg. To niedobrze. Więc my malloced węzła. Będziemy zakładać, mieliśmy sukces tutaj. Mamy zamiar umieścić 12 do Pole danych danego węzła. Teraz wspominasz, które z naszych wskazówek porusza się obok więc nie przerwać łańcuch? Mamy tu kilka opcji, ale jedynym, który będzie bezpieczny jest ustawiony wskaźnik do następnej wiadomości punkt do starego czele listy lub, co wkrótce będzie stary szef listy. I teraz, że wszystkie nasze elementy są połączone w łańcuch, możemy po prostu przejść listy wskazać w tym samym miejscu, że nowe nie. I mamy teraz skutecznie pchnął Nowy element na wierzch stosu. 

Pop Chcemy tylko usunąć ten pierwszy element. I tak w zasadzie to, co mamy tu do czynienia, dobrze musimy znaleźć drugi element. W końcu, że stanie się nowym udać się po usuwamy pierwszy. Więc po prostu trzeba zacząć od początek, przejście o jeden do przodu. Gdy mamy trzymać na jednym z przodu, gdzie obecnie to możemy usunąć pierwszy bezpiecznie a następnie możemy po prostu przesunąć głowę zwrócić się do tego, co było Drugi termin i teraz Jest to pierwsza potem Węzeł został usunięty. 

Więc jeszcze raz, przyjrzeniu na to jak na diagramie chcą teraz pop elementem przy tego stosu. Więc co robimy? Cóż mamy pierwszy zamiar stworzyć nowy wskaźnik, który będzie zwrócić się w tym samym miejscu, co w głowę. Mamy zamiar przenieść go o jedną pozycję do przodu mówiąc równych TRAV TRAV obok na przykład, które by przesunąć jednego wskaźnika trav pozycji do przodu. Teraz, gdy mamy trzymać pierwszy element listę wskaźnik nazywa, a Drugim elementem poprzez wskaźnik zwany trav, możemy bezpiecznie usunąć, że Pierwszy element ze stosu bez utraty resztę łańcucha, bo my mają sposób odnieść do drugiego elementu przekazania w drodze wskaźnik zwany trav. 

Więc teraz możemy uwolnić ten węzeł. Możemy uwolnić listę. I to wszystko, co musimy zrobić teraz jest wykaz przejść do punktu w tym samym miejscu że trav robi, i jesteśmy z powrotem w rodzaju gdzie zaczęliśmy zanim pchnął 12 on na pierwszym miejscu w prawo. To jest dokładnie to, gdzie jesteśmy. Mieliśmy ten czterech elementów stosu. Dodaliśmy jedną piątą. Mamy pchnął piątą Element na, a następnie Niedawno pojawiło, że większość Element dodany wycofać. 

To naprawdę bardzo dużo wszystko na stosy. Możesz wykonać je w tablicach. Możesz wykonać je w połączonych listach. Istnieją oczywiście inne sposoby ich realizacji, jak również. Zasadniczo powodem użylibyśmy Stosy jest przechowywanie danych w taki sposób, że ostatnio dodane Element jest pierwszą rzeczą, że jesteśmy będzie chciał wrócić. Jestem Doug Lloyd, to CS50.