Zum Inhalt springen
L

Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

Informatik Anfänger Kurs | ADTS - Queue & Stack | Deutsch #1

CyberCake22:18 53 Aufrufe veröffentlicht Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 130 Zeilen
Herunterladen
  1. herzlich willkommen bei einer neuen Videoreihe heute soll es um adts gehen diese Videoreihe geht ein bisschen über Informatik im generellen trotzdem aber
  2. noch in der Anwendung mit Java ich werde euch heute zeigen wie Stacks und wieqs funktionieren nicht nur im Code sondern erstmal auch logisch
  3. 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
  4. sortieren kann so ich werde euch jetzt einmal meinem Tablet bisschen versuchen zu zeigen wie Stacks und wieqes funktionieren manche von euch haben wir
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. Element was drauf kommt ist immer das unterste das können wir jetzt hier einfach mal markieren das ist quasi
  20. 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
  21. 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
  22. ein bisschen irwan sprachlicher merken eine Q ist im Grunde genommen dasselbe wie eine Warteschlange Warteschlange kennt ihr von dem Einkaufsladen das hier
  23. 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
  24. was bei einer Schlange passiert ist dass wir hinten immer wieder neue Elemente draufpacken von hier hinten kommt also z.B Person Nummer
  25. 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
  26. 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
  27. 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
  28. elementweise anschauen ich er stell mal einfach eine neue Seite wir möchten jetzt also wieder Elemente zu unserer Schlange hinzufügen zu unserer
  29. 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
  30. 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
  31. 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
  32. 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
  33. ja auch das letzte Element ist was hinzugefügt wurde Beier Q funktioniert das Ganze anders herum das erste Element was
  34. 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
  35. 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
  36. 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
  37. unserem Stack ist das hier das ist das hier das Element was wir zuletzt hinzugefügt haben und das hier das Element was wir
  38. 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
  39. 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
  40. 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
  41. 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
  42. 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
  43. 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
  44. 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
  45. stylischen Einkaufswagen nur dass ich das mal sagen darf und wir packen jetzt in unseren Einkaufswagen Boxen rein das ganze hier ist ja unser
  46. 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
  47. 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
  48. was wir zuletzt reingepackt haben müssen wir auch zuerst rausnehmen um an unsereen Käse ranzukommen das heißt wir nehmen erst
  49. 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
  50. 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
  51. 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
  52. 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
  53. 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
  54. 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
  55. 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
  56. 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
  57. 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
  58. 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
  59. 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
  60. 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
  61. 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
  62. 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
  63. 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
  64. 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
  65. 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
  66. 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
  67. 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
  68. 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
  69. 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
  70. codesalat das wollen wir nicht deswegen schreiben wir in dem Fall hier new Linked List keine weiteren Angaben das fungiert
  71. quasi als unsereue um jetzt in dieser Queue in Java etwas hinzuzufügen müssen wir q. schreiben manche von euch kennen das
  72. 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
  73. 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
  74. 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
  75. 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
  76. 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
  77. 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
  78. quasi umgedrehter Reihenfolge das können wir jetzt auch mal ausprobieren und wir sehen q9537 jetzt hat man hier auch so ein
  79. 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
  80. 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
  81. wieder entfernen in unserem Beispiel gebe ich ja den Stack
  82. 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
  83. 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
  84. von Stack runter und packe sie wieder auf Stck 2 rauf und dabei sehen wir jetzt ein ganz interessantes
  85. Phänomen ich sage mal Stack 2 ist empt denn wir möchten uns jetzt einfach mal den zweiten Stack ausgeben und sagen Stack
  86. 2. Pop so ich gebe das ganze einfach mal aus und wir sehen 9537 das ist jetzt nämlich genau die
  87. umgekehrte Reihenfolge von vorhin im Grunde genommen gibt das Programm unds Deck jetzt so aus wie als hätten wir eine
  88. 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
  89. 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
  90. 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
  91. Umlagerung das unterste Element wir haben den Stack also einmal umgedreht das kann uns bei relativ vielen Problemen helfen und vor allem auch dann
  92. 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
  93. 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
  94. bisschen viel dann kriegt der die die vi und die 2 so jetzt möchten wir diese Stacks miteinander sortieren das ganze wird uns
  95. 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
  96. ein wenig geläufig wir möchten jetzt einen dritten steck erstellen indem wir das ganze reinsortieren den nenne ich jetzt
  97. 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
  98. 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
  99. 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
  100. 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
  101. der richtigen steckanwendung hat wir nur ein davon ich kann e mal zeigen was die beiden ausgeben so jetzt sehen wir first ist
  102. 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
  103. bei einem tatsächlichen stake so nicht das heißt wir verwenden jetzt mal nur get Last mit GET Last kann die also das
  104. oberste Element vergleichen das heißt wir machen mal stack. get Last und fragen ob das kleiner ist als Stack 2 get
  105. 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
  106. 1 kleiner als die 2 ist das der Fall dann wollen wir die Zahl von Stack 1 auf unseren results Deck legen also
  107. resssteck. Push Stack Pop wir nehmen also das oberste Element vom Stck runter ist das nicht
  108. 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
  109. 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
  110. runter und packen es auf resultck Stck 2. Pop so jetzt könnten wir ja das Problem haben dass nicht steack 1 zuerst
  111. durchgelaufen ist sondern 2 in dem Fall hat er keine zu vergleichenden Werte mehr das heißt wir packen uns hier noch mal eine
  112. 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
  113. 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
  114. 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
  115. Stack auf den res result Stack drauf packen DAF kopiere ich mir einmal das hier wir sagen
  116. 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
  117. result Stck aus das ganze will ich mal einmal aus und wir sehen 1398 5 4
  118. 321 wir haben jetzt also beide Stacks ineinander gemerged wichtig ist dass bei diesem Verfahren beide Stacks vorsortiert sein müssen wenn ich jetzt
  119. hier mittend drin eine 14 z.B habe dann funktioniert das ganze nicht mehr dann sehen wir 9 14 13 8 und so
  120. weiter das funktioniert also nicht dieses Sortierverfahren funktioniert nur für vorsortierte Listen also für Listen die von oben nach unten schon korrekt
  121. sortiert sind und jetzt kommen wir wieder zu unserem Anwendungsfall von vorhin mal angenommen wir wollen diese sortierte Liste jetzt nicht vom größten
  122. zum kleinsten ausgeben sondern vom kleinsten z zum Größen dann können wir hier vor hingehen und sagen wir erstellen uns einen neuen
  123. 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
  124. können auch übrigens doppelte und dreifache Verneinungen machen ich würde davon aber abraten und dann sagen wir
  125. fliptppush salzdeck.pp was wir damit jetzt machen ist wir nehmen uns wieder das oberste Element von result also die 13 und fügen
  126. 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
  127. 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
  128. 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
  129. 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
  130. dahin ciao

Zum Nachlesen

Warteschlange (Datenstruktur)In der Informatik bezeichnet eine Warteschlange (englisch queue [kju]) eine häufig eingesetzte Datenstruktur. Sie dient als Puffer zur Zwischenspeicherung … StapelspeicherAbstrakter Datentyp. Bearbeiten. Bei der Implementierung eines Stapelspeichers als abstrakter Datentyp in einer einfach verketteten Liste wird der Zeiger auf … Abstrakter DatentypEin Abstrakter Datentyp (ADT) ist ein Verbund von Daten zusammen mit der Definition aller zulässigen Operationen, die auf sie zugreifen. DatenstrukturIn der Informatik und Softwaretechnik ist eine Datenstruktur ein Objekt, welches zur Speicherung und Organisation von Daten dient. Es handelt sich um eine …