Video 8-4: Array-basierte Listen

0:03 Dann schauen wir uns direkt die erste Art an, wie man diese Datenstrukturen e diese abstrakten Datentypen implementieren kann. Und wir bleiben erstmal bei der einfachsten Version, die Sie auch schon kennen, nämlich Arrays. Wenn ich eine lineare Liste in einem Array darstellen will, dann bleibt mir nicht viel anderes übrig, als diese Liste in irgendein in irgendeiner Art in die Positionen in den Merates abzulegen. Also eine Option wäre, wir fangen eben mit dem kleinsten Element, dem linkesten Element an und packen das an den kleinsten Index im Array und so weiter und so fort. hat dann den etwas lästigen Offset, weil wir bei den Indizes ab null zählen und bei den mathematischen Listen ab ein. Aber abgesehen davon easy peasy. Natürlich hat ein Array, das ist sozusagen Teil der Definition von was ein Array für für mich ist, eine feste Größe, die ich im Wesentlichen ähm beim beim Anlegen von diesem Array, beim Allokieren vom Speicher kennen muss und die kann ich danach auch nicht mehr ändern.

1:09 Also, wenn ich die ähm diese Darstellung für unsere Listen wählen will, dann ist meine Vorstellung, ich äh lege im Konstruktor von dieser Klasse für unsere linearen Listen einmal ein großes Array an und dann habe ich damit zu arbeiten. Dann muss ich die Kapazität von diesem großen Array im Konstruktor einmal festlegen und das war's dann. Mehr geht nicht und weniger geht nicht. Das ist die Idee für diese ersten einfachen Listen. Ähm, die heißen hier im Code Fixed Size Array List. Ähm, hoffentlich der Name selbsterklärend. Die sind eine allgemeine lineare Liste. Kennen Sie in Java kann man angeben, dass man eine eine Klasse äh hier definiert, die dann Interfaces implementiert, die also alle Methoden, die also das Versprechen abgibt, alle Methoden, die es in diesem Interface gibt, dann auch zu implementieren. Die sind nicht alle auf der Folie, kommen ein paar noch. Deswegen hier noch äh der Vorwärtsverweis. Ähm, sie erinnern sich vielleicht nur ganz kurz zum Code, dass dieses Interface für lineare Listen zwei Typ Parameter hatte. einmal die Elemente selbst, das ist das, was wir natürlicherweise wollen und dann noch diese duselige Konvention mit den Positionen, ohne die wir das nicht allgemein kapseln konnten.

2:30 Für Arrays würden wir gerne sagen, dass es eigentlich einfach ein int. Äh um es ein bisschen ähm besser handhabbar zu machen, haben wir hier mal eine extra Klasse für diese Position. Ähm, also int würde eh nicht gehen, wenn dann integer die Rappertypen, aber hier ist es mal sozusagen äh etwas expliziter modelliert, damit wir äh das Interface bereitstellen können. Also, eine Position in diesen Fixed Size Arrays ist im wesentlichen nur ein Index, den wir uns fest speichern. Der ist auch final, das heißt, ich kann den gar nicht verändern. Und der Rest ist nur so die die üblichen ähm Stücke Code, die man in Java immer zu schreiben hat. Wenn man eigentlich sagen möchte, Position ist ein eine Werteklasse, die sich also so verhält wie ein ein statischer Wert oder ein ein konstanter Wert. Ich muss dann eben Equals und Hashcode überschreiben. Das kennen Sie, oder? Hab mir glaube ich im Java Quiz auch abgefragt. Wenn ich äh wenn ich das nicht tue, dann kann ich eben zwei Positionsobjekte instanzieren, die einen den gleichen Index haben und die Java aber nicht als gleich ansehen würde, weil die Standardimplementierung von Equals eben nur Identität von Objekten als gleich zulässt. Und hier sagen wir, ich erlaube alle Objekte, die sind gleich, wenn sie den gleichen Index repräsentieren.

3:59 Und dann wissen Sie auch, wann immer sie Equals überschreiben, müssen sie auch Hashcode überschreiben, sonst ist eventuell die ähm die Semantik da kaputt. Abgesehen davon passiert hier sonst nicht viel spannendes in dieser in dieser Positionsklasse. Der Kern von der von diesem Fixed Size Arraylist besteht aus einem Array. Elements äh hier als Typ in den Method in den Klassen intern haben wir immer Objects, die also nicht auf El spezifisch sind und wir werden dann immer, wenn wir zugreifen, dann cast machen müssen. Sehen Sie auf der nächsten Folie. Und wichtig hier eben beim Anlegen von so einem Fixed Size Array muss ich die Kapazität einmal festlegen. Fixed Size.

4:46 Okay. Äh vielleicht sollte ich noch erwähnen, dass es hier auch eine Definition von Größe gibt. Also Size und Capacity ist nicht das gleiche. Kapazität ist wie viel Platz habe ich in meinem Array, um Elemente abzulegen. Und Size ist, wie viele habe ich wirklich da drin? Denn unsere linearen Listen können ja wachsen und schrumpfen und ich möchte wissen, wie viele Elemente sind da wirklich drin? Also an der Stelle ähm auch wenn wir Arrays unter der Haube verwenden, ist es anders als ein Array, der ja immer eine feste Länge hat.

5:23 Okay, hatte ich schon drüber gesprochen. Ähm, die Operationen von der linearen Liste sind großteils ganz günstig zu erledigen in einem Array. Da es aber unsere erste Implementierung ist, möchte ich die einmal kurz durchgehen. Wir hatten diese zwei Methoden, die uns einen eine Position angeben, die das erste und letzte oder eins hinter dem letzten Element repräsentiert. Also Start soll hier dieses erste Element angeben, das entspricht dem Index 0. Deswegen gebe ich hier eine Position für Index 0 zurück.

6:00 wiederum soll eine Position hinter dem letzten echten Element liegen. Das ist also der Index Size. Deswegen ist es ist das hier die Implementierung. Wenn ich eine Position habe und möchte von der eins größer und eins kleiner werden, dann könnte man jetzt hier einfach eins auf diese Position aufadieren. Ähm, das erlaubt diese Klasse aber nicht so ohne weiteres. Da die hier ähm public ist, könnte man das auch von außen tun. Aber da wir das Interface implementieren, ähm habe ich hier auch diese Implementierung, die dann noch prüfen, ob es diese nächste oder vorherige Position überhaupt gibt. Get set sind ganz einfach. Ich greif mal auf das Array zu. Ähm, an dieser Stelle fehlt offensichtlich der Cast. Habe ich ähm den an der Stelle entfernt?

6:56 Also hier habe ich ein ein Elms Typ, das ist ein Object Array. Also hier müssten Sie auf Elem den Cast einbauen und äh das wiederum würde der Compiler erstmal anmeckern, dass sie da auf einen Teil auf einen Untertyp den Cast machen, wo wir nicht statisch wissen, ob das äh oder wo der Compiler nicht statisch beweisen kann, dass der Cast immer gültig ist. Wir können statisch beweisen als Mensch, dass der immer gültig ist, denn die Elemente in unserem Array sind gekapselt und wir erlauben nur den den Zugriff über die Methoden. Das heißt, aber hier diese Methode würde auch so ein Suppress warnings Das kommt noch x mal auf den nächsten Folien vor. Ähm, tut mir leid, dass es hier fehlt.

8:01 Also, der Kompromiss, um mit den Java Generics auszukommen, ist an dieser einen Stelle diesen Cast zu machen und die Warnung zu unterdrücken und an allen anderen Stellen braucht man es dann nicht. Abgesehen davon ist Zugriff auf den Array einfach nur einmal gekapselt, passiert sonst nichts. Was ist mit den anderen Methoden von Linked List? Wir haben ja noch Insert und Delete. Die Operation hier oben. Okay, sind ja mittlerweile ähm Experten im Analysieren von Codes. Die machen alle nicht viel, die haben alle konstante Laufzeit. Für Insertalle Delete ist es nicht unbedingt der Fall. Darum hatten wir überhaupt mit diesen ganzen linearen Listen angefangen. Also, wenn Sie so mögen, ist diese Fixed Size Array List ähm nur so eine eine erste Implementierung als was geht denn ohne groß nachzudenken, aber die ist nicht so befriedigend, denn sowohl für Insert als auch für Delete muss ich Platz schaffen. Bei Insert an der bestimmten Position muss ich alle Elemente, die an der Position und eins äh und weiter hinten stehen, muss ich eine Position nach hinten versetzen.

9:16 Ich hier einfügen möchte mein neues Element X und sagen wir mal hier die Kapazität ist vielleicht nicht alles, aber all diese Elemente, also der Teil ist leer, aber diese Elemente sind belegt. Dann muss ich die alle um einen Position nach rechts verschieben in der Hoffnung, dass dafür auch genügend Platz ist. Das wiederum prüft diese erste Abfrage. Wenn ich ein Element einfügen will und ich habe schon mein ganzes Array benutzt, dann kann ich das nicht und dann werfe ich hier eine Exception. Ähm ist natürlich im allgemeinen nicht die befriedigende Lösung. Kommen wir noch drauf zurück. Aber abgesehen davon, selbst wenn ich Platz habe, muss ich eventuell eine ganze Menge Elemente kopieren, bevor ich mein neues Element dort unterbringen kann. Und bei Delete passiert das gleiche umgekehrt. Delete ist natürlich immer irgendwie die Umkehrung von Insert. Äh, das gilt ganz allgemein. Das heißt, ich ähm würde das Element hier entfernen und dann die Elemente eine Position nach links kopieren. Das Entfernen, da das Element E überschrieben wird, passiert nicht wirklich was.

10:28 Ähm, was wir hier tun, ist aber bei dem, vielleicht sollte ich präziser sagen, hier kopieren wir die Elemente eine Position nach links. Das heißt, jedes Element, außer das allerletzte wird überschrieben von seinem ehemals rechten Nachbarn. Das letzte, die ehemals letzte Position, aber nicht, da steht hinterher ja kein Element mehr. Wir haben eins weniger insgesamt. Warum habe ich hier diesen diesen Zugriff, dass ich das Element explizit auf auf Null setze? Für die Bedeutung der Datenstruktur brauchen wir das nicht. Also auch hier noch mal das Bildchen. Ich habe eine Position, die ich jetzt löschen möchte. Das ist das P und sag wir hier ist leer. Dann ist hinterher jetzt der vordere Teil gleich und die Elemente habe ich um eins nach links kopiert. Aber warum schreibe ich an diese Stelle jetzt null?

11:26 Noch mal für die Bedeutung der Datenst bräuchte man das nicht. Es gibt aber einen Effekt, der den man unter Leutering äh kennt. Wenn ich ein in dieser Datenstruktur noch eine Referenz auf ein Objekt habe, dann kann dieses Objekt nicht garbage collected werden, selbst wenn sonst niemand eine Referenz mehr auf das Objekt hat. In diesem Fall ist es ein bisschen übervorsichtig, weil wir auf das letzte Element ja trotzdem noch eine Referenz haben, nämlich hier jetzt eine Position weiter links. Der Punkt ist, ich kann ja noch mehr Löschungen machen und dann irgendwann vielleicht auch dieses letzte Element löschen, aber vielleicht diese Position hier hinten nie mehr überschreiben. Und dann kann es mir passieren, dass ich als einzige Referenz auf ein vielleicht großes Objekt, was viel Arbeitsspeicher beansprucht, diese diese Pseudoorferenz hab, die eigentlich gar nicht mehr gültig ist. Die haben wir nur nicht aufgeräumt. Das ist der Effekt von Leutering. Also, indem wir noch einen Pointer auf den Objekt halten. Referenz.

12:50 Aber der Garbage Collector in Java kann halt nicht wissen, welche Referenzen für uns jetzt Bedeutung haben oder nicht. Das müssten wir ihm schon sagen. Das können wir nicht, da gibt's keinen Mechanismus für. Deswegen auf Null setzen wird an ganz vielen Stellen immer so aufkommen. Ich diskutiere es nicht jedes Mal noch mal im Detail. ist so ein so ein Klassiker ähm der dann den Unterschied macht zwischen ist formal korrekt und reicht für eine Algorithmen und Datenstrukturenimplementierung und äh wie möchte man das in der Praxis machen, wenn man den Code dann länger laufen hat und verwendet? Okay. Äh steht schon lange auf den Folien, haben Sie sicher schon drüber Gedanken gemacht. Der Worst Case tritt natürlich ein, wenn ich weit vorne in der Liste einfüge oder lösche, dann habe ich die ganzen Elemente rechts davon zu verschieben. Das ist also teuer und im Allgemeinen dann äh, wenn ich das viel machen muss, nicht zu gebrauchen.

13:54 Ähm ja, zweiter Punkt ist natürlich auch formal von der Funktionalität. Unsere linearen Listen sollen beliebig groß werden können. Ähm das ist natürlich eh immer eine Lüge in der Praxis, denn keine Maschine ist ja unendlich groß. Die Idee ist aber, dass zumindest die Spezifikation von unserem Algorithmus, wenn die Programmiersprache es erlaubt, beliebig große Eingaben erlaubt, soferne eben die Maschine ähm mitwächst oder wann immer sie mehr Platz brauchen, dann schaffen sie irgendwie noch welchen im Cloud Speicher oder sonst wo. Das ist ja gar nicht so unrealistisch heutzutage, aber wir möchten eben keine hard gecodet Limits einbauen, die dann schon von vorne rein festlegen, die größer geht nicht. Das scheint aber ganz und gar unverträglich mit der Idee eine Rate zu verwenden. Das heißt, da werden wir uns was anderes überlegen. Ähm, es gibt aber einen Einsatzzweck, wo zumindest diese Laufzeit kein Thema ist, nämlich für Stacks. Wenn ich eh nur einen Stapel brauche, dann kann ich so einrichten, dass das obere Ende von meinem Stack quasi die das Ende der Liste bei den hohen Indizs ist. Dann passieren alle Einfügungen und Löschungen nur da, wo es nichts weiter rechts zu verschieben gibt. Und dann kann ich diese Insert und ähm Delete Operation effizient nutzen.

15:13 Ähm konzeptionell im Vergleich zu der Liste von vorhin drehen wir das um, so dass die Elemente ähm mit Home Index jetzt weiter oben sind. So kann es natürlich keiner lesen, aber so rum. Ähm ist nur visuell umgedreht. Die Elemente sind immer noch in der gleichen Position. Ich habe nur das Array andersrum gemalt.

15:36 Vom restlichen Code ist auch fast nichts verändert. Hier habe ich nicht vergessen den ähm Cast und die äh Unterdrückung der der Warnung einzubauen. Abgesehen davon ist das im Wesentlichen der alte Code ähm bereinigt um die Stellen, wo wir wissen, dass die Kopierschleifen eh nicht laufen würden. Also Push. Ich weiß, das nächste Element geht hier in die nächste freie Stelle. Dann schreibe ich es da einfach hin und ich muss mir nur noch merken, dass die Größe von der Datenstruktur um eins gestiegen ist. umgekehrt pop. Da muss ich, weil ich das Element zurückgeben möchte, das zuerst auslesen und ähm dann mache ich einfach dieses runterkopieren, aber das ist ja nur ähm die leere die leere Liste. Was also übrig bleibt, ist das Setzen von null, damit ich nicht diese Referenzen übrig habe. Und dann kann ich das Ergebnis zurückgeben. Also, wenn Sie dann ein bisschen hier die Leerzeahlen rausstreichen und das äh kompakter schreiben, dann haben Sie so eine Handvoll von Codezeilen, die wirklich was tun. Und dann haben wir einen Stack, der ähm alle Operationen in Konstantzeit erledigt.

16:59 könnte man vielleicht irgendwo ähm mal noch notieren. Man kann auch dazu sagen, jenseits von diesem groß O, das ist wahrscheinlich die schnellste Implementierung von dem Stack überhaupt, denn dieser Code hier ist unfassbar kompakt. Alles was ich mache ist ein Schreibzugriff und eine Variable erhöhen. Günstiger kriege ich es quasi nicht hin. Aber der große Nachteil ist natürlich immer noch ähm Ach ja, hier fehlt aber definitiv noch ein eine Überprüfung, ne? Ähm, wenn ich schon an der Größe bin, dann würde das hier eine Exception werfen. Kann ich natürlich auch sagen, okay, dann dann lasse ich die einfach durchfliegen. Schöner wäre hier vielleicht eine schöner benannte Exception zu nehmen.

18:03 Wir hatten wir die out of capacity capacity exceeded. Okay, ist natürlich nur ein Name. Also im Prinzip eine perfekte Implementierung, auch super schnell in der Praxis, aber ich habe immer noch diese eigentlich nicht erlaubte Oberschranke für die Größe. Wenn ich mit der nicht zurecht komme, dann ist es kein gültiger Stack.

18:41 Stacks haben also ganz gut funktioniert, abgesehen davon diesem Problem, dass wir mit Erasia nie loswerden. Wie sieht's denn mit Qs aus? Da könnte ich ja das gleiche versuchen. Die sind ja auch sehr eingeschränkt. Das füge ich auch nie in der Mitte ein oder Lösche aus der Mitte raus, sondern immer schön eines eine Ende ein Ende einfügen, ein Ende löschen. Also ich könnte z.B. will das genauso hier anlegen, das Einfügen nach oben günstig ist und löschen von unten funktioniert auch. Das heißt, ich kann auch eine Queue bauen in dem Array. Äh, das einzige Problem dabei ist nach so ein paar Operationen ist wie so eine Raupe hier dieser belegte Bereich immer weiter nach oben gewandert, weil ich immer oben einfüge und unten rausstreiche. Das heißt, irgendwann haut die oben an das Ende vom Array an, obwohl wir vielleicht nur eine Handvoll Elemente verwenden. Also, es ist nicht wie hier, dass die Größe, die Anzahl Elemente an der Kapazitätsgrenze anstößt, sondern einfach nur nach einer Handvoll nach n äh Operation in Q dq bin ich nach oben gewandert und habe keinen Platz mehr, um weiter nach oben zu wandern, obwohl der Rest vom Array leer ist.

19:49 Das ist doof, aber da gibt's auch eine schöne Lösung dafür. Ich verwende mein Array als Kreis, als Ringpuffer, dann kann ich mir ähm immer so viele Elemente erlauben, wie in diesen in dieses Array reinpassen. Ich muss nur ein bisschen flexibler werden in was das denn heißt, dass ich ein zusammenhängendes Stück in meinem Array für diese Queue verwende. Äh und dadurch ähm möchten wir das Bild eigentlich so malen, dass das dieses Array kreisförmig geschlossen ist. Das ist natürlich nur für unsere für unsere ähm unsere Überlegung. In Wirklichkeit habe ich hier einen Sprung von den Indizs. Komme ich nicht drum rum. Äh es gibt aber diese bequeme Modelo Operation, die genau diesen Sprung effektiv wieder rausrechnet. Wenn ich einen Index habe in dieser in dieser Darstellung, der ein paar mal im Kreis gelaufen ist, der also höher größer als C ist, dann kann ich einfach Modulo C rechnen und dann habe ich die Position an dem Kreis, wenn ich im Kreislaufen mir vorgestellt hätte. Okay, sehen Sie gleich. Ähm ist an der Stelle einfach eine sehr bequeme Operation, die diese Berechnung kompakt ähm kapselt.

21:14 Äh, was brauche ich sonst noch? Im Stack hatte ich nur die Größe gespeichert, da sich hier diese belegte Teil wie so eine so eine Raupe ähm durch das Array durchschlängelt. Ich muss immer an Snake denken. Das ist eigentlich auch so, ne? Ich habe vorne wachs ich indem die Schlange eben läuft und hinten schrumpft sie wieder, weil ich ja vorne weitergelaufen bin und ab und zu wächst sie mehr, sie schrumpft und so weiter. Kennen Sie? Ist natürlich auf einem Kreis nicht ganz so spannend. Das heißt, ich brauche hier diese beiden äh Positionen, front und rear. Ähm wobei Rear hier hinten sozusagen, da werden die Einfügungen gemacht und bei Front wird gelöscht. Ist jetzt unsere Konvention. Ja, äh passt natürlich zu einer Warteschlange, wenn Sie sich so vorstellen. Also merke ich mir diese zwei Variablen und die Kapazität und damit äh ist im Wesentlichen alles gesagt. Ich habe natürlich dann auch diesen Fall, dass quasi diese ähm Rear weiter hier oben ist als Front, sodass ich nicht unbedingt sagen kann, welches von den beiden größer ist. Ich muss das immer Modulo C betrachten. Also, ich könnte hier diesen Fall haben. Kommt gleich noch an ein an Bild zu.

22:29 Hier ist eigentlich meine Nullinie oder na ja, die Zelle danach. Jetzt könnte ich hier mein mein Rear haben, hier mein Front. Das heißt, dieser dieser Teil da ist der belegte und er hat jetzt natürlich einen Sprung bei der Null. Macht aber nichts. Wenn ich alle Indizs modulo C nehme, dann habe ich hier von C - 1 auf C, wenn ich einfach ein drauf zähle, Modulo C ist wieder 0. Das heißt, ich kann bei front anfangen immer + 1 + 1 + 1 + 1 + 1 + 1, bis ich bei Rear angekommen bin, soferne ich immer Modulo C noch recht.

23:14 Das ist die Idee von dem Ringpuffer. Und an der Stelle wird's glaube ich Zeit, sie noch mal aufzuwecken. Wenn ich das so mache, wie ich das hier beschrieben habe, ich gehe gleich auch auf die Folie noch mal zurück.

23:33 Ähm, können Sie einfach als als Text die Bedingung reinschreiben, wenn ich wenn ich gar kein Element in der Q habe, was sollte für Front und Rear gelten?

24:47 Also natürlich ist ähm ich hoffe, die Zeichnung ist eindeutig genug. Front ist sozusagen die Position, an der wir das nächste Mal, wenn wir d aufrufen würden, dieses Element entfernen. Und Rear ist das letzte, was noch zu der Warteschlange gehört. Also ich müsste bei Rear + 1 das nächste Element einfügen. Das ist natürlich nur eine Konvention, könnte man auch anders machen, aber wir nehmen mal jetzt diese.

25:44 hoffe mal, sie haben das Bild sich langsam eingeprägt. Sind mir noch ein paar wenige Antworten. Wenn Sie gar keine Ahnung haben, dann schreiben Sie keine Ahnung, damit wir weitermachen.

26:06 Das ist so die Art von Fragen, wo dann in der Regel irgendwann klar ähm beobachtet wird, dass man auch Emoji schicken kann. Aber sie sind ja alle ähm viel viel reifer und erwachsener.

26:23 Jetzt habe ich auch provoziert. Ähm ist auch nichts Unerwachsenes an MoJ oder? Äh, okay. Ähm, ich würde mal ein paar Antworten zeigen. Das ist leider wie immer etwas ähm schwierig, einen Überblick zu bieten.

26:53 Ja, okay. Also das äh ja, ich wä selber schuld. Also hier gibt's so ein paar Antworten, die zumindest die [gelächter] Variablen aus der Frage aufgreifen. Ich denke, der Konsens ist sie sind gleich oder es gibt auch hier die Variante Front is rear -1.

27:14 Also, ich meine ist ja leicht nachzuprüfen, wenn man so möchte. Wenn ich hier in diesem Bild Front und Rear auf die gleiche Position setze, versuch's mal zu malen.

27:31 War mal das doppelt ist gleich, damit es keine Zuweisung sein kann. Äh nach der Definition, wie ich eben sagte, muss ja Front das Element sein, dass ich als nächstes ausgebe, wenn es denn eins gibt und Rear ist das letzte, das noch drin ist. Das heißt, in dem Fall, wenn die gleich sind, habe ich dieses Element noch in der Liste.

27:52 Also, ich habe den Bereich von Front bis Rear, beide Endpunkte inklusive mit Elementen gefüllt. Wenn ich also den leeren Bereich angeben will, dann muss es tatsächlich äh noch eins hinten dran.

28:14 habe also hier meine meine Grenze. Äh front wäre das nächste Element, dass ich ausgeben will, also noch mal zusammen ähm noch mal formal aufgeschrieben, was was wir äh was ich in Worten gesagt hatte. Das ET Element in unserer Q speichern wir an einer bestimmten Position in unserem Array, nämlich Front + I -1, weil wir bei 0 anfangen, ne? Front ist ja schon mit dabei und dann eben Modulo C. Aber natürlich ähm geht I geht das nur bis ähm bis wir Rear erreicht haben.

29:09 Was vollkommen okay ist, ist, wenn das sozusagen überläuft über diesen Bereich null. Das macht das Modulo für uns. Die leere Queue muss ich so darstellen. Front ist ein Element vor re. Aber jetzt könnte man ein Problem sehen, wenn man weilchen drüber nachdenkt. Die gleiche Positionierung von Front und Rear würde nach meiner Beschreibung vorhin auch bedeuten, von Front bis inklusive Rear ist alles gefüllt.

29:40 Das ist natürlich ein Problem. Jetzt habe ich den gleichen internen Zustand mit zwei Bedeutungen überbelegt. Das geht nicht. Aber die Lösung ist ganz einfach. Wir verbieten diesen rechten Teil. Das heißt, die erlaubte Anzahl Elemente ist einfach eins kleiner als die Größe von unserem Array und gut ist. Mehr mehr passiert nicht. Das heißt, wir können einfach diesen Fall nicht zulassen. Wir müssen aufhören, wenn wir fast voll sind. Ein Element muss sozusagen hier Puffer bleiben. Eine Alternative wäre, wir speichern uns explizit die Größe, die Anzahlelemente. Das ginge genauso, kostet aber auch einen extra Speicherplatz, das ist quasi äh gehüpft wie gesprungen. Ähm hier in der Implementierung ist das ist es so gewählt, dass die Kapazität nicht ganz erreicht werden darf. Äh, der volle Code ist hier ausformuliert. Den würde ich gar nicht so im Detail besprechen wollen. Der ist sehr ähnlich zu den Array Stacks, außer dass überall noch so ein Modulo dran gehauen ist. Also, ich habe ein ein Array für die ganzen Objekte, meine Variablen Front und rear. Weil wir die Kapazität so oft brauchen, habe ich dafür eine lokale Variable, Instanzvariable definiert. Die könnte ich aber auch überall ersetzen durch Q. Length. Ja, äh das ist ähm was wir hier verwenden. Äh Qart length + 1 ähm nee, Q length. Vergessen Sie es. Wir ich habe hier das dadurch, dass wir ein Element weniger speichern können, als das Array lang ist, einfach das Array 1 länger gemacht als vom Benutzer sozusagen angefragt. äh mit der Bedeutung, dass Capacity sagt, ich hätte gerne eine eine Que, die so und so viel Elemente umfassen kann. Dann speicher, belege ich so viel Speicher, wie ich dafür brauche.

31:31 In Q muss an die Position rear + 1 schreiben. Das heißt, ich erhöhe Rear um 1. Ich muss dann aber die Modulo Rechnung machen, falls ich übergelaufen bin. Und dann schreibe ich das Element dahin. Für DQ äh mache ich das im Wesentlichen äh rückgängig. Höhe front um eins und muss da auch wieder Modulo rechnen und das Element in Front auslesen ist letztlich einfach. Da ist wieder die Hälfte davon. Java spezifischer Generics äh Spaß. Ähm immer das gleiche, wenn ich habe mich bemüht, das in den Folien drin zu lassen, außer die erste mal, wo ich es vergessen habe, damit der Code sozusagen realistisch ist. Aber das ist äh Boiler Plate.

32:17 Äh hier gibt's diese zwei extra Checks, nur damit man das nicht jedes Mal neu durchdenken muss. Wann ist die Queue leer und wann ist sie voll? Ähm hatten wir aber jetzt an den Beispielen diskutiert. Beachten Sie auch hier, alle Operationen sind wieder Konstantzeit. die sind vielleicht ein Müh langsamer, weil ich diese Modulo Rechnung machen muss, aber das ist immer noch um und bei vielleicht die schnellste Möglichkeit Qs zu implementieren. Wenn ich aber eben damit leben kann, dass die Kapazität beschränkt ist. Es gibt Anwendungen, wo das gar nicht so schlimm ist, wo wir ignorieren, wenn die Queue voll läuft, wir überschreiben einfach die Elemente, dann wird das ein andere Abstrakt, ein anderer abstrakter Datentyp, dann ist es sozusagen ein Puffer der letzten so und so viel Elemente, die in cued wurden. Das kann man gut bei Realtime Daten gebrauchen. Da will ich vielleicht ein bisschen zurückschauen können oder ein bisschen Puffer haben, aber der Stream läuft eh weiter. Ich äh kann also, wenn ich zwischendrin was verloren habe, kann ich das eh nicht beliebig aus ähm äh nicht beliebig auffedern. Also, das Szenario wäre ein Livestream, der läuft, die Netzwerkverbindung ist mal schnell genug und manchmal hat sie Versatz. Dann habe ich lokal im Client einen Ringpuffer, der sozusagen bisschen vorhält Daten, s dass ich kurzen Versatz ausgleichen kann. Ich spiele also das mit kleinem Versatz ab. Dafür kann ich auspuffern, wenn zwischendrin die Übertragungsgeschwindigkeit nicht ganz gleich ist, aber ich würde dann immer die da alten Daten überschreiben, die brauche ich eh nicht mehr. Das ist so die Idee. Das in diesem Kontext äh wird es noch viel häufiger verwendet als für reine QS.

33:57 Bisher das Fazit, wir kriegen zwar schnelle Operationen, wenn wir nur den Rand verändern, aber das Einfügen in der Mitte ist ist ganz ganz ineffizient. Und es ist auch keine allgemeine Lösung, weil wir nicht mit dieser Obergrenze leben wollen.