Einen Stack entwerfen, der auch in O(1) amortisierter Zeit entladen werden kann?

Question

Ich habe einen abstrakten Datentyp, der als eine von links nach rechts gespeicherte Liste mit den folgenden möglichen Operationen betrachtet werden kann: Push: Hinzufügen eines neuen Eintrags am linken Ende der Liste Pop: Entfernen des Eintrags am linken Ende der Liste Pull: Entfernen des Eintrags am rechten Ende der Liste

Implementieren Sie dies mit drei Stapeln und konstantem zusätzlichem Speicher, so dass die amortisierte Zeit für jede Push-, Pop- oder Pull-Operation konstant ist. Die Stapel haben grundlegende Operationen, isEmpty, Push und Pop.

Amortisierte Zeit bedeutet: "Wenn ich diese Menge an Zeit aufbringe, kann ich einen weiteren Block davon aufbrauchen und ihn in einer Zeitbank speichern, um ihn später zu verwenden", z. B. für jede Push-Operation drei Blöcke konstanter Zeit, so dass Sie für jedes geschobene Element zwei zusätzliche Blöcke konstanter Zeit haben.

Answer 1

Ich stelle ein paar Vermutungen an:

1. Dass dies eine Hausaufgabe ist
2. dass dieser Absatz Teil des Auftrags ist

Dies wird mit drei Stapeln und konstantem zusätzlichem Speicher, so dass die amortisierte Zeit für jede Push-, Pop, oder Pull-Operation konstant ist. Die Stapel haben grundlegende Operationen, isEmpty, Push und Pop.

Dann wäre mein erster Rat, die Leute zu ignorieren, die mit Ihnen über verknüpfte Listen sprechen. Stimmt, so würde es jeder vernünftige Mensch umsetzen ohne das Erfordernis von drei Stapeln, Aber das Wichtigste bei Hausaufgaben ist nicht, dass man sie so macht, wie es ein vernünftiger Mensch tun würde, sondern wie es der Lehrer von einem verlangt.

Mein zweiter Ratschlag wäre, ein paar Blöcke, ein Kartenspiel oder einen Haufen Styroporbecher zu besorgen und drei Stapel zu bilden (z. B. mit Untersetzern oder so). Spielen Sie damit, was passiert, wenn Sie den Inhalt eines Stapels auf einen anderen übertragen, und Sie sollten eine Vorstellung davon bekommen.

Answer 2

Du könntest etwas machen, das nur die 3 Stapel verwendet. Denken Sie an Turm von Hanoi .

Answer 3

Verwenden Sie eine doppelt verkettete Liste und behalten Sie Verweise auf den Kopf und das Ende. Für den Rest müssen Sie zuerst Ihren eigenen Code schreiben und sich dann von uns helfen lassen, ihn zu korrigieren.

Answer 4

Beginnen Sie mit der Implementierung einer Warteschlange in Form von zwei Stapeln (ein ziemliches Standardproblem) und verallgemeinern Sie.