Ich möchte damit beginnen, dass dies KEINE Hausaufgabe ist. Ich lese Einführung in Algorithmen - den berühmten CLRS-Text, um ein besserer Programmierer zu werden. Ich versuche, die im Buch angegebenen Probleme und Übungen selbst zu lösen.
Ich versuche, Übung 10.1-2 aus Kapitel 10 Elementare Datenstrukturen aus CLRS Second Edition zu lösen . Hier ist was seine Zustände:
Erklären Sie, wie Sie zwei Stapel in einem Array A [1..n] so implementieren , dass keiner der Stapel überläuft, es sei denn, die Gesamtzahl der Elemente in beiden Stapeln beträgt n . Die PUSH- und POP-Operationen sollten in O (1) -Zeit ausgeführt werden.
Die Lösung, die ich bisher gefunden habe, ist:
Lassen Sie Array A [1..n] zwei Stapel implementieren: S1 [1..i] und S2 [i..n] .
Wenn für die Operationen PUSH-S1 und PUSH-S2 der Stapel "voll" ist, beginnen Sie, Elemente in den anderen Stapel zu schieben (z. B. wenn der Stapel S1 voll ist, wenn versucht wird, ein neues Element einzuschieben, schieben Sie dieses Element hinein Stapel S2 und umgekehrt).
Das Problem bei diesem Ansatz ist, dass ich nicht in der Lage sein werde, POP-S1 oder POP-S2 zuverlässig auszuführen, da es keine Möglichkeit gibt, sich zu merken, welches Element zu welchem Stapel gehört. Wenn es sich bei den Elementen des Stapels um (Schlüssel-, Wert-) Paare handelt, wobei der Schlüssel die Stapelnummer ist, müsste ich im schlimmsten Fall i- oder (ni) -mal suchen, um ein Element zu platzieren. Dies ist O (n) ) (zögern Sie nicht mich zu korrigieren, wenn ich mich hier irre), das wäre nicht O (1) .
Ich habe mich jetzt schon eine ganze Weile mit der Frage beschäftigt. Bin ich auf dem richtigen Weg? Kann jemand meine möglichen Hinweise zur Lösung dieses Problems geben?
Wie sollte ich im Allgemeinen über diese Probleme nachdenken? Oder können nur wirklich intelligente Menschen solche Probleme lösen? Wird es mir dabei helfen, Probleme wie diese anzugehen / zu lösen (dh Erfahrungen zu sammeln), besser zu werden?
Ich warte auf Erleuchtung.
quelle
Antworten:
Ein weiterer Hinweis zusätzlich zu dem, was Yuval gesagt hat: Es hilft, die Stapel auf eine bestimmte Weise in den Arrays zu platzieren und ihre Wachstumsrichtung entsprechend festzulegen. Sie müssen nicht in die gleiche Richtung wachsen.
quelle
Hier sind einige Hinweise:
quelle
Der erste Stapel beginnt bei 1 und wächst in Richtung n, während der zweite Stapel in Richtung n beginnt und nach unten wächst. Ein Stapelüberlauf tritt auf, wenn ein Element gedrückt wird, wenn die beiden Stapelzeiger nebeneinander liegen.
quelle
Diese Methode nutzt den verfügbaren Platz effizient aus. Es wird kein Überlauf verursacht, wenn in arr [] Speicherplatz verfügbar ist. Die Idee ist, zwei Stapel aus zwei extremen Ecken von arr [] zu starten. stack1 beginnt am ganz linken Element, das erste Element in stack1 wird auf Index 0 verschoben. Der stack2 beginnt an der ganz rechten Ecke, das erste Element in stack2 wird auf Index (n-1) verschoben. Beide Stapel wachsen (oder schrumpfen) in entgegengesetzter Richtung. Um auf Überlauf zu prüfen, müssen wir nur den Abstand zwischen den oberen Elementen beider Stapel prüfen.
quelle
Ich dachte an eine andere Lösung. Wenn wir das Array in zwei Hälften teilen (oder so nah wie möglich, wenn das Array eine ungerade Länge hat) und das erste Element in den ersten Stapel und das zweite Element in den zweiten Stapel verschieben. Während des Knallens konnten wir diese Schritte nachvollziehen. Würde eine solche Implementierung jedoch gegen ein Stack-Prinzip verstoßen?
quelle
Einige Hinweise
Erstellen Sie ein Array
Array-Elemente mit ungeradem Index sind für stack1
Array-Elemente mit geradem Index sind für stack2
Jetzt können Sie beide Stapel von links nach rechts vergrößern
Behalten Sie einfach Variablen bei, die die obere Position beider Stapel beibehalten. Sie müssen das Array nicht durchsuchen.
und wenn stack1 voll wird, während stack2 leer ist, können Sie nach zusätzlichen stack1-Elementen in stack2 suchen, indem Sie einige Variablen verwalten
quelle