Stack

Aus ProgrammingWiki

Der Stack (Stapel) wurde als abstrakter Datentyp charakterisiert. Hier werden nun verschiedene konkrete Datenstrukturen zur Implementation dieses ADT verwendet. Anschließend wird ein so implementierter Stack zur Umkehrung einer Liste natürlicher Zahlen verwendet und eine Effizienzbetrachtung angeschlossen.

Das in Python eingebaute Listen-`reverse` verwendet ein dynamisches Array. Es wird zu Beginn so groß dimensioniert, dass es für viele Anwendungsfälle ausreicht. Selbst wenn für `push` und `pop` jeweils ein konstanter Aufwand erforderlich ist, wird dieser durch die Schleife (Listenumkehr) "aufgefressen". Wie bei den anderen Implementierungen liegt der Aufwand zur Umkehrung einer Zahlenfolge in $\mathcal{O}(n)$, allerdings mit einem deutlich kleineren Faktor als bei den anderen konkreten Datentypen (Gerade mit geringerem Anstieg).

## Implementation mit Python-Liste # (veränderlich, unbeschränkt, Zugriff über Index und am Ende) # Variante 1: append()/push(i) und pop(i): beide in O(1) class Stack1: def __init__(self): self.items = [] def isEmpty(self): return self.items == [] def push(self, item): self.items.append(item) def pop(self): tos = self.items[len(self.items)-1] self.items.pop() return tos def size(self): return len(self.items)

# Variante 2: insert(i)/push(i) und pop(i): beide in O(n), wobei n = Stack-size # ineffizienter als Variante 1 class Stack2: def __init__(self): self.items = [] self.topIndex = 0 self.maxIndex = 400000 def isEmpty(self): return self.topIndex <= 0 def push(self, item): if self.topIndex <= self.maxIndex: self.items.insert(self.topIndex, item) self.topIndex = self.topIndex+1 else: print("Stapel voll.") def pop(self): self.topIndex = self.topIndex-1 tos = self.items[self.topIndex] self.items.pop(self.topIndex) # in O(n) return tos def size(self): return self.topIndex def __str__(self): return "[" + (", ".join(map(str, self.items))) + "]"

## Anwendung st2 = Stack2() st2.isEmpty() st2.push(727) st2.push(13) st2.push(123) st2.push(727) st2.push(123) print(st2)

ausführen

### Variante 3: Stack-Impl. mittels einfach verketteter Liste ## Einfach verkettete Liste (singly linked list) # Elemente der Liste sind Knoten (node), # die einen Daten- und einen Referenzteil enthalten class Node: """linked list""" def __init__(self, data): self.data = data self.next = None def getData(self): return self.data def setData(self, somedata): self.data = somedata def getNext(self): return self.next def setNext(self, somenext): self.next = somenext ## first = Node(1) ## second = Node(2) ## first.next = second ## first.next.data ## first.getNext().getData() class SinglyLinkedList: def __init__(self): self.head = None def isEmpty(self): return self.head == None def traverse(self): def traversal(curNode): if curNode is None: print() else: print(curNode.getData()) traversal(curNode.getNext()) traversal(self.head) def prepend(self, item): temp = Node(item) temp.setNext(self.head) self.head = temp def append(self, item): curNode = self.head while curNode.getNext() is not None: curNode = curNode.getNext() temp = Node(item) curNode.setNext(temp) def removeHead(self): self.head = self.head.getNext() # Stack3 verwendet den ADT "SinglyLinkedList" class Stack3: def __init__(self): self.items = SinglyLinkedList() def isEmpty(self): return self.items.isEmpty() def push(self, item): self.items.prepend(item) def pop(self): tos = self.items.head.getData() # Durchgriff auf ADT "Node" self.items.removeHead() return tos def size(self): print('Sag ich nicht.')

### GLEICHER Algorithmus über VERSCHIEDENEN konkreten Datentypen ## Anwendung mit Stack: Invertieren einer Liste # Beispiel: myreverse([1, 2, [3, 4], 5]) = [5, [3, 4], 2, 1] # from stack import Stack1, Stack2, Stack3 import timeit import random import matplotlib.pyplot as plt def myreverse(ls): s = Stack1() # Datenstruktur hier ändern (EINZIGER Eingriff) !!!!!!!!!!!!!!!!!!!!! result = [] # Liste for item in ls: s.push(item) while not(s.isEmpty()): result.append(s.pop()) return result ## ls = [i for i in range(10)] ## print(ls) ## print(myreverse(ls)) ## Effizienzanalyse def analyze(fn, maxi=10000, step=500): '''Funktion zur Ermittlung der Laufzeiten T(n) in Abhängigkeit von der Problemgröße n''' tx = [] ty = [] global n # Damit es im Timer verwendet werden kann for n in range(1, maxi, step): # Wortlängen n (Problemgröße) tt = [] for i in range(10): # Anzahl k der Instanzen für jedes n v = fn + '(ls)' t = timeit.Timer(v, 'gc.enable(); \ from __main__ import ' + fn + ', myreverse, n; \ ls = [i for i in range(n)]') # wie eval tt = tt + [t.timeit(number=1)] tt.reverse() # sort(), falls best case gesucht tx.append(n) ty.append(tt[0]) # ist das Maximum der Zeitenliste return tx, ty plt.figure('Umkehr einer Listen') result = analyze('myreverse') plt.plot(result[0], result[1], 'bo', label='myreverse') plt.legend(loc='upper left') plt.show() # -------------------------------------------------------------------------------- # # Ergebnisse: # # Alle drei in O(n), n ... Anzahl der Listenelemente # Ursache: Die Schleifen arbeiten mit O(n) und verschlingen den O(1)-Vorteil. # # Da push() und pop() von Stack1 in O(1) ist der Anstieg der Geraden geringer. # # Die Stack-Impl. 3 mit einfach verketteten Listen ist die ineffizienteste. # # -------------------------------------------------------------------------------- ### Alternative: Verwendung eines anderen Datentyps: (Python-) Liste def myreverse(ls): ls.reverse() return ls ## plt.figure('Umkehr einer Liste') ## result = analyze('myreverse',30000) ## plt.plot(result[0], result[1], 'bo', label='myreverse') ## plt.legend(loc='upper left') ## plt.show() # ------------------------------------------------------------------------------- # # Ergebnis: # # Liegt ebenfalls in O(n), n ... Anzahl der Listenelemente # Ist wesentlich schneller (Geradenanstieg geringer) als bei Wahl von Stack 1, 2, 3. # # Die Python-Impl. verwendet ein ARRAY (aus C) und dimensioniert es so groß, # dass es für viele Anwendungen ausreicht. Falls es voll ist, wird ein neues # (wiederum over-allocated) ARRAY bereitgestellt und der Inhalt das alten # dorhin KOPIERT. ---> Amorisierte Effizienz ist sehr gut. # Deshalb gibt es in der Aufwandsgrafik immer wieder "Ausreißer". # # --------------------------------------------------------------------------------