Video 8-3: Stacks und Queues

0:04 Neben den linearen Listen, die wir im letzten Kapitel definiert haben, gibt es eingeschränkte abstrakte Datentypen. Stacks andes, werde ich gleich mehr zu sagen und noch ein dritten oder ein vierten je nach Zähne, die eigentlich alle nur Teile dessen tun, was eine lineare Liste tun könnte, aber die trotzdem ihre Daseinsberechtigung haben aus verschiedenen Gründen. Deswegen ähm schauen wir uns die hier an. Die zwei wichtigsten davon sind definitiv die auch im Titel äh dieser dieses Abschnittsaufttauchen Stacks und haben sie v vielleicht auch schon gesehen oder verwendet. Theoretisch brauchen wir keine neuen Implementierung. An ein paar Stellen habe ich dann doch noch eine andere Implementierung angegeben und mit der gestartet. werden sie sehen, die sind oft ein bisschen leichter, auch wenn man es streng genommen nicht machen müsste. Äh, die zwei Gründe, warum wir diese eingeschränkten abstrakten Datentypen überhaupt verwenden, sind hier aufgeführt. Und ich denke, der erstere ist fast so der wichtigere, den Sie im Hinterkopf behalten sollten. Wenn ich jemandem kommunizieren möchte, dass ich mit einer linearen Liste arbeiten kann, aber eigentlich nicht die volle Funktionalität brauche, dann kann ich das tun, indem ich das Interface, gegen das ich dann programmiere in Softwareentwicklungssprache enger fasse, als das Allgemeine, das eine Liste anbieten könnte.

1:29 Und das sorgt eben dafür, dass jemand anderes, der Ihnen so eine Liste zur Verfügung stellt, auch eventuell Optimierung vornehmen kann später noch. ähm die uns vielleicht jetzt noch gar nicht klar waren, ohne dass er prüfen muss, ob ihr Code damit zurecht kommt, denn sie haben überall nur den allgemeinen Teil von, sagen wir verwendet. dann muss ihr Code auch funktionieren, wenn ich dann eine andere Queue einsetze. Insbesondere auch ähm diese Position und diese ähm Diskrepanz in der Bedeutung, die taucht hier gar nicht mehr auf, wenn Sie gleich sehen. Also, ich denke, das ist der der ähm aus praktischer Sicht wichtigere Punkt. Ähm manchmal kann man tatsächlich auch die Implementierung noch verbessern, wenn man manche Operationen verbietet. werden wir in einem anderen Kapitel noch mal ein besseres Beispiel für sehen. Ist hier bei Stacks und es nur so wenn man ganz genau hinschaut der Fall. Kleine Unterschiede kann man auch hier feststellen.

2:28 Das erste davon ist ein Stack oder zu Deutsch Stapel oder auch das schöne etwas altmodische Kellerspeicher. Ich weiß nicht, wer seinen Keller in Stapeln organisiert. Also äh mein Beileid ähm dass ich Bücher so organisiert habe, kam ab und an mal vor. Vielleicht nicht ganz so hoch. Die Anschauung ist, man kann in so einem Stapel leicht auf das Element oben drauf zugreifen und vielleicht kann man noch sehen, was die anderen Elemente sind. Das ist schon unklar. In der normalen Spezifikation hier kann man es nicht, aber ich kann wirklich nur auf das oberste Element zugreifen aus der Datenstruktur entfernen. Das heißt, ich habe diese zwei Operationen, die einfach diesem dieser Metapher auch geschuldet sind. Ich kann auf das oberste Element drauf schauen. Ich kann ein neues Element noch oben auf den Stapel drauf legen und ich kann das oberste Element entfernen und bekommt das dann zurückgegeben. Das ist auch schon alles. Das ist also viel viel eingeschränkter als so eine allgemeine Liste, an der ich an beliebiger Stelle einfügen kann und überall gucken kann und meine Positionen verschieben kann. Aber wir werden Beispiele sehen, wo eben dieses eingeschränkte Interface ausreicht und dann, wie gesagt, ist es eine Kommunikation.

3:37 Äh, auch hier wieder ähm generisch im typisch im allgemeinen Fall, wir haben einen Stack von irgendwelchen Objekten und ganz ganz oft wollen wir, dass diese Objekte von einem bestimmten Typ sind. Das drücken wir also hier wieder mit Java Generics aus.

3:58 Der zweite große abstrakte Datentyp sind die Warteschlangen oder Qs auf Englisch und Q hat sich auch durchgesetzt meine meine Einschätzung nach als der Fachbegriff im Deutschen für diese Art von abstrakten Datentyp. Warteschlange klingt immer irgendwie ein bisschen sperrig im Vergleich. Da gibt's überhaupt nur zwei Operationen. Ich kann ähm mich hinten anstellen oder ich kann vorne aus der Warteschlange entfernt werden. Das sind die zwei Operationen, die wir machen. Und das ist im Wesentlichen alles. Man könnte äh manchmal ist es bequem, dass man noch so ein Zugriff Peak auf das erste Element gibt, der ist nicht direkt entfernt.

4:37 Beim Stack ist Top im Wesentlichen nicht nötig, denn ich könnte immer Top und dann wieder Push machen. Dann habe ich zwar zwei Operationen statt einer, aber theoretisch könnte ich das Top damit ersetzen. Bei der Que müsste ich eigentlich hier Peak mal mit in die Liste aufnehmen, denn da ist es nicht so leicht zu ersetzen. Ja, wenn ich ein Element aus der Warteschlange vorne entfernt habe und dann wieder hinten einfüge, ist ja die Warteschlange nicht mehr im gleichen Zustand wie vorher. äh geht. Also tatsächlich hier ähm ist vielleicht wichtig, dass wir die haben, aber ist auch äh die einfachste zu implementieren. Okay, also das sind die beiden ähm die beiden wichtigen Einschränkungen. Ähm die haben dann noch diese Abkürzung Fo und Lifo. Wer kennt die? Was ist FO? Ja, genau. Für welche der Datenstrukturen passt es denn? ich mal noch eine Slidofrage zu machen können, damit das auch klar ist. Ja, genau.

5:39 Ähm, könnte man Foq sagen, wenn man extra doppelt klar machen will, was man meint. Wer als erstes in die schwarze Schlange reingeht, kommt als erstes auch wieder raus. Dementsprechend ist dann Lifo ein Stack last in first out.

6:09 Also ich bin mit Stack und Que vollkommen zufrieden. Ich möchte nur, dass sie diese Begriffe mal gehört haben, weil die ab und zu verwendet werden.

6:20 Okay, manchmal ist selbst das noch zu streng. Wir hätten gerne einfach nur einen Sack von Elementen, in denen wir Elemente reinpacken können und auch Elemente wieder rausnehmen können. Und z.B. will das Verfahren, das wir beschreiben, hat überhaupt keine Einschränkung daran, in welcher Reihenfolge die Elemente kommen. Dann könnte ich einen Stack nehmen oder ich könnte eine Queue nehmen, würde funktionieren, aber wenn ich das kommunizieren möchte, dass mir es wirklich egal ist, dann könnte man noch einen anderen abstrakten Datentyp dafür vorsehen. Äh, ich habe den mal Berg genannt für ja vielleicht auf Deutsch tatsächlich Sack äh auch. Na ja. Ähm, sie können sich noch andere aussuchen. In in Java gibt's tatsächlich auch diese Abstraktion als Collection, als Oberbegriff für diese ganzen äh Container Datenstrukturen. Da kann ich also beliebige Elemente reinstecken. Ähm habe ich hier nicht klar gemacht, ob mehrmals das gleiche Element reinstecken erlaubt ist oder nicht. In der Regel ist es erlaubt. Bei Stacks und bei wäre es auch erlaubt. Und Delete Annie sagt halt irgendein Element bekomme ich zurück, aber ich hab keinerlei Versprechen, welches es ist.

7:33 Äh beachten Sie, dass man in der Regel durchaus so wer die Implementierung noch sehen gleich, dass man Berg ach einfach als Stack implementieren würde, weil es diese diese zusätzliche Freiheit einem eigentlich gar nichts bringt im Sinne von schneller implementieren. Aber es ist eben die Kommunikation an wen auch immer äh wer auch immer das dann verwendet oder implementiert, was sie verwenden möchten. Wenn Sie sagen, mir ist die Reihenfolle egal, dann könnte das anderswohl ein Vorteil haben.

8:05 Der letzte ähm wo es mir auch einfach wichtig ist, dass sie den Begriff mal gesehen haben, nicht unbedingt, dass wir den P verwenden würden, ist diese Kombination aus ähm einer Queue, an der ich auf beiden Seiten ein und einfügen und entfernen kann. Normale Que hat an einer Stelle einen Eingang, an ander Stelle ein Ausgang. Ist er irgendwie unidirektional. während eine Deck Doubleended queue einfach ähm auf beiden Seiten ein und ausfügen äh einfügen und entfernen erlaubt. Ähm es gab dann irgendwann mal von Dikstra die Idee, man könnte Datenstrukturen schön als als Schienennnetze visualisieren. Ein Stack ist dann besonders einfach, weil ich dann hier so ein so ein Sack äh so ein so ein Abstellgleis habe, auf das ich reinfahren kann und dann irgendwie auch wieder raus, wodurch sich auch die Reihenfolge der Elemente umdreht, nicht auf natürlicher Weise. Das wäre dann ein Stack und dann Kenuth hat in seinem Bos sich die Mühe gemacht, das auch für eine Deck zu malen. Hier dieser mittlere Teil äh könnte man auch als Zugstrecke bauen. Ob das die Anwendung der Wahl ist, weiß ich nicht, aber können sich so vorstellen.

9:22 Ich kann auf beiden beiden Seiten das erste wäre also hier auf der linken Seite für uns normalerweise, da wir von links nach rechts schreiben. Also, ich kann auf der einen auf der linken Seite einfügen und entfernen und auf der rechten Seite einfügen und entfernen.