PHP 5.3 SPL data structures: SplStack, SplHeap, SplPriorityQueue, SplDoublyLinkedList

Following my recent experiments with the new SPL features in PHP 5.3, I saw that there are some new SPL data structures: heap, stack, queue and linked list. They aren't documented yet but I had a peek at the C sources.

SplStack

The first class, SplStack, is a standard implementation of a stack (duh!).

$stack = new SplStack();
 
$stack->push('b');
$stack->push('a');
$stack->push('c');
 
echo $stack->pop()."\n";
echo $stack->pop()."\n";
echo $stack->pop()."\n";
 
// OUTPUT:
// c
// a
// b

SplHeap

The second class is SplHeap, which is an abstract class and can't be instantiated directly. Two of its child classes are SplMinHeap (which sorts the data in descending order) and SplMaxHeap (which sorts the data in ascending order).

$heap = new SplMaxHeap();
$heap->insert('b');
$heap->insert('a');
$heap->insert('c');
 
echo $heap->extract()."\n";
echo $heap->extract()."\n";
echo $heap->extract()."\n";
 
// OUTPUT:
// c
// b
// a
$heap = new SplMinHeap();
$heap->insert('b');
$heap->insert('a');
$heap->insert('c');
 
echo $heap->extract()."\n";
echo $heap->extract()."\n";
echo $heap->extract()."\n";
 
// OUTPUT:
// a
// b
// c

Another SplHeap-derived class is SplPriorityQueue, which sorts the data by priority. With the setExtractFlags() method, you can choose what to extract:

  • EXTR_DATA (only the data)
  • EXTR_PRIORITY: only the priority value
  • EXTR_BOTH: both (array)

$pqueue = new SplPriorityQueue();
$pqueue->setExtractFlags(SplPriorityQueue::EXTR_DATA);
 
$pqueue->insert('low',    1);
$pqueue->insert('top',    3);
$pqueue->insert('medium', 2);
 
echo 'TOP ELEMENT: '.$pqueue->top()."\n";
echo $pqueue->extract()."\n";
echo $pqueue->extract()."\n";
echo $pqueue->extract()."\n";
 
// OUTPUT:
// TOP ELEMENT: top
// top
// medium
// low

SplDoublyLinkedList

$list = new SplDoublyLinkedList();
$list->push('a');
$list->push('b');
$list->push('c');
 
echo 'TOP: '.$list->top()."\n";
echo 'BOTTOM: '.$list->bottom()."\n";
 
// OUTPUT:
// TOP: c
// BOTTOM: a
 
echo "FIFO:\n";
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO);
for ($list->rewind(); $list->valid(); $list->next()) {
    echo $list->current()."\n";
}
 
// OUTPUT:
// FIFO:
// a
// b
// c
 
echo "LIFO:\n";
$list->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);
for ($list->rewind(); $list->valid(); $list->next()) {
    echo $list->current()."\n";
}
 
// OUTPUT:
// LIFO:
// c
// b
// a



2 responses to "PHP 5.3 SPL data structures: SplStack, SplHeap, SplPriorityQueue, SplDoublyLinkedList"

Hi.
It seems you know how to work with the \"new\" SPL classes. I\'m wondering if you could write an article with a solution to this one: http://stackoverflow.com/questions/2095680/, and make a blog entry out of it.
I\'ll keep an eye on your blog
Yours, Flavius

lorenzo,
cheers for the info. the SplPriorityQueue will definitely be used in a new project of mine.
Matt

Lorenzo Alberton

Lorenzo Alberton Lorenzo PHP5 ZCE - Zend Certified Engineer has been working with large enterprise UK companies for the past years and is now Chief Tech Architect at DataSift. He's an international conference speaker and a long-time contributor to many open source projects. Lorenzo Alberton's profile on LinkedIN View Lorenzo Alberton's Twitter stream

Lorenzo Alberton - Sun Certified MySQL 5 Developer

Tags

AJAX, Apache, Book Review, Charset, Cheat Sheet, Data structures, Database, Firebird SQL, Hadoop, Imagick, INFORMATION_SCHEMA, JavaScript, Kafka, Linux, Message Queues, mod_rewrite, Monitoring, MySQL, NoSQL, Oracle, PDO, PEAR, Performance, PHP, PostgreSQL, Profiling, Scalability, Security, SPL, SQL Server, SQLite, Testing, Tutorial, TYPO3, Windows, Zend Framework

Buy me a book - Introduction To Information Retrieval