Können drei Stapel in einem Array mit O (1) Push / Pop-Zeit implementiert werden?

Zwei Stapel können mithilfe eines Arrays mit fester Größe effizient implementiert werden: Stapel Nr. 1 beginnt am linken Ende und wächst nach rechts, und Stapel Nr. 2 beginnt am rechten Ende und wächst nach links. Ist das gleiche für drei Stapel möglich?

Insbesondere ist es möglich, drei Stapel unter den folgenden Bedingungen zu implementieren:

Sie haben ein Array mit fester Größe, das N Objekte aufnehmen kann.
Solange die Summe der drei Stapelgrößen <N ist, sollte push () nicht fehlschlagen.
Sowohl push () als auch pop () sollten O (1) dauern.
Zusätzlich zum Array können Sie nur O (1) zusätzlichen Speicherplatz verwenden.

Hier sind Beispiele für Lösungen, die diese Anforderungen nicht erfüllen:

Teilen Sie das Array in 3 feste Teile und verwenden Sie jeden Teil für einen Stapel (verletzt 2).
Ähnlich wie oben, jedoch mit beweglichen Grenzen zwischen Stapeln (verletzt 3).
Einfache Implementierungen auf der Basis verknüpfter Listen (Verstöße gegen 4).

Ich akzeptiere nicht triviale Algorithmen oder Unmöglichkeitsbeweise, auch wenn sie nicht alle Bedingungen (1) - (4) genau erfüllen, zum Beispiel einen Algorithmus, bei dem Push / Pop O (1) amortisierte Zeit benötigt oder bei dem die zusätzlicher Speicher ist kleiner als O (N), z. B. O (log N). Oder ein Unmöglichkeitsnachweis, der zeigt, dass beispielsweise der Zugriff auf weniger als 5 Elemente des Arrays pro Push / Pop nicht möglich ist.

ds.data-structures lower-bounds user1020406
quelle

Ich weiß nicht, ob Sie dies als Verstoß gegen Anforderung 4 betrachten, aber wenn jedes "Objekt" in Ihrem N-Objekt-Array ein zusätzliches Feld wie einen ganzzahligen Index enthalten kann, können Sie die "verknüpften Listen" in Ihrem Array implementieren . Sie können den Index der Oberseite jedes der 3 Stapel mit 3 externen Variablen halten, und jedes "Objekt" kann auf das vorherige Element zeigen, auf das es seinen Stapel hat.

Avi Tal

Mit "Objekten" meinte ich Dinge, die push () akzeptiert und pop () zurückgibt. Aus Sicht der Stapelimplementierung handelt es sich lediglich um undurchsichtige Datenblobs (beispielsweise kann ein Objekt eine 32-Bit-Ganzzahl sein). Die Stack-Implementierung sollte diese Objekte in keiner Weise ändern.

user1020406

N

$N$

O (\sqrt{N})

$O(\sqrt{N})$

O (\sqrt{N})

$O(\sqrt N)$

Antworten:

$\Theta(n^\varepsilon)$ $\Theta(\sqrt{n})$ $\sqrt{n}$ $\sqrt{n}$ , wobei jeder Block für genau einen Stapel verwendet wird und einen einzelnen Zeiger auf den nächsten Block in diesem Stapel enthält.

jbapple
quelle

Sei N die Länge des zugrunde liegenden Arrays. Ich kann mir Stapel als verknüpfte Listen großer Blöcke vorstellen, sodass die Gesamtzahl der Blöcke nicht mehr als O (log2 (N)) beträgt. Platzieren Sie den dritten Stapel zwischen den ersten beiden am Index von N / 2. Wir haben also 3 besetzte Gebiete und 2 freie. Wenn ein Stapel das nächste Element nicht akzeptieren kann, bedeutet dies, dass ein freier Bereich erschöpft ist. Wenn auch der andere erschöpft ist, ist der gesamte Speicher erschöpft. Ansonsten gibt es einen weiteren freien Bereich mit einer Größe von nicht mehr als N / 2. Setzen Sie den übergelaufenen Stapel in diesen freien Bereich fort. so dass die gesamte Konfiguration dem anfänglichen Layout der Stapel ähnelt. Da der freie Speicher jetzt nicht mehr als die Hälfte des Anfangs beträgt, gibt es nicht mehr als log2 (N) solcher Verknüpfungsoperationen. Jede Verknüpfungsoperation erfordert eine feste Speichermenge, um den vorherigen Status des Stapels zu speichern. So,

Alexei Kaigorodov
quelle

Wie recyceln Sie Speicher, der durch das Löschen von Dingen aus einem der großen Blöcke erhalten wurde?

Emil Jeřábek

Gute Frage. Eine schnelle Antwort ist, dass der frei werdende Block seinen Speicher in den freien Bereich zurückgibt, aus dem er zuvor entnommen wurde. Aber was ist, wenn der freie Bereich seit dem Zeitpunkt des Zuweisungsspeichers für diesen Block kleiner geworden ist und der Block jetzt nicht daran angrenzt? Dies führt zu einer Fragmentierung des freien Speichers. Es kann mehr als 2 freie Bereiche geben, was meine gesamte Konstruktion ruiniert.

Alexei Kaigorodov

Popping ist in der Tat das Problem hier, aber Alexeis Konstruktion bietet eine schöne Obergrenze für die Version des Problems, nach der Dmitri in den Kommentaren gefragt hat: Was ist, wenn alle Pushs vor allen Pops stattfinden müssen? Ich frage mich, ob in diesem Fall etwas Besseres als O (log N) möglich ist.

user1020406