Lorenzo Alberton

At a glance

A sneak peak at some new SPL data structures (stack, heap, queue, list) introduced in PHP 5.3.

Print     Permalink

Latest articles

• Profiling PHP applications with XHProf: the path to scalability
• Speaking at the PHP Barcelona conference 2009
• New article: Graphs in the database, SQL meets social networks
• Create a video preview as animated GIF with FFmpeg and PHP SPL
• Trees in the database: It sure ain't no CouchDB!

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

Lorenzo Alberton

Lorenzo works as a Consultant / Software Engineer at Ibuildings, always busy with many cool clients. He's a long-time contributor to many open source projects.

Tags

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