Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
EIG: Abstrakter Datentyp Keller
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 84 Zeilen
- willkommen zur Einführung Informatik für Geisteswissenschaftler dieses Video ist entstanden im Rahmen der gleichnamigen Veranstaltungen der Universität
- Paderborn in diesem Video wollen wir uns den nächsten abstrakten Datentyp angucken nämlich den Keller wir hatten im letzten Video schon die Schlange
- kennengelernt als einen einfachen abstrakten Datentyp und hier ergänzen wir das nun um einen zweiten Typus der Keller ist ein bisschen anders aufgebaut
- man kann ihn sich vorstellen wie ein Bücherstapel bei dem ein neues Buch immer nur oben auf den Stapel gelegt werden kann und doch nur oben vom Stapel
- herunter genommen werden kann auf Englisch heißt der Keller Stack was auch mit Stapel übersetzt werden kann und eigentlich sogar die bessere Bezeichnung
- als Keller ist warum das auf deutsch meist als Keller bezeichnet wird weiß ich ehrlich gesagt gar nicht den Stapel trifft es eigentlich viel besser man
- darf nicht zwischendurch auf die einzelnen Elemente zugreifen also irgendwo mittendrin ein Buch herausnehmen das ist schlicht und
- ergreifen nicht erlaubt dafür bei der Schlange das Prinzip fast in first out hatten das heißt was immer zuerst in die Schlange eingefügt wurde auf das erste
- Element das wieder entfernt wurde ist es beim Bücherstapel etwas anders hier wird natürlich weil wir ein Buch oben auf Stapel legen immer das zuletzt
- aufgelegte Buch als erstes wieder entfernt das uns unterste Buch wartet also mitunter sehr sehr lange bis es irgendwann tatsächlich mal dran kommt
- dieses Prinzip nennt man auch liefo-prinzip Last in first out es wird also das Element das zuletzt eingefügt wurde auch als erstes wieder entfernt
- man kann sich das wie gesagt so vorstellen dass man immer Elemente von oben auflegt aber natürlich werden wir das wenn wir das Implementieren nicht zu
- geometrisch darstellen sondern müssen uns dann wieder eine geeignete Datenstruktur ausdenken mit dem wir das abbilden können vergleichen wir das noch
- einmal mit der Schlange vom letzten Mal dann können wir das abstrakt in dieser Art aufmalen die einzelnen Kästchen sind wieder die Elemente die wir in unserem
- Keller haben hier haben wir schon mal einen einen Keller der mit einigen Elementen befüllt ist er könnte aber natürlich auch noch leer sein dann
- hätten wir dann noch kein einziges Kästchen stehen wenn wir jetzt ein neues Element in den Keller einfügen legen es also gewissermaßen oben drauf ein
- Zugriff erfolgt ebenfalls immer nur auf das oberste Element lesen und löschen können wir ausschließlich das oberste Element während alles was da unten im
- Keller oder im Stapel noch drin liegt das wissen wir einfach nicht wir können dann nicht hinein gucken können also nicht einfach mal sagen was ist denn das
- dritte Element von oben wir können auch die Elemente nicht einfach mal durchlaufen also haben wir hier auch wieder ähnlich wie bei der Schlange die
- ganz bewusste Einschränkung auf wenige Operationen die nur zulässig sind und mit diesem keller-objekt ganz bestimmte Aufgaben sehr gut und sehr einfach
- erledigen zu können was für Aufgaben das sind gucken uns zu einem späteren Zeitpunkt noch an ähnlich wie bei der Schlange ist es auch hier so dass die
- Reihenfolge der Elemente im Keller natürlich nicht verändert werden kann wir können nicht mal eben sortieren wir können doch nicht auf einzelne Elemente
- zugreifen wie es gerade schon angedeutet habe all das können wir hier schlicht und ergreifen nicht sondern immer nur auf das oberste Element zugreifen über
- welche Methoden soll nun ein solcher Keller verfügen nun wir haben wieder rechts das Klassen die eragramm auch hier auf Englisch Stack genannt diese
- Klasse würden wir wieder in einer Datei stack.s definieren wenn wir das denn implementieren intern brauchen wir wieder eine Datenstruktur in der die
- Elemente gespeichert werden können die nämlich wieder einfach data das kann wieder ein Array sein wird bei uns auch tatsächlich wieder ein Array sein aber
- das ist an dieser Stelle wie gesagt mal wieder uninteressant weil es eine private Eigenschaft ist auf die wir niemals von außerhalb zugreifen wollen
- bei der Implementierung der Methoden der Klasse müssen wir auf diese Eigenschaft zugreifen ähnlich wie wir das bei der Schlange gesehen haben aber ansonsten
- greifen wir auf diese interne Datenstruktur niemals zu sondern verwenden ausschließlich die vier Methoden die uns die Klasse ist Weg zur
- Verfügung stellt um auf die Keller Objekte zuzugreifen die Methoden die für diesen Datentyp definiert sind sind Push zum Hinzufügen eines Elements zu dem
- Keller bedruckten etwas oben auf den Stapel drauf Pop wer entfernt das oberste Element vom Schnabel top wir gucken nach was oben auf dem Stapel
- drauf liegt und endlich wir gucken wieder einfach nach ob irgendetwas im Keller drin ist insgesamt ist das also ganz ähnlich wie das was wir bei der
- Schlange gesehen haben da ist eine Methoden etwas anders die einzige Methode die bei beiden Objekten gleich heißt NQ hinten zu
- Hinzufügen und Entfernen von Elementen dort zum Anschlagen und abschlagen sozusagen Front um zu gucken was das war das Element der Schlange ist beim Keller
- heißt es die entsprechend zuletzt und top weil wir von oben auf den Fehler drauf gucken die Operation zum Hinzufügen und Entfernen das sind Push
- und Pop und die kommen uns schon irgendwie bekannt vor denn die haben wir bei Arrays schon gesehen bei den Arrays habt ihr euch vielleicht ein wenig
- gewundert warum diese Methoden diese komischen Namen tragen aber jetzt dann Keller bzw Stapel ist das vielleicht ein bisschen verständlicher wir drücken
- etwas oben auf den Stapel drauf wir entfernen etwas oben vom Stapel daher kommen diese Namen und die Namen haben sich sozusagen zum Erl durchgesprochen
- man hat sie für das übernommen weil sie beim Eric ganz ehrlich funktioniert und wenn wir unser Objekt gleich geschickt implementieren wird die Implementierung
- sehr trivial werden wir werden dafür benutzen wir bleiben aber zunächst noch einmal bei dem abstrakten Datentyp wo wir über die Realisierung noch nicht
- sprechen wir können nun ein Keller erzeugen wie wir das hier links in dem Beispiel Code sehen mit LED K also beliebiger variable name natürlich wie
- immer gleich wird hier jetzt ein neues Keller Objekt erzeugt der Kelle ist an dieser Stelle noch leer es ist noch nicht drin jetzt können wir den Keller
- etwas einfügen wir fügen wieder eine Zeichenkette ein das erste Element dass ich einfügen möchte sein ah das zweite ist die Zeichenkette die aus
- dem B besteht und hier sehen wir jetzt dass der Keller gewissermaßen nach oben wächst wie gesagt bei einem Array wächst nichts in eine Himmelsrichtung nach oben
- unten links oder rechts da werden wir uns gleich einmal überlegen müssen wir das mit einem geschickt umsetzen können aber man kann sich das wie gesagt so
- vorstellen wenn das ein Stapel wäre würde dieser jetzt von unten nach oben wachsen der Anfang unseres Stapels den ich hier wieder mit dem Namen der
- Variablen gekennzeichnet habe ich jetzt nach oben gewandert das ist anders als bei der Schlange vergleicht das noch einmal mit dem letzten Video und ihr
- werdet sehen dass der Schlangenkopf sich anders verhält als hier die Spitze des Kellers und wenn wir das nächste Element einfügen wandert das natürlich auch
- wieder oben auf den Keller und wenn wir jetzt beispielsweise die Methode MT aufrufen würden würde natürlich falls zurückbekommen denn unser Keller ist ja
- nicht leer das wäre er ganz am Anfang gewesen auf dem weder zeugt und bevor wir das erste Element eingefügt haben wir können außerdem z.B die Methode top
- aufrufen die wird uns jetzt das C zurückliefern also die Zeichenkette C weil dies das oberste Element auf unserem Speck ist natürlich für Sie den
- Keller unverändert belassen wenn wir nun hingegen top aufrufen wird uns ebenfalls dieses oberste Element also C zurückgeliefert aber gleichzeitig wird
- dieses Element natürlich aus dem Keller entfernt die Methode Pop liefert also das Element zurück und der Keller ist wieder geschrumpft die Spitze des
- Kellers ist sozusagen wieder einen nach unten gewandert das ist eigentlich schon alles was man zum Keller sagen kann außer natürlich dass wir jetzt noch
- implementieren wollen das machen wir ganz ähnlich wie wir das beim letzten Mal mit der Schlange gemacht haben wir implementieren den Stack nun kurz und
- ebenfalls mit einem area als interner Datenstruktur wir schreiben zunächst wieder ein Konstrukt oder nichts anderes macht als einfach eine leere
- Datenstruktur zu erzeugen in der wir die Elemente ablegen können das können wir auch anders machen aber es ist schon sehr sinnvoll wenn wir das einfach mit
- einem machen was bedeutet es nun ein Element im Keller hinzuzufügen das bedeutet dass wir das Element dieser internen Datenstruktur hinzufügen müssen
- wenn also die Methode pusht es Kellers einen Wert übergeben bekommt dann nehmen wir den einfach und pushen ihn in das Array hinein wie ihr euch erinnert fügt
- die Methode pusht dass er recht dass ihr übergebene Element hinten an das an unser wächst also offenbar nach rechts hier ist der Anfang des Arrays und das
- wandert jetzt in diese Richtung das heißt es werden Elemente angefügt angefügt angefügt angefügt und das bedeutet natürlich dass anders als bei
- der Schlange wo Front das vorderste Element war top jetzt natürlich das hinterste Element ist und das sehen wir dann auch hier schon in dem
- Implementierung der Methode top die wieder als drittes auf der linken Seite der Folie stehen haben diese Methode fragt wieder wie schon Front bei der
- Schlange erst einmal ab ob unser Keller überhaupt irgendwelche Elemente enthält wenn das nicht der Fall ist gehen wir nicht zurück das ist wieder eine
- ähnliche Überlegung wie im letzten Video die man da anstellen muss das also nichts zurückgegeben werden wenn ihr Topf für einen leeren Keller aufgerufen
- wurde und top wäre an die Feind wie wir das bei Front bei der Schlange schon gesehen haben ansonsten müssen wir nun nicht wie bei der Schlange ganz vorne
- gucken sondern wir müssen uns das letzte Element angucken das letzte Element so wissen wir finden wir im airray Wissen Punkt data an der Stelle lenken minus 1
- der Link ist die Anzahl der Element und wir fangen immer bei Null an zu zählen das liefert uns also das letzte Element sind und das ist das was wir von Top
- erwarten mit Pop können wir im Prinzip auch genau auf dieses Element zugreifen und das kurze Hand zurückliefern müssen es dann aber noch entfernen ja das
- können wir doch ganz einfach machen wie wir das schon kennengelernt haben die Methode Pop für Array macht ja genau dass sie entfernt das letzte Element aus
- dem Arian gibt es zurück und genau das wollen wir hier natürlich auch machen wir wollen aus unserem internen arrivedespunkt data das letzte Element
- entfernen und zurückgeben wir nehmen also den Rückgabewert von Display data.com und geben diesen Wert also Rückgabewert der Methode Pop unseres
- Kellers zurück auch hier müssen wir wieder Vorsicht warten lassen denn wenn unser Keller leer ist bedeutet das dass in unserem internen Erik keine Elemente
- enthalten sind wenn wir aber für einen leeres Array die Methode Pop aufrufen was liefert sie denn dann zurück das wie gesagt muss man noch einmal in der
- Dokumentation nachgucken und dann den Leuten die unseren Keller verwenden wollen mitteilen zu können was denn unser Keller als Rückgabewert von
- zurückliefert wenn diese Methode für ein leeren Keller aufgerufen wird wir schauen das jetzt gerade mal nicht in der Dokumentation nach aber ihr könnt ja
- mal selber nachschauen was da eigentlich passiert oder es natürlich natürlich auch einfach ausprobieren und testen was in diesem Fall geschieht zu guter Letzt
- haben wir noch die Methode MT wenn ihr die mit der gleichnamigen Methode der Schlange vergleicht seht ihr dass diese ganz ähnlich ist wir gucken schlicht und
- ergreifend nach ob die Länge des internen RS 0 ist wenn das der Fall ist heißt dass ihr das nicht enthalten ist das also unser Keller leer ist in dem
- Fall geben wir daher Crew zurück sonst gehen wir vor uns zurück auch hier will ich wieder darauf hinweisen dass die Methode hier komplizierter als nötig ist
- das kann man viel kürzer und viel knapper schreiben aber auch hier will ich das wieder nicht machen weil das auch ein kleines bisschen verwirrend ist
- damit sind wir im Grunde genommen schon mit der datenstrukturell Keller durch und wir haben neben der Schlange jetzt eine weitere Datenstruktur von der uns
- vielleicht fragen und was will man mit diesem Dingern jetzt eigentlich das werden uns aber in der Vorlesung und auch in den Übungen noch angucken da
- werden uns Anwendungen für genau solche abstrakten Datentypen noch ansehen das ist aber nicht mehr Gegenstand dieses Videos tschüss bis zum nächsten Video