Java Gleitende Mittlere Warteschlange

Implementieren einer Fixed-FIFO-Warteschlange in Java Bei der Arbeit mit Zeitreihendaten müssen oft Summen aufeinanderfolgender Zahlen für einen vorgegebenen Zeitrahmen berechnet werden. Stellen Sie sich zum Beispiel die Berechnung eines gleitenden Durchschnitts mit einer festen Größe vor. Let39s Blick auf eine sehr einfache Zeitreihen. Angenommen, ein gleitender Durchschnitt der Länge 4 ergibt das folgende Array: Die Formel für einen gleitenden Durchschnitt der Länge 4 ist also: MA t (Summe aller Elemente von t-3 bis t) / 4 Wie würden wir dies effizient in Java-Code implementieren? Das Problem ist, dass wir die Summe in der Formel für jeden gleitenden Durchschnitt berechnen müssen. Natürlich ist es möglich, immer über alle Zahlen im aktuellen Zeitrahmen zu wiederholen, dies zu tun, aber dies ist unnötig langsam. Stattdessen können wir einfach das letzte Element im Zeitrahmen subtrahieren und das neueste zu Summe hinzufügen. Auf diese Weise können wir eine erhebliche Anzahl unnötiger Berechnungen sparen. Dennoch müssen wir den Überblick behalten, was eigentlich die alten und die neuen Elemente sind. Wir müssen diese Zahlen irgendwo speichern. Eine geeignete Datenstruktur wäre eine First-in-First-Out (FIFO) - Warteschlange von Zahlen. Aber wie genau kann eine FIFO-Warteschlange in einer (nicht funktionalen) Programmiersprache wie Java implementiert werden? Die erste Idee ist, typischerweise eine arraybasierte Implementierung zu verwenden und die Position von Elementen in dem Array zu verschieben, indem wiederholt leicht verschobene Kopien von erzeugt werden Das Array. Im obigen Beispiel müssten wir ein neues Array fünfmal erstellen, einmal für jede neue Summe, die berechnet wird. Dies ist natürlich sehr ineffizient, da die Erzeugung eines Arrays im Speicher relativ langsam ist. Implementierungen, die auf Klassen wie java. util. ArrayList oder java. util. Vector basieren, sind bereits viel besser, weil sie sich intern auf längere Arrays und Indizes verlassen. Dennoch ist dies nicht die beste Lösung, denn sobald sich die internen Indizes außerhalb der internen array39s Grenzen bewegen, muss eine neue Kopie des internen Arrays erstellt werden. Eine typische Alternative zur Implementierung von FIFO-Warteschlangen besteht somit darin, eine verkettete Liste zu verwenden: Der Vorteil liegt auf der Hand, nicht mehr kopieren oder neu erstellende Arrays im Speicher. Wir müssen nur ein paar Zeiger manipulieren. Natürlich verlieren wir den Vorteil, ein Element in der Warteschlange nach einem Index direkt zu bewerten, aber für unseren Zweck - Berechnung der gleitenden Mittelwerte - das wollen wir sowieso nicht. Gestern ist mir plötzlich aufgefallen, dass es tatsächlich eine noch bessere Alternative gibt, wenn die Länge der Warteschlange festgelegt ist (wie in unserem Beispiel). Wir können effektiv einen Ring verwenden. Das Hinzufügen einer neuen Nummer in die Warteschlange und das Löschen der ältesten ist das gleiche wie das einfache Ersetzen des ältesten Elements in diesem Ring durch ein neues. Intern können wir wiederum ein Array fester Länge in Kombination mit einem Rotationsindex verwenden. So sieht der Code in Java aus. Zuerst erstellen wir eine eigene Queue-Schnittstelle: Diese Schnittstelle weicht etwas von derjenigen ab, die in den Java-Bibliotheken zur Verfügung gestellt wird, aber das ist unwichtig fürs Erste. Als nächstes, die Umsetzung unserer Warteschlange: Die Warteschlange quotrollsquot durch den Ring. Durch das Hinzufügen eines neuen Elements am Anfang der Warteschlange wird automatisch das älteste Element in der Warteschlange entfernt - kein Kopieren von Arrays oder das Zurücksetzen von Objektreferenzen erforderlich. Anders als mit verketteten Listen können wir auf jedes Element im Ring direkt mit der Methode get zugreifen. Schließlich können wir eine Unterklasse unseres Warteschlangenobjekts erstellen, die gnädig überrollen wird, wenn neue Werte in die Warteschlange / den Ring eingefügt werden. Wir können die Klasse jetzt benutzen. Die Länge des gleitenden Mittels wird anfänglich über die Länge des Arrays festgelegt, die an seinen Konstruktor gegeben wird. Ich muss den Überblick über die letzten 7 Tage Arbeitsstunden in einer flachen Datei lesen Schleife. Seine verwendet werden, um die Ermüdbarkeit von Arbeitsplänen zu messen. Im Moment habe ich etwas, das funktioniert, aber es scheint ziemlich ausführlich und Im nicht sicher, ob theres ein Muster, das mehr prägnant ist. Derzeit habe ich eine Java-Klasse mit einem statischen Array, um die letzten x-Tage-Daten halten, dann, wie ich durch die Datei zu lesen, hacke ich das erste Element und verschieben die anderen 6 (für eine Woche rollen insgesamt) zurück um eins. Die Verarbeitung dieses statischen Arrays erfolgt in seinem eigenen Verfahren, dh. Meine Frage: ist dies eine vernünftige Design-Ansatz, oder gibt es etwas blendend offensichtlich und einfach, diese Aufgabe zu tun Danke Jungs gefragt Aug 30 11 at 14:33 Vielen Dank Jungs: I39ve bekam die Nachricht: verwenden Sie ein übergeordnetes Objekt und nutzen Sie die Relevante Methoden oder einen Ringpuffer. Große Antworten, alle von ihnen. Wenn Sie darüber nachdenken, benötigen Sie immer Zugriff auf das gesamte Array, so können Sie loswerden, dass erste Eintrag - die ich war nicht sicher, auf eigene Faust. I39m erleichtert, dass ich hadn39t verpasste einige 1 Liner und war im Grunde auf eine vernünftige, wenn nicht effizient und knapp Track Dies ist, was ich liebe über diese Website: qualitativ hochwertige, relevante Antworten von Menschen, die ihre sht kennen. Ndash Pete855217 Aug 11, 2010, um 15:05 Uhr Warum initialisieren Sie runningTotal auf null Was ist der Typ, wo es deklariert Es wäre gut, wenn Sie einige Code-Beispiele, die tatsächlichen Java-Code ähneln setzen. Im Übrigen wäre meine Kritik die folgende: Ihre Funktion hat zu viel. Eine Funktion oder Methode sollte zusammenhängend sein. Entsprechend sollten sie eine Sache und eins nur tun. Schlimmer noch, was passiert in Ihrer for-Schleife, wenn x 5 Sie kopieren runningTotal6 in runningTotal5. Aber dann haben Sie zwei Kopien des gleichen Wertes an Position 5 und 6. In Ihrem Entwurf, Ihre Funktion bewegt / shuffles die Einzelteile in Ihrem Array berechnet die Gesamtabzüge Stuff zu Standardfehler liefert die Summe Es tut zu viel. Mein erster Vorschlag ist nicht zu bewegen Zeug um in der Array. Stattdessen implementieren Sie einen kreisförmigen Puffer und verwenden Sie es statt des Arrays. Es vereinfacht Ihren Entwurf. Mein zweiter Vorschlag ist, Dinge in Funktionen zusammenzufassen, die zusammenhängen: haben Sie eine Datenstruktur (ein zirkularer Puffer), der Ihnen erlaubt, sie hinzuzufügen (und dass der älteste Eintrag sinkt, wenn er seine Kapazität erreicht hat) Interator haben eine Funktion, die die Summe auf dem Iterator berechnet (Sie dont care, wenn Sie die Summe aus einem Array, Liste oder kreisförmigen bufer.) Dont nennen es insgesamt. Nennen Sie es Summe, die ist, was Sie berechnen. Das ist, was Id tun :) That39s große info luis, aber denken Sie daran, diese Funktion ist ein kleiner Teil der Funktionalität der Klasse, und es wäre Overkill zu viel Code hinzufügen, um es perfekt. Sie sind technisch korrekt, und ich verstehe, dass mein Code zu viel 39 macht, aber gleichzeitig ist es manchmal besser, auf der Seite des kleineren, klareren Codes zu irren als für Perfektion zu gehen. Angesichts meiner Java-Fähigkeiten, auch die Herstellung der Pseudocode Sie beschreiben kompilieren würde ich blasen mein Budget auf diese (), aber danke für die klare Beschreibung. Ndash Pete855217 Aug 31 11 at 2:23 Hmmm, es geht nicht um Perfektion, sondern um etablierte industrielle Praktiken, die wir für die letzten 3 Jahrzehnte kennen. Sauberer Code ist immer einer, der partitioniert ist. Wir haben jahrzehntelange Evidenz, die zeigen, dass dies der Weg ist, um in den allgemeinen Fall zu gehen (in Bezug auf Kosteneffizienz, Defektverkleinerung, Verständnis usw.). Es sei denn, es ist Wegwerf-Code für eine einmalige Art der Sache. Es ist niemals teuer, dies zu tun, wenn man auf diese Weise eine Problemanalyse startet. Codierung 101, brechen das Problem und der Code folgt, weder Overkill noch schwierig) ndash luis. espinal Ihre Aufgabe ist zu einfach und die Vorgehensweise Sie angenommen haben, ist sicherlich gut für den Job. Allerdings, wenn Sie ein besseres Design verwenden möchten, müssen Sie loszuwerden, dass alle die Anzahl der Bewegung Sie besser eine FIFO-Warteschlange und machen gute Verwendung von Push-und Pop-Methoden, die Art und Weise der Code reflektiert keine Datenbewegung, nur die beiden logischen Aktionen Von neuen Daten und entfernen Sie Daten, die älter als 7 Tage sind. Beantwortet Aug 30 11 um 14: 49Stacks und Warteschlangen Einleitung Beide Stacks und Warteschlangen sind wie Listen (geordnete Sammlungen von Elementen), aber mit mehr eingeschränkten Operationen. Sie können beide implementiert werden entweder mit einem Array oder mit einer verketteten Liste, um die tatsächlichen Elemente zu halten. Stacks Das Konzeptbild eines Stack ADT ist so: Denken Sie an einen Stapel von Zeitungen oder Tabletts in einer Cafeteria. Das einzige Element, das herausgenommen (oder sogar gesehen werden kann) ist das zuletzt hinzugefügte (oder obere) Element. Ein Stapel ist ein LIFO-abstrakter Datentyp. Hier sind die Stack-ADT-Operationen: return true, wenn der Stack leer ist add ob an den Anfang des Stack entfernen und zurückgeben das Element aus dem oberen Rand des Stacks (Fehler, wenn der Stack leer ist) zurückgeben das Element, das an der Spitze ist der Stapel. Aber entfernen Sie es nicht (Fehler, wenn der Stapel leer ist) In Java erstellen wir die StackADT-Schnittstelle als: Warteschlangen Das konzeptionelle Bild einer Warteschlange ADT ist so etwas wie dies: Denken Sie an Menschen in der Schlange stehen. Eine Warteschlange ist ein First-In-First-Out (FIFO) abstrakter Datentyp. Elemente können nur an der Rückseite der Warteschlange hinzugefügt werden und das einzige Element, das entfernt werden kann, ist das an der Vorderseite der Warteschlange. Hier sind die Warteschlange-ADT-Operationen: return true iff die Warteschlange ist leer void enqueue (E ob) Hinzufügen ob auf der Rückseite der Warteschlange entfernen und das Element von der Vorderseite der Warteschlange zurückgeben (Fehler, wenn die Warteschlange leer ist) In Java wir Erstellen Sie die QueueADT-Schnittstelle wie: Implementieren von Stacks Die Stack-ADT ist sehr ähnlich der Liste ADT daher sind ihre Implementierungen auch ziemlich ähnlich. Array Implementation Unten ist die Definition der ArrayStack-Klasse, mit einem Array, um die Elemente in der Stack-Note zu speichern, dass wir eine statische finale Variable INITSIZE enthalten. Die vom ArrayStack-Konstruktor als Anfangsgröße des Arrays verwendet werden (das gleiche gilt für die ArrayList-Klasse). TEST YOURSELF 1 Schreiben Sie den ArrayStack-Konstruktor. Die Push-Methode ist wie die Version der List add-Methode, die ein Objekt am Ende der Liste hinzufügt (weil Elemente immer auf die Spitze des Stacks gedrückt werden). Beachten Sie, dass es an uns liegt, wie die Designer der ArrayStack-Klasse entscheiden, welches Ende des Arrays dem oberen Ende des Stacks entspricht. Wir könnten immer wählen, Elemente am Anfang des Arrays hinzuzufügen oder immer Elemente am Ende des Arrays hinzuzufügen. Jedoch ist es offensichtlich keine gute Idee, Elemente am Anfang des Arrays hinzuzufügen, da es erforderlich ist, alle existierenden Elemente zu verschieben, d. H. Diese Auswahl würde O (N) machen (wobei N die Anzahl von Elementen im Stapel ist). Wenn wir Elemente am Ende des Arrays hinzufügen, hängt die Zeit für Push davon ab, wie wir mit der Erweiterung des Arrays umgehen. Die naive Implementierung macht Push-O (1), wenn das Array nicht voll ist, O (N), wenn es voll ist, und O (1) im Durchschnitt. Wenn wir den Schatten-Array-Trick verwenden, dann ist push immer O (1). Hier sind vor und nach Bildern, die die Auswirkungen eines Aufrufs zum Push veranschaulichen: Und heres der Code für die Push-Methode: Die Pop-Methode muss das Top-of-Stack-Element zu entfernen, und es zurückgeben, wie unten dargestellt. Beachten Sie, dass der Wert bbb noch in Items2 ist, dieser Wert aber nicht mehr im Stapel liegt, da numItems 2 ist (was bedeutet, dass item1 das letzte Element im Stack ist). TEST YOURSELF 2 Vervollständigen Sie die pop-Methode mit dem folgenden Header Die peek-Methode ist der Pop-Methode sehr ähnlich, außer dass sie nur den Wert des oberen Stacks zurückgibt, ohne den Stack zu ändern. Die isEmpty-Methode gibt einfach true zurück, wenn ifn numItems Null ist. TEST YOURSELF 3 Füllen Sie die folgende Tabelle aus, indem Sie die Big-O-Notation verwenden, um die schlechtesten und durchschnittlichsten Zeiten für jede der ArrayStack-Methoden für einen Stapel der Größe N zu erhalten. Linked-List-Implementierung Um einen Stack mithilfe einer verknüpften Liste zu implementieren, Muss zuerst die Listnode-Klasse definieren. Die Listnode-Definition ist die gleiche, die wir für die Linklisten-Implementierung der LinkedList-Klasse verwendet haben. Die Signaturen der Methoden der StackADT-Schnittstelle sind unabhängig davon, ob der Stack unter Verwendung eines Arrays implementiert ist oder eine verkettete Liste verwendet, um das StackADT mit Hilfe einer verketteten Liste zu implementieren, und ändern Sie den Namen der Klasse, die den Stack implementiert, und den Typ der Items Feld: Wie oben diskutiert, ist eine wichtige Eigenschaft von Stapeln, dass Elemente nur an einem Ende (der Spitze des Stapels) gedrückt und geknallt werden. Wenn wir einen Stapel mit Hilfe einer verketteten Liste implementieren, können wir wählen, welches Ende der Liste dem oberen Ende des Stacks entspricht. Es ist am einfachsten und am effizientesten, Elemente an der Vorderseite einer verknüpften Liste hinzuzufügen und zu entfernen, daher wählen wir die Vorderseite der Liste als das obere Ende des Stapels aus (dh das Item-Feld ist ein Zeiger auf den Knoten, der die Top-of-Stack-Element). Unten ist ein Bild eines Stapels, der in diesem Fall durch eine verknüpfte Liste dargestellt wird, die Elemente wurden in alphabetischer Reihenfolge gedrückt, so dass cc an der Spitze des Stapels ist: Beachten Sie, dass in der Abbildung die Spitze des Stapels nach links An der Vorderseite der Liste), während für die Array-Implementierung die Spitze des Stacks rechts (am Ende des Arrays) war. Wie können Sie die Pop-Methode schreiben? Sie müssen die folgenden Schritte ausführen: Überprüfen Sie, ob der Stack in diesem Fall leer ist, werfen Sie eine EmptyStackException aus. Entfernen Sie den ersten Knoten aus der verknüpften Liste, indem Sie die Elemente items. getNext () setzen. NumItems dekrementieren. Geben Sie den Wert zurück, der sich in dem ersten Knoten in der Liste befand. Beachten Sie, dass der erste Knoten bereits aus der Liste entfernt worden ist, um den letzten Schritt zurückzugeben (Rückgabe des Wertes des obersten Stapels), so dass wir seinen Wert speichern müssen, um ihn zurückzugeben (nennen Sie diesen Schritt 2 (a)). Hier ist der Code und eine Illustration, was passiert, wenn Pop für einen Stapel mit cc, bb, aa (mit cc an der Spitze) aufgerufen wird. Betrachten wir nun die Push-Methode. Hier sind vor und nach Bildern die Auswirkungen eines Aufrufs auf Push, wenn der Stack unter Verwendung einer verketteten Liste implementiert wird, darzustellen: Die Schritte, die ausgeführt werden müssen, sind: Erstellen Sie einen neuen Knoten, dessen Datenfeld das zu schiebende Objekt enthält und dessen nächstes Feld enthält einen Zeiger auf den ersten Knoten in der Liste (oder null, wenn die Liste leer ist). Beachten Sie, dass der Wert für das nächste Feld des neuen Knotens der Wert im Feld LLStack s Items ist. Ändern Sie Elemente, um auf den neuen Knoten zu zeigen. Inkrementieren von numItems. TEST YOURSELF 4 Führen Sie die Push-Methode mit dem folgenden Header aus. Die übrigen Methoden (Konstruktor, Peek und Leer) sind ganz einfach. Sie sollten in der Lage, sie ohne größere Probleme umzusetzen. TEST YOURSELF 5 Füllen Sie die folgende Tabelle aus, indem Sie die Big-O-Notation verwenden, um die Worst-Case-Zeiten für jede der LLStack-Methoden für einen Stack der Größe N anzugeben, wobei eine Implementierung der verknüpften Liste vorausgesetzt wird. Schauen Sie zurück auf den Tisch, den Sie für die Array-Implementierung ausgefüllt haben. Wie sind die Zeiten zu vergleichen Was sind die Vor-und Nachteile der Verwendung eines Arrays vs mit einer verketteten Liste zur Implementierung der Stack ADT Implementing Queues Der Hauptunterschied zwischen einem Stapel und einer Warteschlange ist, dass ein Stapel nur von oben, während eine Warteschlange zugegriffen wird Wird von beiden Enden (von hinten zum Hinzufügen von Gegenständen und von der Vorderseite zum Entfernen von Gegenständen) zugegriffen. Dies macht sowohl das Array als auch die Verknüpfungslistenimplementierung einer Warteschlange komplizierter als die entsprechenden Stapelimplementierungen. Array Implementation Als erstes betrachten wir eine Queue-Implementierung, die unserer (arraybasierten) List-Implementierung sehr ähnlich ist. Heres die Klassendefinition: Wir könnten Enqueue implementieren, indem wir das neue Element am Ende des Arrays einfügen und dequeue implementieren, indem wir das erste Element im Array speichern, alle anderen Elemente nach links verschieben und den gespeicherten Wert zurückgeben. Das Problem bei diesem Ansatz ist, dass, obwohl die Enqueue-Operation effizient ist, die Dequeue-Operation nicht - es erfordert Zeit proportional zu der Anzahl der Elemente in der Warteschlange. Um sowohl enqueue als auch dequeue effizient zu machen, benötigen wir folgende Einsicht: Es gibt keinen Grund, die Front der Warteschlange immer in Items0 zu zwingen. Können wir es nach oben verschieben, wenn Elemente dequeued werden. Um dies zu tun, müssen wir die Indizes der Elemente an der Vorder - und Rückseite der Warteschlange beibehalten (also müssen wir der ArrayQueue-Klasse, frontIndex und rearIndex zwei neue Felder hinzufügen). Um diese Idee zu veranschaulichen, ist hier ein Bild einer Warteschlange, nachdem einige Enqueue - und Dequeue-Operationen durchgeführt wurden: Überlegen Sie nun, was mit dieser Warteschlange passieren soll, wenn wir zwei weitere Elemente einschalten: dd und ee. Klar sollte dd in items6 gespeichert werden. Dann was Wir könnten die Größe des Arrays und setzen ee in items7. Aber das würde zu verschwendeten Raum führen - wir würden niemals Items0 wiederverwenden. Einzelteile1. Oder Items2. Im Allgemeinen würden die Elemente in der Warteschlange nach rechts im Array verschoben, wodurch mehr und mehr vergeudeten Speicherplatz am Anfang des Arrays. Ein besserer Ansatz ist, die hintere Indexumwicklung (in diesem Fall von 6 bis 0) so lange zulassen, wie es leeren Raum in der Vorderseite des Arrays. Ähnlich ist es, wenn wir nach dd und ee vier Elemente dequeue (so dass nur ee in der Warteschlange bleibt), muss der Frontindex von 6 auf 0 umwickeln. Heres ein Bild von dem, was passiert, wenn wir dd und ee enqueue: Konzeptionell ist das Array ein kreisförmiges Array. Es kann leichter sein, es als einen Kreis zu visualisieren. Zum Beispiel könnte das Array für die abschließende Warteschlange, die oben gezeigt wird, als angenommen werden: Wir müssen noch darüber nachdenken, was passieren sollte, wenn das Array voll ist, betrachten Sie diesen Fall in einer Minute. Hierbei handelt es sich um den Code für die Enqueue-Methode, wobei der vollständige Array-Fall noch ausgefüllt werden muss: Beachten Sie, dass anstelle von incrementIndex der mod operator () verwendet werden kann, und schreiben Sie: rearIndex (rearIndex 1) items. length. Allerdings ist der Mod-Operator ziemlich langsam und es ist leicht, diesen Ausdruck falsch, so dass wir die Hilfsmethode (mit einem Check für die Wrap-around-Fall) statt. Um zu sehen, warum wir nicht einfach expandArray verwenden können, wenn das Array voll ist, betrachte das unten gezeigte Bild. Nach Aufruf von expandArray. Das letzte Element in der Warteschlange ist immer noch rechts vor dem ersten Element - es gibt noch keinen Platz, um das neue Element (und es gibt eine große Lücke in der Mitte der Warteschlange, von Items7 zu Items13). Das Problem ist, dass expandArray die Werte im alten Array in die gleichen Positionen im neuen Array kopiert. Dies funktioniert nicht für die Warteschlangen-Implementierung, die wir benötigen, um die umbrochenen Werte zu verschieben, um nach den nicht umbrochenen Werten in dem neuen Array zu kommen. Die Schritte, die ausgeführt werden müssen, wenn das Array voll ist: Zuweisen eines neuen Arrays von zweimal der Größe. Kopieren Sie die Werte im Bereich itemsfrontIndex auf itemsitems. length-1 in das neue Array (beginnend bei position frontIndex im neuen Array). Kopieren Sie die Werte in den Bereich items0 in itemrearIndex in das neue Array (beginnend bei Position items. length im neuen Array). Hinweis: wenn die Vorderseite der Warteschlange in Items0 war. Dann wurden alle Werte durch Schritt 2 kopiert, so dass dieser Schritt nicht benötigt wird. Setzen Sie Elemente, um auf das neue Array zu zeigen. Fixieren Sie den Wert von rearIndex. Heres eine Abbildung: Und heres der endgültige Code für enqueue: Die dequeue Methode wird auch Methode incrementIndex verwenden, um ein FrontIndex (mit Wrap-around) hinzuzufügen, bevor der Wert, der an der Vorderseite der Warteschlange war. Die andere ArrayQueue-Methode isEmpty. Ist das gleiche wie für die ArrayStack-Klasse - es verwendet nur den Wert des Felds numItems. Verknüpfte Liste Implementierung Die erste Entscheidung bei der Planung der Verknüpfungslistenimplementierung der Warteschlange ADT ist, welches Ende der Liste der Vorderseite der Warteschlange entspricht. Erinnern Sie sich, dass Elemente auf der Rückseite der Warteschlange hinzugefügt und von der Vorderseite der Warteschlange entfernt werden müssen. Daher sollten wir unsere Wahl auf der Grundlage, ob es einfacher, hinzufügen / entfernen Sie einen Knoten aus dem Vorder - / Ende einer verketteten Liste. Wenn wir Zeiger sowohl auf den ersten als auch den letzten Knoten der Liste halten, können wir einen Knoten an jedem Ende in konstanter Zeit hinzufügen. Obwohl wir den ersten Knoten in der Liste in konstanter Zeit entfernen können, erfordert das Entfernen des letzten Knotens zuerst das Lokalisieren des vorherigen Knotens, was Zeit erfordert, die proportional zur Länge der Liste ist. Daher sollten wir wählen, um das Ende der Liste machen die Rückseite der Warteschlange und die Vorderseite der Liste die Front der Warteschlange sein. Die Klassendefinition ist ähnlich der Arrayimplementation: Heres ein Bild einer Warteschlange mit drei Elementen, aa, bb, cc, mit aa an der Vorderseite der Warteschlange: Sie sollten in der Lage sein, alle LLQueue Methoden mit dem zu schreiben Code, den Sie für die Verknüpfungsliste-Implementierung der Liste ADT als Leitfaden geschrieben haben. Vergleich von Array - und Linked-List-Implementierungen Die Vor - und Nachteile der beiden Implementierungen sind im wesentlichen die gleichen wie die Vor - und Nachteile bei der List-ADT: Bei der Linklistenimplementierung muss für jeden Posten in der Stapel / Warteschlange, während das Array nur die Elemente selbst speichert. Auf der anderen Seite ist der Platz, der für eine verknüpfte Liste verwendet wird, immer proportional zur Anzahl der Elemente in der Liste. Dies gilt nicht notwendigerweise für die Array-Implementierung wie beschrieben: Wenn eine Menge von Elementen zu einem Stapel / einer Warteschlange hinzugefügt und dann entfernt werden, kann die Größe des Arrays beliebig größer als die Anzahl von Elementen in dem Stapel / der Warteschlange sein. Allerdings könnten wir dieses Problem beheben, indem Sie die Pop / Dequeue-Operationen ändern, um das Array zu schrumpfen, wenn es zu leer wird. Für die Array-Implementierung sind die Worst-Case-Zeiten für die Push - und Enqueue-Methoden O (N) für die naive Implementierung, für einen Stapel / eine Warteschlange mit N Elementen (um ein neues Array zuzuordnen und die Werte zu kopieren) unter Verwendung des Shadow-Array-Tricks , Sind diese beiden Operationen O (1). Für die Verknüpfungslistenimplementierung sind Push und Enqueue immer O (1). Anwendungen von Stacks und Queues Stacks werden verwendet, um Methoden zur Laufzeit zu verwalten (wenn eine Methode aufgerufen wird, werden ihre Parameter und lokale Variablen auf einen Stapel gedrückt, wenn die Methode zurückgibt, die Werte werden aus dem Stapel gelocht). Viele Parsing-Algorithmen (die von Compilern verwendet werden, um zu bestimmen, ob ein Programm syntaktisch korrekt ist) beinhalten die Verwendung von Stapeln. Stapel können verwendet werden, um arithmetische Ausdrücke (z. B. durch ein einfaches Rechnerprogramm) auszuwerten, und sie sind auch für einige Operationen auf Graphen nützlich. Eine Datenstruktur, die wir später im Semester lernen werden. Warteschlangen sind für viele Simulationen nützlich und werden auch für einige Operationen auf Graphen und Bäumen verwendet. TEST YOURSELF Vollständige Methode reverseQ. Dessen Header unten angegeben ist. Methode reverseQ sollte einen Stack verwenden, um die Reihenfolge der Elemente in seinem Queue-Parameter umzukehren.4.3 Stacks und Queues In diesem Abschnitt stellen wir zwei eng verwandte Datentypen zur Manipulation beliebig großer Sammlungen von Objekten vor: Stack und Queue. Stapel und Warteschlangen sind Sonderfälle der Idee einer Sammlung. Jeder ist durch vier Operationen gekennzeichnet: Erstellen Sie die Sammlung, legen Sie ein Element, entfernen Sie ein Element, und testen Sie, ob die Auflistung leer ist. Stapel. Ein Stack ist eine Sammlung, die auf der Last-in-First-out (LIFO) Politik basiert. Traditionell nennen wir die Stack-Insert-Methode push () und die stack remove-Operation pop (). Wir haben auch eine Methode, um zu testen, ob der Stack leer ist, wie in der folgenden API angegeben: Array-Implementierungen von Stacks. Die Darstellung von Stacks mit Arrays ist eine natürliche Idee. Insbesondere behalten wir eine Instanzvariable n bei, die die Anzahl der Elemente im Stack und die Array-Elemente speichert, die die n Items speichern, wobei das zuletzt eingefügte Element in itemsn-1 und das am wenigsten kürzlich eingefügte Element in items0 enthalten sind. Diese Richtlinie ermöglicht das Hinzufügen und Entfernen von Elementen am Ende, ohne irgendwelche der anderen Elemente im Stapel zu verschieben. Fixed-Length-Array-Implementierung eines Stapels von Strings. ArrayStackOfStrings. java implementiert diesen Ansatz für einen Stapel von Zeichenketten, deren maximale Kapazität durch das Argument für den Konstruktor angegeben wird. Um ein Element zu entfernen, dekrementieren wir n und geben dann a zurück, um ein neues Element einzufügen, setzen wir ein gleiches auf das neue Element und erhöhen dann n. Größe der Array-Implementierung eines Stapels von Strings. ResizingArrayStackOfStrings. java ist eine Version von ArrayStackOfStrings. java, die die Länge der Array-Elemente dynamisch anpasst, sodass sie ausreichend groß ist, um alle Elemente zu halten, aber nicht so groß, dass eine übermäßige Menge an Speicherplatz vergeudet wird. Erstens, in Push (). Ob es Platz für das neue Element gibt, wenn nicht, erstellen wir ein neues Array mit der doppelten Länge des alten Arrays und kopieren die Elemente aus dem alten Array in das neue Array. Ebenso in Pop (). Ob das Array zu groß ist, und wir halbieren seine Länge, wenn dies der Fall ist. Diese Verdoppelungs - und Halbierungsstrategie garantiert, dass der Stapel nie überläuft und nie weniger als ein Viertel voll wird. Anpassen der Array-Implementierung eines generischen Stacks. ResizingArrayStack. java implementiert einen generischen Stack mit einem Resizing-Array. Aus technischen Gründen ist ein Cast erforderlich, wenn das Array von Generics zugewiesen wird. Verknüpfte Listen. Eine einfach verkettete Liste besteht aus einer Folge von Knoten. Wobei jeder Knoten eine Referenz (oder Verknüpfung) zu seinem Nachfolger enthält. Nach Konvention ist die Verknüpfung im letzten Knoten null. Um anzuzeigen, dass es die Liste beendet. Bei der objektorientierten Programmierung ist die Implementierung verketteter Listen nicht schwierig. Wir definieren eine Klasse für die Knoten-Abstraktion, die rekursiv in der Natur ist: Ein Knoten-Objekt hat zwei Instanzvariablen: einen String und einen Knoten. Der String ist ein Platzhalter in diesem Beispiel für alle Daten, die wir mit einer verketteten Liste strukturieren möchten (wir können beliebige Instanzvariablen verwenden). Die Instanzvariable vom Typ Knoten charakterisiert die verknüpfte Struktur der Datenstruktur. Verknüpfen einer verknüpften Liste. Zum Beispiel, um eine verknüpfte Liste zu erstellen, die die Elemente enthält. Sein . Und oder. Erstellen wir für jeden Artikel einen Knoten: Einfügen. Angenommen, Sie möchten einen neuen Knoten in eine verkettete Liste einfügen. Der einfachste Ort, um dies zu tun ist am Anfang der Liste. Zum Beispiel, um die Zeichenfolge nicht am Anfang einer gegebenen verknüpften Liste einzufügen, deren erster Knoten zuerst ist. Speichern wir zuerst in einer temporären Variablen oldFirst. Weisen Sie zuerst einen neuen Knoten zu. Und ordnen Sie das Item-Feld nicht an und sein nächstes Feld an oldFirst. Entfernen. Angenommen, Sie möchten den ersten Knoten aus einer Liste entfernen. Dieser Vorgang ist noch einfacher: Einfach zuerst den Wert first. next. Traversal zuordnen. Um jedes Element in einer verknüpften Liste zu untersuchen, initialisieren wir eine Schleifenindexvariable x, die auf den ersten Knoten der verknüpften Liste verweist. Dann finden wir den Wert des mit x verbundenen Elements, indem wir auf x. item zugreifen. Und aktualisieren Sie dann x, um auf den nächsten Knoten in der verknüpften Liste zu verweisen, ihm den Wert von x. next zuzuweisen und diesen Vorgang zu wiederholen, bis x Null ist (was angibt, dass wir das Ende der verketteten Liste erreicht haben). Dieser Vorgang ist als Durchlaufen der Liste bekannt und wird in diesem Codefragment prägnant ausgedrückt: Implementieren von Stapeln mit verknüpften Listen. Die Darstellung von Stapeln mit verknüpften Listen ist eine natürliche Idee. Insbesondere pflegen wir zunächst eine Instanzvariable, die einen Verweis auf das zuletzt eingefügte Element speichert. Mit dieser Richtlinie können Sie Elemente am Anfang der verknüpften Liste hinzufügen und entfernen, ohne auf die Links anderer Elemente in der verknüpften Liste zuzugreifen. Linked-List-Implementierung eines Stapels von Strings. LinkedStackOfStrings. java verwendet eine verknüpfte Liste, um einen Stapel von Zeichenfolgen zu implementieren. Die Implementierung basiert auf einem verschachtelten Knoten wie der, den wir verwenden. Java erlaubt es, andere Klassen innerhalb von Klassenimplementierungen in dieser natürlichen Weise zu definieren und zu verwenden. Wir nennen die verschachtelte Klasse als privat, weil Clients keine der Details der verknüpften Listen kennen müssen. Linked-List-Implementierung eines generischen Stacks. Stack. java implementiert einen generischen Stack mit einer einzigen verketteten Liste. Warteschlange. Eine Warteschlange unterstützt das Einfügen und Entfernen von Operationen mit einer First-In First-Out (FIFO) Disziplin. Nach der Konvention, nennen wir die Warteschlange Insert Operation Enqueue und die Remove Operation Dequeue. Wie in der folgenden API angegeben: Linked-List-Implementierung einer Warteschlange. Queue. java implementiert eine FIFO-Warteschlange von Zeichenfolgen mithilfe einer verknüpften Liste. Wie Stapel. Wir pflegen einen Verweis zuerst auf den am wenigsten kürzlich hinzugefügten Knoten in der Warteschlange. Für die Effizienz behalten wir auch eine Referenz für den zuletzt hinzugefügten Knoten in der Warteschlange bei. Größe der Array-Implementierung einer Warteschlange ändern. ResizingArrayQueue. java implementiert eine Warteschlange mit einem resizing-Array. Es ähnelt ResizingArrayStack. java. Aber schwieriger, da wir Elemente aus den entgegengesetzten Enden des Arrays hinzufügen und entfernen müssen. Generika. Wir haben Stack-Implementierungen entwickelt, die es uns ermöglichen, einen Stack von einem bestimmten Typ, wie String zu erstellen. Ein spezieller Mechanismus in Java, der als generische Typen bekannt ist, ermöglicht es uns, Sammlungen von Objekten eines Typs zu erstellen, die vom Clientcode festgelegt werden sollen. Implementieren einer generischen Sammlung. Um eine generische Auflistung zu implementieren, geben wir einen Typ-Parameter an. Wie Einzelteil. In spitzen Klammern und verwenden Sie diese Art Parameter in unserer Implementierung anstelle eines bestimmten Typs. Zum Beispiel ist Stack. java generische Version von LinkedStackOfStrings. java Verwenden einer generischen Auflistung. Um eine generische Auflistung zu verwenden, muss der Client das Typargument angeben, wenn der Stapel erstellt wird: Autoboxing. Wir haben unsere Stacks entworfen, um generisch zu sein. So dass sie Objekte jeglicher Art. Die Java-Sprach-Features bekannt als AutoBoxing und Unboxing ermöglichen es uns, generischen Code mit primitiven Typen wieder verwenden. Java liefert eingebaute Objekttypen, die als Wrappertypen bezeichnet werden. Eine für jeden der primitiven Typen: Boolean. Ganze Zahl. Doppelt. Charakter. und so weiter. Java wandelt automatisch zwischen diesen Referenztypen und den entsprechenden Primitivtypen um, so dass wir Code wie folgt schreiben können: Iteration. Manchmal muss der Client alle Elemente einer Sammlung einzeln zugreifen, ohne sie zu löschen. Um die Kapselung zu pflegen, wollen wir die interne Darstellung der Warteschlange (Array oder verkettete Liste) nicht dem Client offenlegen. Um diesem Entwurfsmuster gerecht zu werden, bietet Java die foreach-Anweisung an. Sie sollten folgendes für die Anweisung im folgenden Codefragment wie für jede Zeichenkette s in der Auflistung interpretieren, ausdrucken. Die Implementierung einer Sammlung, die Iteration auf diese Weise unterstützt, erfordert die Implementierung von Javas java. util. Iterator und java. util. Iterable Schnittstellen. Details finden Sie im Lehrbuch. Stapel - und Warteschlangenanwendungen. Stacks und Warteschlangen haben zahlreiche nützliche Anwendungen. Arithmetische Ausdrucksauswertung. Eine wichtige Anwendung von Stacks ist das Parsen. Ein Compiler muss beispielsweise arithmetische Ausdrücke analysieren, die mit der Infix-Notation geschrieben wurden. Zum Beispiel wird der folgende infix-Ausdruck zu 212 ausgewertet. Evaluate. java wertet einen vollständig parenthesisierten arithmetischen Ausdruck aus. Funktion-Aufruf-Abstraktion. Die meisten Programme verwenden Stapel implizit, weil sie eine natürliche Methode zur Implementierung von Funktionsaufrufen wie folgt unterstützen: An jedem Punkt während der Ausführung einer Funktion definieren Sie ihren Zustand als die Werte aller Variablen und einen Zeiger auf die nächste Anweisung Ausgeführt. Die natürliche Weise, die Funktionsaufruf-Abstraktion zu implementieren, besteht darin, einen Stapel zu verwenden. Um eine Funktion aufzurufen, drücken Sie den Status auf einen Stapel. Um von einem Funktionsaufruf zurückzukehren, geben Sie den Zustand aus dem Stack zurück, um alle Variablen auf ihre Werte vor dem Aufruf der Funktion zurückzusetzen und die Ausführung mit der nächsten auszuführenden Anweisung fortzusetzen. M / M / 1-Warteschlange. Eines der wichtigsten Warteschlangenmodelle ist eine M / M / 1-Warteschlange, die gezeigt hat, dass sie viele Situationen der realen Welt präzise abbildet. Es ist durch drei Eigenschaften gekennzeichnet: Es gibt eine servermdasha FIFO Warteschlange. Interarrival Zeiten in die Warteschlange gehorchen einer exponentiellen Verteilung mit Rate Lambda pro Minute. Dienstzeiten aus einer nicht leeren Warteschlange gehorchen einer exponentiellen Verteilung mit einer Rate mu pro Minute. Code.