My Blog
My Blog

splQueue

Queue is data structure it allow to add element First in First out. adding data at the back and reading data from front . in PHP queue can bee seen as standard DoublyLinkedList it  extend SplDoublyLinkedList  Inherit all methods from SplDoublyLinkedList. SplQueue have an two extra two methods which are enqueue() and dequeue() these methods alias for push() and  shift()

SplQueue come with default iterative mode of IT_MODE_FIFO | IT_MODE_KEEP. you able to change to IT_MODE_DELETE but can’t change to IT_MODE_LIFO

USAGE

use SplQueue when you need to store data and fetch data in the same order. Below example creates an event handler where you can hook your own functions

$eventHandler = new SplQueue();

$eventHandler->enqueue("function1");
$eventHandler->enqueue("function2");

while (!$eventHandler->isEmpty()) {
    $event = (string)$eventHandler->dequeue();

    if (function_exists($event)) {

        $event($eventHandler);
    }
}

function function1(SplQueue $eventHandler)
{
    print "Function 1 called. " .
        "Adding function3() to the event handler\n";
    $eventHandler->enqueue("function3");
    $eventHandler->enqueue("a message for function 3");
}

function function2(SplQueue $eventHandler)
{
    print "Function 2 called.\n";
}

function function3(SplQueue $eventHandler)
{
    $msg = $eventHandler->dequeue();
    print "Function 3 called. Message: $msg\n";
}

The SplStack class

Stack is the data structure let you add and remove item Last in  First out order. You can push item on the top and also pop item on the top

PHP SplSatck  is just a inked list , where it can be seen as vertical list, where elements are stack upon each other. SplStack Extends SplDoublyLinkedList and Inherit all methods inside the SplStack . Only different between SplStack and SplDoublyLinkedList you can’t set IT_MODE_FIFO in SplStack::setIteratorMode It will throw RuntimeException

USAGE

use an SplStack where you want to store data and only deal with last element you have stored. it mostly useful for recursive functionality where store all data and deal with them until stack is empty.

Creates calculator with SplStack, Creates Stack and where we push two operators and operations. it only pops the two operators and operation from stack. does the calculation and push in to stack . this process continue until only one item present in stack

$stack = new SplStack();

// This will calculate: (((3 * 4) + 4) - 2) / 2) = 7
$stack->push("divide");
$stack->push(2);
$stack->push("subtract");
$stack->push(2);
$stack->push("add");
$stack->push(4);
$stack->push("multiply");
$stack->push(3);
$stack->push(4);

calculate($stack);

print "The result: " . $stack->pop() . PHP_EOL;
exit;

function calculate(SplStack $stack)
{
    $value1 = $stack->pop();
    $value2 = $stack->pop();
    $cmd = $stack->pop();
   
    // Execute command and push the result back onto the stack
    switch ($cmd) {
        case "add" :
            $stack->push($value1 + $value2);
            break;
        case "subtract" :
            $stack->push($value1 - $value2);
            break;
        case "multiply" :
            $stack->push($value1 * $value2);
            break;
        case "divide" :
            $stack->push($value1 / $value2);
            break;
    }

    // If we still have multiple entries on the stack,
    // so calculate again
    if ($stack->count() > 1) {
        calculate($stack);
    }
}

SplDoublyLinkedList

Before We talk about doubly linked list lets we talk about inked list. Linked list is data structure where elements are linked together. every element in the list has a at least two properties which are property is store actual data and property store pointer to the next element  in the linked list

First element in the Linked list its called Head ,  when we need find the element, we want to start to from head, if isn’t one we need we use the pointer to go next element, we continue process until the pointer of the element does not point to an element this element call tail

When creating Linked list usually, both head and tail elements are store as a meta-data for quicker access

Adding and Deleting Elements

Inserting new element is changing the pointer of the previous element let it point to the new element and pointer of the new element point to the next element

Deleting element if we want to delete element  N we want to find N-1 because  point to pointer of N-1 to N+1 and Skip N. there for delete must look up N-1 element searching through list from head element. to overcome this problem most of the linked list have an deleteAfter method where you do not point to the element you need to delete,  but to the element before that.

Sequential reads are very fast. just we can read Head element and we move until we reach the tail element. we don’t need any special method, like we needed to reach hash table sequentially , However random reads on linkedlist is so slow, because if we want to read from 6th element first we fetch head element and we have to move up to 5th element before we have found the 6th element. so it takes O(n) complexity to random read.but sequentially read takes O(1) complexity

DOUBLE-LINKED LISTS

This Nothing more than adding one more pointer to the each element to point to previous element.  this mean we can either move forward or backward. which is speedup more things

Deletion is much easier. Since we know we want to delete element N , Just move backward to find N-1 (previous ) and move forward to find N+1 (next) element. Delete operation O(1) complexity

Random reads would still not easy but, sequential read from back to front are made easy

ADVANTAGES OF USING LINKED LISTS

One of the property of linked that they don’t have an fixed size. LinkedList can be empty or can have thousand elements, no need to memory allocation in advance like hashtable . Linked list more memory efficient data structure delete and insert are very fast and also merge ,  just connect to the tail of linked list 1 and head of the Linked list 2

COUNTING ELEMENTS

Even thought lot of operation can be done with O(1) , But random reads and count take O(n) complexity, if you want to count we want to iterate through from head to tail. Because counting is such a common thing ,PHP has added meta-information inside the linked list , such as number of elements is stored in linkedlist, the counting the element in the linked list (SplDoublyLinkedList::count() ) is O(1), but merely cheating

USAGE

SplDoublyLinkedList is a perfect way to save memory. while still being to use more array functionality. main purpose of it iterate over through the elements sequential way either backward or forward. Don’t use this data structure you have planned to do  mostly random reads

NOTABLE METHODS

void SetIteratorMode(int $mode)

The setIteratorMode defines how behave when iterate through the list. following constant can be set.

IT_MODE_LIFO:   The elements are read Last in First out. in other word read backward

IT_MODE_FIFO:  The elements are read First in First out. Read forward like normal iterator. this option is default

IT_MODE_KEEP : Elements are kept when iteration. this option is default

IT_MODE_DELETE: Elements are automatically deleted when iterating

If  you want to use last in first out and delete when iterate you want to set IT_MODE_LIFO | IT_MODE_DELETE. default is IT_MODE_FIFO | IT_MODE_KEEP

$splDL = new SplDoublyLinkedList();

$splDL->push(1);
$splDL->push(2);
$splDL->push(3);
$splDL->push(4);
$splDL->push(5);

$splDL->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_DELETE);

var_dump($splDL);

foreach ($splDL as $value) {
    echo "$value </br>";
}
var_dump($splDL);

 

Result will be

C:\wamp64\www\spl\index.php:13:
object(SplDoublyLinkedList)[1]
  private 'flags' => int 3
  private 'dllist' => 
    array (size=5)
      0 => int 1
      1 => int 2
      2 => int 3
      3 => int 4
      4 => int 5


5 
4 
3 
2 
1 


C:\wamp64\www\spl\index.php:18:
object(SplDoublyLinkedList)[1]
  private 'flags' => int 3
  private 'dllist' => 
    array (size=0)
      empty

 

mixed bottom(void)

This will return the first (head ) element of the list

mixed top (void)

This will return last(Tail) element of the list

void unshift(mixed $value)

It will be added the value top (Head) of the list. this is different from push(), where it will be added end(Tail) of the list

mixed shift(void)

shift() does opposite of unshift() it will remove an element head of the list