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.
