Dynamische Variante eines Stacks

Question

Aufgabe:

Implementieren Sie die dynamische Variante eines Stacks/Kellers für ganze Zahlen. Dynamisch heißt in diesem Fall, dass der Stack beliebig viele Elemente speichern kann. Die Implementierung soll die folgenden Operationen unterstützen:

Push (x) - speichert ein neues Element mit Wert x auf dem Stack

Pop () - entfernt das oberste Element des Stacks und gibt seinen Wert aus

Top () - gibt den Wert des obersten Elements aus

Size () - gibt aus, wie viele Elemente sich im Stack befinden

Der Stack soll mithilfe eines Feldes und eines Stackpointers t implementiert werden, der auf die oberste (bzw. letzte) belegte Zelle zeigt. Läuft das Feld über, dann soll es durch ein doppelt so großes Feld ersetzt werden; sinkt der Pegel des Stacks wieder, dann soll das Feld sinnvoll verkleinert werden. (Bspw. so, dass nach einer pop-Operation nicht mehr als ein Drittel des Felds leer ist.)

Analysieren Sie die Laufzeiten ihrer Methoden.

Hinweis: Wir verwenden Pseudo-Code.

Comments

... Stackpointers t implementiert werden, der auf die oberste (bzw. letzte) belegte Zelle zeigt.

Diese Anforderung zeugt mal wieder davon, dass die Dozenten, die sich solche Aufgaben ausdenken, selbst keine Programmierpraxis haben!

Answer 1

Antwort mit KI erzeugt

Dynamische Variante eines Stacks Implementierung

Die Implementierung eines dynamischen Stacks erfordert eine interne Datenstruktur, die wachsen und schrumpfen kann. Ein Array bietet eine geeignete Basis, muss aber dynamisch gehandhabt werden, um die Größe nach Bedarf anzupassen. Wir nutzen einen Index (Stackpointer t), um auf das oberste Element zu zeigen. Dieser Iterator hat initial den Wert -1, da der Stack zu Beginn leer ist. Hier folgt ein Entwurf der dynamischen Stack-Implementierung mit unterstützten Operationen:

python
class DynamicStack:
    def __init__(self):
        self.capacity = 2  # Startkapazität des Stacks
        self.stack = [None] * self.capacity
        self.t = -1  # Stackpointer
    
    def push(self, x):
        if self.t + 1 == self.capacity:
            self.resize(self.capacity * 2)  # Verdoppelung der Kapazität
        self.t += 1
        self.stack[self.t] = x
    
    def pop(self):
        if self.t < 0:
            raise Exception("StackUnderflow")
        value = self.stack[self.t]
        self.stack[self.t] = None  # Entfernen des Elements
        self.t -= 1
        if self.capacity > 2 and (self.t + 1) <= self.capacity // 4:
            self.resize(self.capacity // 2)  # Halbierung der Kapazität, wenn angemessen
        return value
    
    def top(self):
        if self.t < 0:
            raise Exception("EmptyStack")
        return self.stack[self.t]
    
    def size(self):
        return self.t + 1
    
    def resize(self, new_capacity):
        new_stack = [None] * new_capacity
        for i in range(self.t + 1):
            new_stack[i] = self.stack[i]
        self.stack = new_stack
        self.capacity = new_capacity

Laufzeitanalyse

- push(x): Diese Methode hat im Durchschnitt eine Laufzeit von \(O(1)\). Im schlimmsten Fall, wenn das Array vergrößert werden muss, ist die Laufzeit \(O(n)\), wobei \(n\) die Anzahl der Elemente im Stack ist. Da das Array jedoch mit jedem Vergrößern doppelt so groß wird, verteil sich der Vergrößerungsaufwand über viele push-Operationen, sodass die amortisierte Laufzeit ebenfalls \(O(1)\) beträgt.
- pop(): Ähnlich wie bei push kann das Reduzieren der Array-Größe einen \(O(n)\) Aufwand erfordern, jedoch nur selten. Das macht die amortisierte Laufzeit wiederum zu \(O(1)\).
- top(): Diese Methode hat eine konstante Laufzeit \(O(1)\), da sie direkt auf das oberste Element zugreift, ohne die Struktur zu verändern.
- size(): Diese Methode hat ebenfalls eine konstante Laufzeit \(O(1)\), da sie nur den Stackpointer t ausliest.

Die dynamische Natur des Stacks ermöglicht es, effizient mit Speicherplatz umzugehen, indem die Kapazität des internen Arrays nach Bedarf angepasst wird. Dadurch bleibt die Effizienz der Stack-Operationen auch bei einer großen Anzahl von Elementen gewährleistet.