• Increase font size
  • Default font size
  • Decrease font size

Statische Datenstrukturen

E-Mail Drucken PDF

Stack

Ein Stapel stellt eine einfach zu definierende Datenstruktur dar. Er ist nach dem LIFO (Last In - First Out) Prinzip organisiert. Die Vorstellung von einem Tellerstapel ist naheliegend. Ein Teller wird von oben vom Stapel entfernt (pop) und es kann ein Teller nur oben auf den Stapel gelegt werden (push). Daraus ergibt sich in Python eine mögliche Realisierung der Klasse Stack über eine Liste.

   01   class stack : 
   03   def __init__(self):  self.liste = [] 
06 def empty (self): return len (self.liste) == 0
   08   def push (self):  self.liste.insert (0,wert) 
   11   def pop (self): 
12 if self.liste == [] : return
13 else :
14 wert = self.liste [0]
15 del self.liste [0]
16 return wert
17
18 def top (self): return self.liste [0]

Eine alternative Implementierung ohne eingebaute Funktionen bzw. durch die Verwendung dynamischer Datenstrukturen ist möglich. Typische Anwendungen stellen Klammergebirge und Palindromtest dar.

 

Palindromtest

 

Queue

Auch eine Queue hat die Aufgabe Elemente zu verwalten. Dies geschieht allerdings gegenüber dem Stack entgegengesetzt. Das hier zugrundeliegende Prinzip ist das FIFO (First - In - First - Out) Prinzip. Vergleichbar ist die Datenstruktur mit einer Warteschlange. Auch hier sei eine Struktur dargestellt, die auf in Python eingebauten Funktionen beruht. Die Standard - Implemntierung für eine Queue stellt allerdings der zirkuläre Puffer dar, der über Indizes verwaltet wird. Durch den Modulo - Operator ist ein Einfügen (enqueue) ebenso möglich, wie ein Entfernen (dequeue) eines Elementes.

   01   class Queue :
   02   def __init__(self): self.liste = []
   03   def empty (self): return len (self.liste) == 0
   04   def enqueue (self,wert): self.liste.append (wert)
   05   def dequeue (self): del self.liste [0]
   06   def head (self): return self.liste [0]

Die Klasse Queue basiert auf einfachen eingebauten Funktionen. Alternative Implementierungen sind Gegenstand der Anwendung.

 

Aktualisiert ( Donnerstag, 09. April 2009 um 12:58 Uhr )  

(c) g-ymnasium.de 2006 - 2013 + Administrator