My Blog
My Blog


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


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();


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

    if (function_exists($event)) {


function function1(SplQueue $eventHandler)
    print "Function 1 called. " .
        "Adding function3() to the event handler\n";
    $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


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


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

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);
        case "subtract" :
            $stack->push($value1 - $value2);
        case "multiply" :
            $stack->push($value1 * $value2);
        case "divide" :
            $stack->push($value1 / $value2);

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


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


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


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


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


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


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->setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO | SplDoublyLinkedList::IT_MODE_DELETE);


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


Result will be

  private 'flags' => int 3
  private 'dllist' => 
    array (size=5)
      0 => int 1
      1 => int 2
      2 => int 3
      3 => int 4
      4 => int 5


  private 'flags' => int 3
  private 'dllist' => 
    array (size=0)


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



Sierpinski Triangle and Sierpinski Carpet

Sierpinski Triangle

Another fractal that exhibits the property of self-similarity is the Sierpinski triangle. An example is shown in below picture . The Sierpinski triangle illustrates a three-way recursive algorithm. The procedure for drawing a Sierpinski triangle by hand is simple. Start with a single large triangle. Divide this large triangle into four new triangles by connecting the midpoint of each side. Ignoring the middle triangle that you just created, apply the same procedure to each of the three corner triangles. Each time you create a new set of triangles, you recursively apply this procedure to the three smaller corner triangles. You can continue to apply this procedure indefinitely if you have a sharp enough pencil. Before you continue reading, you may want to try drawing the Sierpinski triangle yourself, using the method described.

When you change the depth shape will change like below


function drawLine(ctx, top_point, left_point, right_point) {

    ctx.fillStyle = "red";

    ctx.moveTo(top_point.x, top_point.y);
    ctx.lineTo(left_point.x, left_point.y);
    ctx.lineTo(right_point.x, right_point.y);
function sierpinksiTriangle(level, ctx, top_point, left_point, right_point) {

    if (level === 0) {

        drawLine(ctx, top_point, left_point, right_point);

    } else {

        var leftMid = {};
        var rightMid = {};
        var bottomMid = {};

        leftMid.x = (top_point.x + left_point.x) / 2;
        leftMid.y = (top_point.y + left_point.y) / 2;

        rightMid.x = (top_point.x + right_point.x) / 2;
        rightMid.y = (top_point.y + right_point.y) / 2;

        bottomMid.x = (left_point.x + right_point.x) / 2;
        bottomMid.y = (left_point.y + right_point.y) / 2;

        sierpinksiTriangle(level - 1, ctx, top_point, leftMid, rightMid);
        sierpinksiTriangle(level - 1, ctx, rightMid, right_point, bottomMid);
        sierpinksiTriangle(level - 1, ctx, leftMid, left_point, bottomMid);



Now invoke the Function

var c = document.getElementById("canvas");
var ctx = c.getContext("2d");
var topPoint = {};
var leftPoint = {};
var rightPoint = {};
var depth = 6;

topPoint.x = 200;
topPoint.y = 10;

leftPoint.x = 10;
leftPoint.y = 200;

rightPoint.x = 400;
rightPoint.y = 200;

sierpinksiTriangle(depth, ctx, topPoint, leftPoint, rightPoint);

Sierpinski carpet

The Sierpinski carpet is the fractal illustrated below which may be constructed analogously to the Sierpinski sieve, but using squares instead of triangles.



function drawRect(ctx, x, y, width, height) {
    ctx.fillStyle = "red";
    ctx.fillRect(x, y, width, height);
function sCarpet(level, ctx, x, y, width, height) {
    if (level === 0) {
        drawRect(ctx, x, y, width, height);
    } else {

        width = width / 3;
        height = height / 3;

        sCarpet(level - 1, ctx, x, y, width, height);
        sCarpet(level - 1, ctx, x + width, y, width, height);
        sCarpet(level - 1, ctx, x + width * 2, y, width, height);

        sCarpet(level - 1, ctx, x, y + height, width, height);
        sCarpet(level - 1, ctx, x, y + height * 2, width, height);

        sCarpet(level - 1, ctx, x + width, y + height * 2, width, height);

        sCarpet(level - 1, ctx, x + width * 2, y + height, width, height);
        sCarpet(level - 1, ctx, x + width * 2, y + height * 2, width, height);


Now invoke the function

var c = document.getElementById("canvas2");
var ctx = c.getContext("2d");
var height = 500;
var width = 500;
var x = 0;
var y = 0;
var depth = 3;
sCarpet(depth, ctx, x, y, width, height);

Change the depth to see different shapes  through iteration

Koch Curve

The Koch Snowflake was created by the Swedish mathematician Niels Fabian Helge von Koch. he used the Koch Snowflake to show that it is possible to have figures that are continuous everywhere but differentiable nowhere.

The Koch Curve

In order to create the Koch Snowflake, von Koch began with the development of the Koch Curve. The Koch Curve starts with a straight line that is divided up into three equal parts. Using the middle segment as a base, an equilateral triangle is created. Finally, the base of the triangle is removed, leaving us with the first iteration of the Koch Curve.


And Lets Implement with JavaScript and canvas

function drawLine(ctx, x1, y1, x2, y2, color) {

    ctx.fillStyle = "#000";
    ctx.strokeStyle = color;
    ctx.moveTo(x1, y1);
    ctx.lineTo(x2, y2);
    ctx.lineWidth = 1;


function kochCurve(level, ctx, x1, y1, lenght, angle, color) {

    if (level === 0) {

        var x2 = x1 + lenght * Math.cos(angle);
        var y2 = y1 + lenght * Math.sin(angle);
        drawLine(ctx, x1, y1, x2, y2, color);

    } else {

        var x2 = x1 + lenght / 3 * Math.cos(angle);
        var y2 = y1 + lenght / 3 * Math.sin(angle);

        var theta1 = angle - Math.PI / 3;
        var theta2 = angle + Math.PI / 3;

        var x3 = x2 + lenght / 3 * Math.cos(theta1);
        var y3 = y2 + lenght / 3 * Math.sin(theta1);

        var x4 = x1 + lenght * 2 / 3 * Math.cos(angle);
        var y4 = y1 + lenght * 2 / 3 * Math.sin(angle);

        kochCurve(level - 1, ctx, x1, y1, lenght / 3, angle, 'red');
        kochCurve(level - 1, ctx, x2, y2, lenght / 3, theta1, 'blue');
        kochCurve(level - 1, ctx, x3, y3, lenght / 3, theta2, 'yellow');
        kochCurve(level - 1, ctx, x4, y4, lenght / 3, angle, 'brown');



Invoke kochCurve function


var c = document.getElementById("canvas");
var ctx = c.getContext("2d");
var x1 = 20; 
var y1 = 200;
var length = 300;
var angle = 0;
var depth = 3;

kochCurve(depth, ctx, x1, y1, length, angle, 'black');

When you Invoke with different depth you will see one of the below shape

The Koch Snowflake

From the Koch Curve, comes the Koch Snowflake. Instead of one line, the snowflake begins with an equilateral triangle. The steps in creating the Koch Curve are then repeatedly applied to each side of the equilateral triangle, creating a “snowflake” shape.

To Implement Just  write kochCurve  function two time with 60 degree angle

var c = document.getElementById("canvas");
var ctx = c.getContext("2d");
var x1 = 20;
var y1 = 200;
var length = 300;
var angle = 0;
var depth = 3;

var x2 = x1 + length;

var x3 = x1 + length * Math.cos(Math.PI / 3);
var y3 = y1 + length * Math.sin(Math.PI / 3);

kochCurve(depth, ctx, x1, y1, length, angle, 'black');
kochCurve(depth, ctx, x2, y1, length, Math.PI * 2 / 3, 'black');
kochCurve(depth, ctx, x3, y3, length, -Math.PI * 2 / 3, 'black');when

When you Invoke with different depth you will see one of the below shape




Implementing Quick sort

Quick sort is divide and conquer method. although it does not divide in to two equal part like merge sort it divide int to dynamic partition to sort data

  1. Pick random value from the array which will call Pivot
  2. Reorder the array so that the item smaller than pivot it goes on left of it ,and  the item greater than  or equal to pivot it go to right of it , this is know as a partitioning
  3. Recursively call step 1 and 2 until list sorted

There many ways to picking up pivot from the array. either we choose left most item or right most item form array. in both way  If array is already sorted it will take worst case complexity . choosing a good pivot can improve the efficiency of the algorithm


we used the first item as a pivot . we can choose last item or median. lets Implement on PHP

function quickSort($array)
    $count = count($array);

    if ($count <= 1)
        return $array;

    $pivot = $array[0];
    $left = $right = array();

    for ($i = 1; $i < $count; $i++) {

        if ($array[$i] > $pivot) {
            $right[] = $array[$i];
        } else if ($array[$i] < $pivot) {
            $left[] = $array[$i];

    return array_merge(quickSort($left), 

The worst case complexity causes with selection of pivot , here is the complexity

Worst case  O(n2)

Average case  O(nlog(n))

Best case O(nlog(n))

Sapce Complexity (worst case) O(log(n))