Wie implementiert man zwei Stacks in einem Array?

15

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.

Suyash Gupta
quelle
3
"Wird es mir helfen, Probleme wie diese anzugehen / zu lösen (dh Erfahrungen zu sammeln), dies zu verbessern?" Nach meiner Erfahrung ist dies definitiv der Fall. Wenn nichts anderes, dann haben Sie das Problem auf vielfältige Weise bedacht und allein dadurch mehr Einsicht entwickelt. Wie mir kürzlich gesagt wurde: Der beste Weg, gute Ideen zu haben, besteht darin, viele Ideen zu haben.
G. Bach

Antworten:

7

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.

G. Bach
quelle
5

Hier sind einige Hinweise:

  1. Einer der Stapel sollte "hoch" und der andere "runter" wachsen.
  2. Es gibt keine Möglichkeit, sich zu merken, welches Element zu welchem ​​Stapel gehört - Sie dürfen zusätzliche Variablen verwenden, um sich bei solchen Dingen zu helfen. (Dies ist bei der im ersten Hinweis vorgeschlagenen Lösung sinnvoller.)
Yuval Filmus
quelle
1

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.

Pankaj Moolrajani
quelle
1

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.

MONU KUMAR
quelle
-1

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?

MindBrain
quelle
Willkommen in der Informatik ! Ihr Vorschlag funktioniert leider nicht. In einem Array von LängeN, Sie sollten zwei Stapel speichern können , die nicht überläuft , wenn ihre Gesamtgröße überschreitet N (so sollte es in der Lage sein , mit einem leeren Stapel und einem Stapel von Länge zu bewältigenN). Ihre Lösung läuft über, wenn einer der Stapel den zulässigen Wert überschreitetN/2.
David Richerby
-2

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

user4129542
quelle
Das ist sehr verworren. Die vorhandenen Antworten geben bereits viel einfachere Möglichkeiten zur Lösung des Problems
David Richerby