Alle Artikel mit dem Schlagwort: Queues

PHP 5: Standard-Datenstrukturen nicht neu erfinden – Queues, Stacks und Co.

Problem Sie benötigen in Ihrem Programm Datenstrukturen, die PHP nicht out-of-the-box bietet (z.B. Stack, Linked-List oder Queue). Sie könnten diese  mithilfe von Arrays als eigene Klasse implementieren, sind sich aber nicht sicher, ob Sie dabei nicht unnötig das Rad neu erfinden. Lösung Seit PHP 5.3 bietet die Standard PHP Library (SPL) einige dieser Datenstrukturen an. Die Klasse SplStack implementiert eine LIFO-Datenstruktur (Last-In-First-Out) und somit eine Datenstruktur, die sich wie ein Stack (engl. für Stapel) verhält: $stack = new SplStack(); $stack->push(‘a’); $stack->push(‘b’); $stack->push(‘c’); echo $stack->pop().”\n”; echo $stack->pop().”\n”; echo $stack->pop().”\n”; c b a Die Klassen SplHeap, SplMinHeap und SplMaxHeap implementieren eine Heap-Datenstruktur.SplHeap ist dabei eine abstrakte Klasse und kann nicht direkt instantiiert werden. In einem Heap werden die einzelnen Elemente anhand ihrer Schlüsselwerte in einer Baumstruktur abgelegt. SplMinHeap und SplMaxHeap implementieren jeweils die von SplHeap als abstrakt deklarierte Funktion compare(). SplMinHeap legt die hinzugefügten Elemente in aufsteigend sortierter Reihenfolge ab, SplMaxHeap dagegen in absteigend sortierter Reihenfolge: $heap = new SplMaxHeap(); $heap->insert(‘b’); $heap->insert(‘a’); $heap->insert(‘c’); echo $heap->extract().”\n”; echo $heap->extract().”\n”; echo $heap->extract().”\n”; c b a $heap = new SplMinHeap(); $heap->insert(‘b’); …