Data Structures in PHP

Đã đăng vào - Cập Nhật Lần Cuối vào

Like any other general-purpose programming language, PHP also offers data structures for developers that can be used in the implementation of business logic. These data structures are implemented in the Standard PHP Library (SPL), which has been a part of standard PHP since version 5.3.0.

Arrays

Arrays are the simplest and most powerful data structures in PHP. The arrays in PHP are not the same concept as arrays in C++ or Java or C#. The arrays in PHP are associative arrays, having key/value pairs. Arrays can be created using the array() language construct.

$array1 = array('name' => 'John Doe',
		    'age' => 13,
		    'address' => 'California, Palo Alto',
		    'website' => 'http://johndoe.com' );
$array2 = array(0 => 2 , 
		    1 => 3 ,
		    2 => 5 ,
		    3 => 7 ,
		    4 => 11 );

Items in an array can be accessed using the index [] operator. The index can be an integer or a string, depending on the items stored in an array. For example the below code would print 5:

print($array2[2]);

There are some constraints on what type of data can be used as a key in the arrays. The keys can be strings, integers (float numbers will be also converted to integers by truncating the fractional part). Other arrays and objects cannot be used as keys.

List based data structures

In SPL, there are three list-based data structures: SplDoublyLinkedList, SplQueue and SplStack. The SplDoublyLinkedList, as its name suggests, is an implementation of the double linked list. Adding and removing items from a double linked list is a cheap operation with a O(1) complexity.

The code creates a new double-linked list and prints out how many items are in the list (it will print $dll has 3 items in it.).

$dll = new SplDoublyLinkedList();
$dll->push("hello");
$dll->push("world");
$dll->push("!");
print("\$dll has ".$dll->count()." items in it.");

These collection types can be used in for statements too:

for ($dll->rewind(); $dll->valid(); $dll->next()) {
    echo $dll->current()." ";
}

The above code will print: hello world !

The SplQueue reuses the implementation of the SplDoublyLinkedList. In addition, it provides the enqueue and dequeue methods.

$q1 = new SplQueue();
$q1->enqueue("San Francisco");
$q1->enqueue("Montreal");
$q1->enqueue("Barcelona");
$q1->enqueue("New York");

print($q1->dequeue()." | ");
print($q1->dequeue()." | ");
print($q1->dequeue());

The code creates a new instance of the SplQueue class, enqueues four cities (San Francisco, Montreal, Barcelona, New York), and prints out the returned value of dequeue() method. The result will be: San Francisco | Montreal | Barcelona.

SplStack should be used with the pop, push and top methods, and is a child implementation of SplDoublyLinkedList. All three methods are implemented in SplDoublyLinkedList.

$st1 = new SplStack();
$st1->push("San Francisco");
$st1->push("Montreal");
$st1->push("Barcelona");
$st1->push("New York");

print($st1->pop()." | ");
print($st1->pop()." | ");
print($st1->pop());

Since this is a stack, which is a LIFO type data structure, the output will be: New York | Barcelona | Montreal.

Heap-based data structures

Heap is a tree-like data structure that can be max and min heap. In the case of a max heap, the root of the tree holds the biggest value in the tree, and each parent node has to have a bigger or equal value then their children. For min heaps, the requirement is vice versa.

The SplHeap is an abstract class (meaning you will have to derive from it, in case you want to use its implementation). Actual implementations are SplMaxHeap and SplMinHeap.

$heap = new SplMaxHeap();
$heap->insert(array ('Prague' => 45));
$heap->insert(array ('Budapest' => 25));
$heap->insert(array ('London' => 90));
$heap->insert(array ('Tokyo' => 420));
$heap->insert(array ('New York' => 140));


while ($heap->valid()) {
  list ($city, $population) = each ($heap->current());
  print($city . ':' . $population);
  print("<br/>");
  $heap->next();
}

The output will be:

Prague:45
New York:140
Tokyo:420
London:90
Budapest:25

In many cases, simple arrays do the job when implementing new functionality or adding extra business logic to the web application. For cases with particular needs, knowing about these standard library data structures can be an advantage.

Đã đăng 23 tháng 3, 2015

Greg Bogdan

Software Engineer, Blogger, Tech Enthusiast

I am a Software Engineer with over 7 years of experience in different domains(ERP, Financial Products and Alerting Systems). My main expertise is .NET, Java, Python and JavaScript. I like technical writing and have good experience in creating tutorials and how to technical articles. I am passionate about technology and I love what I do and I always intend to 100% fulfill the project which I am ...

Bài báo kế tiếp

CSS3 Media Queries