DOUG LLOYD: Alle Rechte, so von diesem Punkt bist du wahrscheinlich ziemlich vertraut mit Arrays und verkettete Listen der die beiden Primär ist Datenstrukturen, wir haben sprach über für die Aufbewahrung Sätze Daten von ähnlichen Datentypen organisiert. Jetzt werden wir zu sprechen über ein paar Variationen auf Arrays und verkettete Listen. In diesem Video werden wir über Stapel zu sprechen. Insbesondere werden wir sprechen über eine Datenstruktur, genannt ein Stapel. Rückruf von früheren Diskussionen über Zeiger und Gedächtnis, daß der Stapel auch die Bezeichnung für einen Abschnitt des Speichers wo statisch deklariert memory-- Speicher, die Sie Namen, Variablen, die Sie nennen, et cetera und Funktionsrahmen, die wir Call-Stack-Frames vorhanden sind. Das ist also ein Stapel-Datenstruktur kein Stapelspeichersegment. OK. 

Aber was ist ein Stack? Es ist also ziemlich genau ein besondere Art von Struktur dass die Daten pflegt in einer organisierten Art und Weise. Und es gibt zwei sehr gemeinsame Wege zur Umsetzung Stacks unter Verwendung von zwei Datenstrukturen dass wir bereits kennen, Arrays und verkettete Listen. Was macht ein Stapel besonderen ist die Weise, in der wir uns stellen Informationen in den Stapel, und, wie wir entfernen Sie Informationen aus dem Stapel. Insbesondere mit Stapeln die Regel ist nur das zuletzt hinzugefügten Elements entfernt werden kann. 

Also denken Sie darüber nach, als ob es ein Stapel. Wir häufen Informationen auf sich selbst, und nur das, was an der Spitze des Stapels entfernt werden kann. Wir können die Sache nicht unter zu entfernen denn alles andere würde Zusammenbruch und umfallen. So dass wir wirklich bauen ein Stack, Wir müssen dann Stück für Stück zu entfernen. Aus diesem Grund haben wir gemeinhin beziehen einen Stapel als LIFO-Struktur, last in, first out. LIFO, last in, first out. 

So, weil dieser Beschränkung wie Informationen hinzugefügt werden und aus einem Stapel entfernt, gibt es wirklich nur zwei Dinge, die wir mit einem Stapel tun können. Wir können zu drücken, die der ist Begriff verwenden wir für das Hinzufügen ein neues Element in der Oberseite des Stapel, oder wenn der Stapel nicht vorhanden und wir schaffen es von Grund auf, Erstellen des Stapels in dem ersten Platz wäre schieben. Und dann Pop, das ist die Art von CS Begriff verwenden wir, um die zuletzt entfernen von der Oberseite des Stapels aufgenommen Element. 

So werden wir an beiden freuen Implementierungen, sowohl Array basiert und verknüpften Liste basiert. Und wir sind zu gehen beginnen mit Array basiert. Also hier ist die grundlegende Idee von dem, was die Array-basierte Stapeldatenstruktur aussehen würde. Wir haben eine typisierte Definition hier. Innenseite, dass wir zwei Mitglieder oder Felder der Struktur. Wir haben ein Array. Und wieder bin ich mit der beliebige Datentyp Wert. 

So könnte dies ein beliebiger Datentyp sein, int char oder eine andere Daten Geben Sie zuvor erstellt haben. So haben wir eine Reihe von Größe Kapazität. Kapazität, die ein Pfund definierte Konstante, vielleicht irgendwo anders in unserer Datei. So bemerken bereits mit diesem Umsetzung wir begrenze uns als war typisch mit Arrays der Fall ist, die wir nicht dynamisch die Größe können, wo es eine bestimmte Anzahl von Elementen Höchstbetrag, Wir können in unserem Stapel gelegt. In diesem Fall ist es Kapazitätselemente. 

Wir halten auch verfolgen das obere Ende des Stapels. Welches Element am meisten, vor kurzem zu dem Stapel hinzugefügt? Und so verfolgen wir, dass in einer Variablen namens top. Und all dies wird zusammen eingewickelt in einen neuen Datentyp mit dem Namen eines Stapels. Und sobald wir geschaffen sind Diese neue Datentyp wir können sie zu behandeln wie andere Datentyps. Wir können Stapel s gerade wie zu erklären, wir könnten int x, y oder char zu tun. Und wenn wir sagen stapeln s, auch, was passiert, wird wir eine Reihe von zu bekommen Speicher für uns beiseite stellen. 

In diesem Fall Kapazität Ich habe offenbar beschlossen ist 10, weil ich eine bekommen Einzel Variable des Typs Stack welche enthält zwei Felder wieder zu verwenden. Eine Anordnung, in diesem Fall wird um eine Anordnung von Zahlen sein wie es in den meisten meiner Beispielen der Fall ist. Und noch ein Integer-Variable fähig zur Speicherung der Spitze, die zuletzt hinzugefügten Element auf den Stapel. So ein Einzelstapel, was wir gerade definiert sieht wie folgt aus. Es ist eine Kiste mit ein Array von 10 Meinung werden Zahlen in diesem Fall, und ein weiterer Integer-Variablen gibt es in grün um die Oberseite des Stapels anzuzeigen. 

Um die Oberseite des Fernseh Stapel wir nur sagen s.top. Das ist, wie wir Zugang zu einem Feld einer Struktur Rückruf. s.top effektiv gleich 0 tut dies, um unsere Stack. So haben wir wieder zwei Operationen dass wir jetzt durchführen können. Wir können schieben und wir knallen kann. Lassen Sie uns mit Push starten. Auch hier drängt das Hinzufügen einer neuen Element mit dem oberen Ende des Stapels. 

Also, was tun wir in tun müssen Dieses Array basierte Implementierung? Gut im Allgemeinen die Push-Funktion wird zu müssen, um eine zu akzeptieren Zeiger auf den Stack. Nun nehmen Sie sich die Zeit und denken Sie darüber nach. Warum sollten wir annehmen wollen, ein Zeiger zu dem Stapel? Recall aus früheren Videos auf Geltungsbereich von Variablen und Zeiger, was passieren würde, wenn wir gerade geschickt Stapel, s eher als Parameter? Was wäre eigentlich da drin übergeben werden? Denken Sie daran, wir schaffen eine Kopie wenn wir es übergeben, um eine Funktion es sei denn, wir Zeigern. Und so diese Funktion schieben Bedürfnisse einen Zeiger auf den Stapel übernehmen so dass wir wirklich zu ändern der Stapel wollen wir ändern. 

Die andere Sache, Push wahrscheinlich will akzeptieren, ist ein Datenelement vom Typ Wert. In diesem Fall wieder eine ganze Zahl, wir werden an die Spitze der Stapel hinzufügen. So haben wir unsere beiden Parameter hat. Was machen wir Jetzt innerhalb von Push zu tun? Nun, ganz einfach, wir sind gerade dabei, fügen dass das Element nach oben aus dem Stapel und ändern Sie dann in dem die Spitze der der Stapel, dass s-Punktoberwert. Also das ist, was eine Funktion Erklärung für Push- könnte wie in einem Blick Array-basierte Implementierung. 

Auch dies ist keine feste Regel, dass man dies ändern und sie unterscheiden sich in unterschiedlicher Weise. Vielleicht s global deklariert. Und damit Sie brauchen noch nicht einmal einen Pass zu spielen ist als Parameter. Dies ist wiederum nur ein allgemeine Fall für Push. Und es gibt verschiedene Möglichkeiten, es zu implementieren. Aber in diesem Fall unsere Push dauern wird zwei Argumente einen Zeiger auf einen Stapel und ein Datenelement vom Typ Wert, integer in diesem Fall. 

So erklärten wir s, wir sagte s.top gleich 0. Lassen Sie uns jetzt drücken Sie die Nummer 28 auf den Stapel. Nun, was soll das bedeuten? Nun noch die oben auf dem Stapel ist 0. Und was ist im Grunde geschehen ist wir werden die Anzahl Stick 28 in Feldposition 0. Ziemlich einfach, nicht wahr, dass war der Top-und jetzt sind wir gut zu gehen. Und dann zu dem, was wir ändern müssen Die Oberseite des Stapels wird. So daß das nächste Mal, schieben wir ein Element, wir werden es in speichern Array Lage, wahrscheinlich nicht 0. Wir wollen nicht zu überschreiben, was wir dort setzen gerade. Und so werden wir nur bewegen Sie den oben nach 1. Das macht wohl Sinn. 

Wenn wir nun ein weiteres Element setzen wollen auf den Stapel, sagen wir, bis 33 zu schieben möchten, und jetzt sind wir gerade dabei, 33 nehmen und legen Sie sie auf Array Platznummer 1, und ändern Sie dann die Spitze unserer stapeln, um Matrixort Nummer zwei zu sein. Also, wenn das nächste Mal, wenn wir wollen, drücken Sie ein Element auf den Stapel, es wird in der Anordnung Standort 2 gestellt werden. Und lassen Sie uns tun, dass man mehr Zeit. Wir drücken 19 Aus der Stapel. Wir werden 19 in Array Standort 2 gesetzt und ändern Sie die Spitze unserer Stapel Array Lage 3 sein so dass, wenn das nächste Mal, wenn wir brauchen, um eine Push wir sind gut zu gehen zu machen. 

OK, also ist das Schieben auf den Punkt. Was ist mit knallen? So knallen ist die Art von Gegenstück zu schieben. Es ist, wie wir Daten aus dem Stapel zu entfernen. Und im allgemeinen pop Bedürfnisse um Folgendes zu tun. Es braucht, um einen Zeiger auf die Annahme Stapel, wieder in den allgemeinen Fall. In einem anderen Fall, dass Sie vielleicht haben Sie den Stapel global deklariert, In diesem Fall brauchen Sie nicht, um es zu übergeben in, da es bereits Zugang hat als globale Variable. Aber dann, was wir sonst noch tun müssen? Nun, wir waren Erhöhen die Oberseite des Stapels in push, so dass wir wahrscheinlich gehen zu wollen, um die Oberseite des Stapels zu dekrementieren in Pop, nicht wahr? Und dann natürlich wir auch gehen zu wollen, um den Wert, den wir entfernen zurückzukehren. Wenn wir das Hinzufügen von Elementen wollen wir Elemente später raus, wir wohl tatsächlich wollen sie, so dass wir speichern nicht nur aus dem löschen stapeln und dann nichts zu tun mit ihnen. Im Allgemeinen, wenn wir Schieben und hier knallen wir diese speichern möchten Informationen in sinnvoller Weise und so ist es nicht sinn Sinn, nur verwerfen. So sollte diese Funktion Wert wahrscheinlich zu uns zurückkehren. 

Also das ist, was eine Erklärung für die Pop- könnte wie es in der oberen linken aussehen. Diese Funktion gibt Daten vom Typ Wert. Wieder haben wir habe mit Zahlen überall. Und es nimmt einen Zeiger auf einen Stapel als das einzige Argument ist oder einzige Parameter. Also, was ist pop tun? Nehmen wir an, wir wollen jetzt Pop ein Element aus der s. So erinnere ich mich, dass Stacks letzten in, first out, LIFO-Datenstrukturen. Welches Element zu gehen wird aus dem Stapel entfernt werden? Haben Sie erraten, 19? Da hätten Sie recht. 19 war das letzte Element, das wir auf der Mehr stapeln, als wir an Schubelemente, und so ist es mit dem ersten gehen Element, das entfernt wird. Es ist, als ob wir die 28, und dann setzen wir 33 oben drauf, und wir haben 19 obendrein. Das einzige Element, die wir ergreifen können ausgeschaltet ist 19. 

Jetzt in der Grafik hier was ich getan habe ist eine Art gelöscht 19 aus dem Array. Das ist nicht wirklich was wir tun werden. Wir sind gerade dabei, Art von so tun, es ist nicht da. Es ist immer noch da in dass Speicherplatz, aber wir sind gerade dabei, es zu ignorieren durch Ändern der Spitze unserer Stapel entfernt, 3-2. So, jetzt zu schieben, wenn wir ein anderes Element auf dem Stapel, Es wäre mehr als 19 schreiben. 

Aber lasst uns nicht die Mühe zu gehen das Löschen 19 von dem Stapel. Wir können einfach so tun, es ist nicht da. Für die Zwecke des Stapels ist es, wenn gegangen wir die Spitze zu ändern, um 2 statt 3 sein. Na gut, das war so ziemlich alles. Das ist alles, was wir tun müssen um ein Element abspringt. Lass uns das nochmal machen. Also habe ich es hier rot hervorgehoben zeigen wir machen einen weiteren Anruf. Wir werden das gleiche tun. 

Also, was wird passieren? Nun, wir werden zu speichern 33 in x und wir werden um die Oberseite des Stapels auf 1 zu ändern. So dass, wenn wir nun auf ein Push Element in den Stapel, die wir sind gehen zu tun, gerade jetzt, was wird passieren wird wir überschreiben gehen Array Platznummer 1. So dass 33, die Art von übrig blieb hinter, dass wir nur vorgab nicht mehr da ist, sind wir gerade dabei um es zu verprügeln und legte 40 dort statt. Und dann natürlich, da wir einen Push, wir werden das Inkrement Oberseite des Stapels 1-2 so dass, wenn wir jetzt hinzufügen ein weiteres Element, es wird gehen Sie in Feldposition Nummer zwei. 

Jetzt verkettete Listen sind ein weiterer Weg, um Stapel zu implementieren. Und wenn dieser Definition auf die Bildschirm Hier schaut Ihnen vertraut, es ist, weil es sieht fast aus genau gleich sind, in der Tat, es ziemlich viel ist genau die Gleiche wie eine einfach verkettete Liste, wenn Sie von unserer Diskussion erinnern einzeln in einem anderen Video-verknüpften Listen. Die einzige Einschränkung hier ist für uns als Programmierer, wir dürfen nicht einfügen oder löschen Zufallsprinzip aus der einzeln verkettete Liste die wir vorher tun könnte. Wir können nur jetzt einlegen und aus löschen der Vorder- oder Oberseite des verknüpften Liste. Das ist wirklich die einzige Unterschied though. Das ist sonst eine einfach verkettete Liste. Es ist nur die Beschränkung Ersatz an uns selbst wie Programmierer, verwandelt es sich in einem Stapel. 

Die Regel hier ist, um immer einen Zeiger auf den Kopf einer verketteten Liste. Das ist natürlich eine allgemein wichtige Regel zuerst. Für einfach verkettete Liste irgendwie, das Sie brauchen nur einen Zeiger auf den Kopf Um dies zu haben Kette in der Lage, zu beziehen zu jedem anderen Element in der verknüpften Liste. Aber es ist vor allem wichtig mit einem Stapel. Und so in der Regel sind Sie gehen, um wirklich wollen Diese Zeiger auf eine globale Variable sein. Es ist wahrscheinlich zu sogar noch einfacher. Was also sind die Analoga von Push- und Pop? Recht. Also noch einmal drücken wird das Hinzufügen ein neues Element in den Stapel. In einer verknüpften Liste, bedeutet, dass wir gehen zu müssen, um einen neuen Knoten, die wir erstellen gehen, um sich der Liste hinzuzufügen, und befolgen Sie die vorsichtige Schritte dass wir vorher skizziert habe, in einfach verkettete Listen, um sie hinzuzufügen die Kette ohne die Kette und verlieren oder zu verwaisen jede Elemente der verketteten Liste. Und das ist im Grunde, was das kleinen Klecks Text gibt einen Überblick. Und lassen Sie uns einen Blick es als ein Diagramm. 

Also hier ist unsere verknüpften Liste. Es enthält gleichzeitig vier Elemente. Und mehr perfekt hier ist unsere Stack mit vier Elementen. Und lassen Sie uns sagen, wir wollen jetzt drücken Sie ein neues Element auf diesem Stapel. Und wir ein neues zu schieben möchten Artikel, deren Datenwert ist 12. Nun, was sollen wir tun? Nun zunächst sind wir zu gehen malloc Raum, dynamisch Speicherplatz zuweisen für einen neuen Knoten. Und selbstverständlich unmittelbar nach Wir machen einen Aufruf an die wir immer malloc stellen Sie sicher, für null zu überprüfen, denn wenn wir null zurückkamen es war eine Art von Problem. Wir wollen nicht zu dereferenzieren, die NULL Zeiger oder Sie eine seg Störung leiden. Das ist nicht gut. Also haben wir des Knotens malloced habe. Wir gehen davon aus, wir haben Erfolg hatte hier. Wir werden 12 kannst das Datenfeld dieses Knotens. Jetzt müssen Sie sich erinnern was unserer Zeigern bewegt sich weiter, so dass wir die Kette nicht zu brechen? Wir haben ein paar Optionen hier, aber das einzige, das geht sicher zu sein ist es, Nachrichten nächsten Zeiger zu setzen Punkt zum alten Kopf der Liste oder was wird bald die alte Spitze der Liste. Und jetzt, da alle unsere Elemente werden miteinander verkettet, wir können einfach bewegen Liste zu Punkt an der gleichen Stelle, die neuen tut. Und wir haben nun effektiv geschoben a neues Element auf der Vorderseite des Stapels. 

Um wir wollen einfach nur Pop- löschen Sie diese erste Element. Und so im Grunde, was Wir haben hier zu tun, auch wir haben, um das zweite Element zu finden. Schließlich, dass das neue geworden Kopf, nachdem wir die erste löschen. Also müssen wir nur noch aus starten der Anfang, verschieben Sie eine nach vorn. Sobald wir einen Halt auf der einen stand vorne, wo wir aktuell sind wir die erste sicher löschen und dann können wir nur den Kopf bewegen zu dem, was war, zeigen die zweite Amtszeit und jetzt dann ist das erste danach Knoten gelöscht wurde. 

Also noch einmal, sich einen Blick es als ein Diagramm wir will jetzt ein Pop- Element weg von diesem Stapel. Also, was machen wir? Nun wir zuerst zu erstellen ein neuer Zeiger, die gehen an der gleichen Stelle wie der Kopf zeigen. Wir werden sie um eine Position vorne mit den Worten trav equals trav nächsten zum Beispiel, die würde die trav Zeiger einem voran Position nach vorne. Jetzt, wo wir haben ein Halten Sie auf dem ersten Element durch den Zeiger namens Liste und die zweite Element durch einen Zeiger namens trav, können wir sicher zu löschen, dass das erste Element aus dem Stapel ohne den Rest zu verlieren der Kette, weil wir eine Möglichkeit haben, beziehen an dem zweiten Element mitteln über das Zeiger namens trav. 

So, jetzt können wir diese Knoten zu befreien. Wir können die Liste zu befreien. Und dann alles, was wir jetzt tun müssen, ist, bewegen Liste Punkt an der gleichen Stelle dass trav tut, und wir sind Art von Rück wo wir angefangen haben, bevor wir 12 geschoben auf in den ersten Platz, richtig. Das ist genau das, wo wir waren. Wir hatten diese vier Elementstapel. Wir haben ein Fünftel. Wir schoben einen fünften Element auf, und dann werden wir geknallt, dass die zuletzt Mehrelement wieder aus. 

Das ist wirklich ziemlich alles, was man stapelt. Sie können sie als Arrays zu implementieren. Sie können sie als verkettete Listen zu implementieren. Es gibt natürlich andere Möglichkeiten, auch diese zu implementieren. Grundsätzlich ist der Grund, warum wir verwenden würden, Stapeln ist es, Daten in unter- halten dass der zuletzt hinzugefügten Element ist das erste, was wir sind gehen zu wollen, zurück zu bekommen. Ich bin Doug Lloyd, ist dies CS50.