Informatik Anfänger Kurs | ADTS - Queue & Stack | Deutsch #1
CyberCake
https://www.youtube.com/watch?v=ruX2fJ0Q9B0

Transkript (automatisch erstellt)

0:00 herzlich willkommen bei einer neuen Videoreihe heute soll es um adts gehen diese Videoreihe geht ein bisschen über Informatik im generellen trotzdem aber
0:10 noch in der Anwendung mit Java ich werde euch heute zeigen wie Stacks und wieqs funktionieren nicht nur im Code sondern erstmal auch logisch
0:19 dass ihr überhaupt das Konzept versteht danach gehen wir noch auf die praktische Anwendung ein und dann zeige ich euch noch wie man Stacks miteinander
0:29 sortieren kann so ich werde euch jetzt einmal meinem Tablet bisschen versuchen zu zeigen wie Stacks und wieqes funktionieren manche von euch haben wir
0:38 vielleicht schon mal von FIFO und LIFO gehört das sind zwei Konzepte FIFO steht für first in first out ich hoffe man kann meine Schrift halbwegs lesen wenn
0:52 ich Pech gehabt Leo steht dabei für Last in first out das sind also die beiden Konzepte die wir uns hier anschauen wir fangen an mit LIFO LIFO gehört zum Stack
1:06 also Stack gleich Lio so was heißt das jetzt erstmal n Stack ein Stack besteht immer aus mehreren Elementen das können z.B Zahlen sein das können auch Texte
1:19 sein mal angenommen wir haben jetzt ein Stack mit Zahlen dann hat jede Zahl ein eigenes Objekt also wir haben hier einen Würfel da ist z.B die 1 drin dann haben
1:33 wir noch ein Würfel jer Würfel ist jetzt hier ein Element da ist z.B die fün drin und diese Würfel kann ich aufeinander stacken wir haben dann in dem Stack von
1:44 oben nach unten mehrere Objekte mal angenommen ich packe jetzt die ein auf den Stack dann sage ich hier ist die ein dann packe ich jetzt noch das höchste
1:55 Element auf den Stck z.B die fün das kann ich jetzt einfach mal weiterführen und dann haben wir hier die 7 die 3 die 5 und die 1 auf unserem Stack jetzt
2:05 haben wir ja das Leo Prinzip also Last in first out für uns heißt das jetzt das letzte Element das drauf gepackt wurde ist das erste Element das auch wieder
2:14 rausnehmen können das letzte Element war jetzt in unserem Fall die 7 die S ist also auch die erste die wir wieder rausnehmen möchten wir den Stapel
2:23 jetzt also wieder abbauen dann würden wir zuerst die S runternehmen wir packen also die sie auf unseren nächsten Stapel drauf und zwar hier dann nehmen wir die
2:34 S von hier oben runter das heißt für uns quasi dass wir an die ein hier unten nicht rankommen solange wie wir nicht diese beiden Elemente runtergepackt
2:43 haben wir könnten jetzt also die D hier auch mit auf unseren Stapel tun das sehe dann so aus jetzt hätten wir zwei Stapel wir könnten auch wieder von unserem
2:55 rechten Stapel die D hier drauf packen was wir nicht machen können ist irgendwie an diese sieben zu kommen um an die sieben zu kommen müssen wir die
3:03 drei zuerst nach hier drüben packen so jetzt können wir uns die sieben nehmen und wieder zurückpacken das ist der sogenannte Stack das erste
3:13 Element was drauf kommt ist immer das unterste das können wir jetzt hier einfach mal markieren das ist quasi
3:21 das das hier ist quasi das unterste und das hier ist das oberste an das oberste kommen wir in dem Fall zuerst dran an das unterste
3:32 zuletzt das ist der Stack dann gibt es ja noch Last in first out das ist die sogenannte Q Q und Deck können wir uns auch noch
3:43 ein bisschen irwan sprachlicher merken eine Q ist im Grunde genommen dasselbe wie eine Warteschlange Warteschlange kennt ihr von dem Einkaufsladen das hier
3:52 ist unser Laden natürlich sehr schön gezeichnet und hier vor haben wir Leute Person Nummer 1 Person Nummer 2 und Person Nummer 3
4:00 was bei einer Schlange passiert ist dass wir hinten immer wieder neue Elemente draufpacken von hier hinten kommt also z.B Person Nummer
4:10 4 abgearbeitet werden die Elemente in einer Schlange aber vorne das heißt diese Person ist die erste Person die bearbeitet wird diese Person war auch
4:21 die erste Person von diesen Vieren die an diese Warteschlange rangegangen ist deshalb nennen wir das ganze hier FIFO first in first out das heißt in unserem
4:33 Fall die erste Person die gekommen ist ist die erste Person die die Schlange auch wieder verlässt das ganze können wir uns jetzt auch mal in dieser
4:42 elementweise anschauen ich er stell mal einfach eine neue Seite wir möchten jetzt also wieder Elemente zu unserer Schlange hinzufügen zu unserer
4:50 Q das heißt ich packe hier mal wieder das Element 1 drauf packe ich jetzt noch ein Element dazu dann kommt so gesehen nicht oben
5:00 drauf sondern wir machen das mal bildlich das kommt links ran ich würde euch generell empfehlen falls ihr euch das ganze mal auf Papier
5:09 veranschaulichen wollt dass ihr den Stack von oben nach unten macht und die que von rechts nach links ich zeige euch auch gleich warum wenn wir jetzt auf die
5:22 Q was drauf packen haben wir die 1 die 3 dann haben wir hier die 7 und die F bei einem Stack wäre jetzt die 5 das erste Element was genommen wird da das
5:36 ja auch das letzte Element ist was hinzugefügt wurde Beier Q funktioniert das Ganze anders herum das erste Element was
5:48 gekommen ist das ist in dem Fall unsere ein ist auch das erste Element was verschwindet nehmen wir jetzt also ein Element von Q herunter dann nehmen wir
5:57 nicht die 5 sondern die 1 und packen die jetzt z.B mal auf eine neue Schlange mal angenommen wir nehmen uns jetzt wieder ein Objekt aus der ersten
6:06 Schlange dann nehmen wir uns die drei und fügen die hinten wieder an das ist also unser first in first out Prinzip noch mal zum Vergleich bei
6:17 unserem Stack ist das hier das ist das hier das Element was wir zuletzt hinzugefügt haben und das hier das Element was wir
6:27 zuerst hinzugefügt haben das Element was wir zuerst hinzugefügt haben können wir auch erst zuletzt holen und das Element was wir zuletzt hinzugefügt haben können
6:36 wir uns als erstes holen bei der Q ist es anders herum das Element was wir zuerst hinzugefügt haben können wir uns auch als erstes Wied neehmen das Element
6:45 was wir zuletzt hinzugefügt haben können wir uns auch erst als letztes wieder nehmen das führt so gesehen zu einem gewissen Umkehreffekt ich kann jetzt
6:53 dieq mal wieder richtig aufbauen das heißt wir haben wir hier markiert das ist rote ist das Element was wir uns zuerst holen können das blaue was wir
7:01 uns zuletzt holen können in diesem Fall ist der Kopf der Schlange was wir uns zuerst holen können das hier und was wir uns zuletzt holen
7:11 können ist das hier und das sind so gesehen unsere QES und unsere Schlangen zumack können wir uns das ganze auch noch mal ein bisschen veranschaulichen
7:22 und zwar ist ein Stack ein bisschen wie ein Warenkorb ist auch ein gern genutztes Beispiel in z.B Prüfungen wir haben jetzt hier unseren sehr
7:32 stylischen Einkaufswagen nur dass ich das mal sagen darf und wir packen jetzt in unseren Einkaufswagen Boxen rein das ganze hier ist ja unser
7:42 Stack und ich packe jetzt hier eine Box rein und da ist Käse drin ist auch egal Käse ist mal die ein und dann packen wir das Wurst rein das ist die
7:53 2 wie wir jetzt schon sehen die Wurst haben wir hier als erstes Element reingepackt doch über der Wurst liegt der Käse das heißt der Käse das Element
8:03 was wir zuletzt reingepackt haben müssen wir auch zuerst rausnehmen um an unsereen Käse ranzukommen das heißt wir nehmen erst
8:10 die Wurst raus und dann den Käse raus das heißt steacks und es haben verschiedene Anwendungsfälle haben wir z.B eine Schlange vor einem Laden dann
8:20 nehmen wir eine UE haben wir z.B ein containerschift dann nehmen wir ein Deck denn physikalisch würden wir jetzt bei einem Containerschiff an die untersten
8:29 Container erst rankommen wenn wir die darüber rausgenommen haben so nachdem wir jetzt geklärt haben wie Stacks und wie QES funktionieren kommen wir mal
8:37 einmal zu der Implementierung in Java zu allererst einmal werde ich einen Stck erstellen dafür nehme ich den dentyp Deck und jetzt haben wir hier eine
8:46 kleine Neuerung und zwar das größer klein als dazwischen geben wir den Datentypen an der das Deck später haben soll in unserem Fall wollen wir jetzt
8:56 einfach mal integer aufeinander stcken das heißt ich gebe ihm hier integer rein jetzt braucht die Variable einen Namen ich nenne sie mal ganz einfach Stack da
9:07 steck ja auch eine Klasse ist kann ich davon ein Objekt erstellen mit new deck das ist jetzt mal ganz einfach um inj etwas auf den Stack drauf zuacken können
9:17 wir stack. Push eingeben er schlägt uns dann hier auch gleich den Datentypen vor den wir ja hier oben angegeben haben da könnten auch Strings drin liegen oder
9:26 auch andere Objekte wie z.B das Auto aus der letzten ich möchte jetzt einfach mal ein paar Zahlen auf den ST packen z.B die ne und
9:35 dann noch ein paar weitere und zwar die 5 die D und die 7 die habe ich jetzt alle samt auf den Stack gepackt nun WIS W zuerst wird die
9:47 ne auf den steck gepackt darüber wird die 5 gelegt darüber die D und darüber die 7 jetzt können wir uns das ja einfach mal ausgeben lassen dafür
9:56 schreibe ich eine Schleife und sage dann stack. ist empty ist empty gibt un zurück ob im Stack aktuell noch Werte drin liegen oder
10:06 nicht mit dem Ausrufezeichen vernein ich dieses das heißt die W Schleife soll läuft so lange wie noch ein Objekt im Stack enthalten ist so während das wahr
10:19 ist soll er uns das oberste Element des Stacks ausgeben ich schreibe noch mal Stack Doppelpunkt davor damit wir später auch wissen was zu was gehört und dann
10:29 sage ich stack. pop stack. pop hat jetzt zwei Aufgaben zum einen gibt es uns das oberste Element des Decks zurück das sollte am Anfang die Sieben sein denn
10:43 die sieben liegt ja ganz oben zudem entfernt poppt das Element auch noch das heißt es nimmt sich die sieben gibt es aus und entfrt die sieben vom Stck
10:54 danach macht es das mit der 3 der 5 und der neun soweit die Theorie mal schauen ob das in Praxis auch noch funktioniert und wir sehen 7 3 5 9 in dem Fall jetzt
11:07 von unten nach oben weil man im Stack das erste Element nach ganz unten gelegt hat das ganze können wir uns jetzt auch mal für die Q
11:17 anschauen die Q schreiben wir so ähnlich auch wieder mit dem größer kleiner Symbol und dem integer das ganze n wirq doch das ganze hat eine Besonderheit und
11:29 zw ist selbst keine Klasse selbst ist ein Interface was das ist darauf kommen wir eventuell noch mal irgendwann anders in der Java Videoreihe doch was das für
11:39 uns bedeutet ist dass wir nicht einfach newq schreiben können ich kann mal zeigen was passiert wenn wir das machen hier kommt ein riesiger
11:47 codesalat das wollen wir nicht deswegen schreiben wir in dem Fall hier new Linked List keine weiteren Angaben das fungiert
11:57 quasi als unsereue um jetzt in dieser Queue in Java etwas hinzuzufügen müssen wir q. schreiben manche von euch kennen das
12:06 vielleicht unter dem Befehl NQ ja natürlich richtig schreiben NQ das ist in dem Fall jetzt hier einfach unser ad das können wir also
12:17 Synonym benutzen auch hier möchte ich mal wieder die ne die 5 die 3 und die 7 hinzufügen und wieder oben können wir auch hier
12:26 wieder eine while Schleife machen und Fragen ist der Q nicht empty das ist ja das was diese Verneinung hier vorut auch hier machen wir uns wieder eine Ausgabe
12:37 schreiben jetzt mal Q vor und wir sagen q.pul manche von euch kennen das hier vielleicht als DQ DQ macht im Grunde dasselbe wie
12:49 stack. Pop es nimmt sich das vorderste Element gibt es zurück gibt es hier so aus und entfernt es aus der Liste da beim das FIFO Prinzip haben wird das
13:03 erste Element das reingekommen ist auch wieder rausgenommen in unserem Fall müsste es jetzt also 9 5 37 ausgeben nicht so wie beim Stack 7 359 also in
13:14 quasi umgedrehter Reihenfolge das können wir jetzt auch mal ausprobieren und wir sehen q9537 jetzt hat man hier auch so ein
13:23 ganz schönes Muster und zwar ein ortogramm das heißt man kann es von vorne und von hinten gleich lesen da ja die UE quasi anders herum wie das Deck
13:32 operiert jetzt möchte ich noch mal ein bisschen auf die praktischen Tipps eingehen in Verbindung mit dem Stack die Queue kann ich jetzt dafür erstmal
13:40 wieder entfernen in unserem Beispiel gebe ich ja den Stack
13:49 aus mal angenommen ich erstelle einen neuen Stack und den nennen wir mal Stack 2 soll nicht zu Verwirrung führen statt jetzt die Elemente von Stack auszugeben
14:03 möchte ich Sie einfach auf Stack 2 legen das mache ich indem ich sage Stack 2. Push und dann stack.pp ich nehme mir also die Elemente
14:17 von Stack runter und packe sie wieder auf Stck 2 rauf und dabei sehen wir jetzt ein ganz interessantes
14:25 Phänomen ich sage mal Stack 2 ist empt denn wir möchten uns jetzt einfach mal den zweiten Stack ausgeben und sagen Stack
14:36 2. Pop so ich gebe das ganze einfach mal aus und wir sehen 9537 das ist jetzt nämlich genau die
14:46 umgekehrte Reihenfolge von vorhin im Grunde genommen gibt das Programm unds Deck jetzt so aus wie als hätten wir eine
14:53 denn wir legen die ne rein die 5 rein die D rein und die 7 rein gelesen wird ja dann 7 3 5 9 weil man die Elemente quasi aufeinander legt
15:04 9 ist also das unterste Element stapeln wir jetzt den ursprünglichen Stapel um dann fangen wir wieder mit der sieben an die sieben wird
15:13 also zuerst auf Stack 2 gelegt dann die 3 dann die 5 und dann die 9 die 7 ist dann also nicht mehr das oberste Element sondern nach der ganz einfachen
15:23 Umlagerung das unterste Element wir haben den Stack also einmal umgedreht das kann uns bei relativ vielen Problemen helfen und vor allem auch dann
15:32 wenn wir ein Deck auf oder absteigen sortiert haben wollen mal angenommen ich möchte den steack jetzt sortieren das zeig ich euch mal indem
15:41 wir hier den zweiten steack haben das unten nehme ich mal weg und der zweite Stack der bekommt jetzt auch mal Zahlen dem geben wir z.B die 13 das F ein
15:52 bisschen viel dann kriegt der die die vi und die 2 so jetzt möchten wir diese Stacks miteinander sortieren das ganze wird uns
16:07 jetzt einfacher gemacht wenn wir die Stacks schon absteigen sortiert haben eventuell kennen manche von euch den Merch sort daraus ist uns das ja schon
16:16 ein wenig geläufig wir möchten jetzt einen dritten steck erstellen indem wir das ganze reinsortieren den nenne ich jetzt
16:23 einfach mal result deack in den sortieren wir das ganze rein und jetzt mach machen wir eine wi Schleife solange wie in Stack noch etwas
16:34 drin ist möchten wir dass wir das oberste Element von diesem Stck und das oberste Element von diesem Stack miteinander vergleichen in unserem Fall
16:43 wäre das jetzt hier die zwei und die 1 was wir jetzt wollen ist dass wir die Stacks ineinander packen und sie trotzdem richtig sortiert
16:53 sind das heißt wir vergleichen das oberste Element von Stack mit dem obersten Element von Stack 2 in Java haben wir den get first und get Last in
17:05 der richtigen steckanwendung hat wir nur ein davon ich kann e mal zeigen was die beiden ausgeben so jetzt sehen wir first ist
17:13 Last ist one last ist also in unserem Fall die Zahl die ganz oben liegt und first ist die Zahl die ganz unten liegt die Zahl die ganz unten liegt hätten wir
17:27 bei einem tatsächlichen stake so nicht das heißt wir verwenden jetzt mal nur get Last mit GET Last kann die also das
17:36 oberste Element vergleichen das heißt wir machen mal stack. get Last und fragen ob das kleiner ist als Stack 2 get
17:48 lastast was wir jetzt also damit machen ist die obersten beiden Elemente von steack und Stack 2 zu vergleichen ist also in unserem Fall die
17:59 1 kleiner als die 2 ist das der Fall dann wollen wir die Zahl von Stack 1 auf unseren results Deck legen also
18:11 resssteck. Push Stack Pop wir nehmen also das oberste Element vom Stck runter ist das nicht
18:21 der Fall dann bedeutet das ja dass die oberste zeillen steck 2 gleich groß oder größer ist sind sie gleich groß ist es quasi egal von welchem Stack wir die
18:31 Zahl runternehmen ist sie größer dann können wir sie ja von Stack 2 runternehmen das heißt wir machen uns ein els und nehmen von Stack 2 das
18:43 runter und packen es auf resultck Stck 2. Pop so jetzt könnten wir ja das Problem haben dass nicht steack 1 zuerst
18:56 durchgelaufen ist sondern 2 in dem Fall hat er keine zu vergleichenden Werte mehr das heißt wir packen uns hier noch mal eine
19:06 unbedingung rein und sagen Stck 2 soll auch nicht empty sein ist jetzt ein der beiden Stacks leer dann ist ein Stack mit nur größeren Zahlen übrig den müssen
19:21 wir dann nach unserer Schleife noch hinzufügen können wir also gucken ist empty dann müsste ja in Stack 2 noch etwas drin liegen wir sagen also während
19:36 Deck 2 noch nicht MT wollen wir auf den results Deck 2 machen in dem Fall das auf Stack noch was drauf ist wollen wir zahlen von
19:50 Stack auf den res result Stack drauf packen DAF kopiere ich mir einmal das hier wir sagen
19:59 W wir auf den Stack drauf packen das können wir uns jetzt einfach einmal anschauen dafür gebe ich alles aus dem Stack dafür gebe ich alles aus dem
20:10 result Stck aus das ganze will ich mal einmal aus und wir sehen 1398 5 4
20:19 321 wir haben jetzt also beide Stacks ineinander gemerged wichtig ist dass bei diesem Verfahren beide Stacks vorsortiert sein müssen wenn ich jetzt
20:31 hier mittend drin eine 14 z.B habe dann funktioniert das ganze nicht mehr dann sehen wir 9 14 13 8 und so
20:40 weiter das funktioniert also nicht dieses Sortierverfahren funktioniert nur für vorsortierte Listen also für Listen die von oben nach unten schon korrekt
20:49 sortiert sind und jetzt kommen wir wieder zu unserem Anwendungsfall von vorhin mal angenommen wir wollen diese sortierte Liste jetzt nicht vom größten
20:56 zum kleinsten ausgeben sondern vom kleinsten z zum Größen dann können wir hier vor hingehen und sagen wir erstellen uns einen neuen
21:04 deack und in diesen möchte ich den results Deck flippen wir sagen also wieder ist empty mit der Verneinung davor solange also wie es nicht le wir
21:15 können auch übrigens doppelte und dreifache Verneinungen machen ich würde davon aber abraten und dann sagen wir
21:24 fliptppush salzdeck.pp was wir damit jetzt machen ist wir nehmen uns wieder das oberste Element von result also die 13 und fügen
21:34 Sie zuerst ein das heißt 13 ist da nicht mehr das oberste Element sondern das unterste Element anstatt uns jetzt hier results Deck auszugeben geben uns jetzt
21:44 hier einfach mal flit aus und wir sehen es startet nicht mehr beim größten sondern beim kleinsten und es immer noch vollständig sortiert das soll es auch
21:53 erstmal soweit zu Stacks und es gewesen sein ich hoffe dieses Video hat euch geholfen und ich denke mal dass es zu dieser Videoreihe noch mehrere Videos
22:05 geben wird wir haben ja z.B noch die normalen listen wir haben binary trees und mal schauen was sonst noch so kommt ich hoffe wir sehen uns bald wieder bis
22:16 dahin ciao