Backend Development

SPL Data Structures In PHP: The SplStack

SPL Data Structures In PHP_ The SplStack

In this article i will describe another SPL data structure type in php widely known which takes some features from the SplDoublyLinkedList which is the SplStack. 

 

 

 

We talked in a previous article about the SPLDoublyLinkedList. And mentioned that the SPLDoublyLinkedList combines the functionality of both the queue and the stack. In this article we will see how SplStack work.

The SplStack is in fact a doubly linked list with iteration mode LIFO (Last In First Out) in other means the last inserted element is the first element on retrieval. 

 

Class Terminology

class SplStack extends SplDoublyLinkedList implements Iterator, ArrayAccess, Countable {
/* Methods */
public __construct()
public setIteratorMode(int $mode): void
/* Inherited methods */
public SplDoublyLinkedList::add(int $index, mixed $value): void
public SplDoublyLinkedList::bottom(): mixed
public SplDoublyLinkedList::count(): int
public SplDoublyLinkedList::current(): mixed
public SplDoublyLinkedList::getIteratorMode(): int
public SplDoublyLinkedList::isEmpty(): bool
public SplDoublyLinkedList::key(): int
public SplDoublyLinkedList::next(): void
public SplDoublyLinkedList::offsetExists(int $index): bool
public SplDoublyLinkedList::offsetGet(int $index): mixed
public SplDoublyLinkedList::offsetSet(?int $index, mixed $value): void
public SplDoublyLinkedList::offsetUnset(int $index): void

.... 
....

}

As you see from the class terminology the SplStack extend from SplDoublyLinkedList. This class contains exactly some of the same methods of doubly linked list. The setIteratorMode() method modifies the iteration mode. There is only one mode you use which is:

SplDoublyLinkedList::IT_MODE_KEEP (Elements are traversed by the iterator)

 

Let’s see an example:

<?php

$sms = new SplStack();

$sms->push("new sms Message 1");
$sms->push("new sms Message 2");
$sms->push("new sms Message 3");


$sms->rewind();
while($sms->valid()) {
    
    echo $sms->current() . "\n<br/>";
    $sms->next();
}

// output
// new sms Message 3
// new sms Message 2
// new sms Message 1

As you see when iterated over the stack it retrieves the items in reversed order which is the LIFO order.

 

Adding items at specific index

You can add items in specific index using the add() method:

$sms->add(3, "new sms messages 4");

$sms->rewind();
while($sms->valid()) {
    
    echo $sms->current() . "\n<br/>";
    $sms->next();
}

If you specified an existing index, the previous values will be shuffled like so:

$sms->add(3, "new sms messages 5");
$sms->add(1, "new sms message 4");

$sms->rewind();
while($sms->valid()) {
    
    echo $sms->current() . "\n<br/>";
    $sms->next();
}

But if you tried to add an item in out of bounds index an exception will be thrown:

$sms->add(9, "new sms messages 9");

$sms->rewind();
while($sms->valid()) {
    
    echo $sms->current() . "\n<br/>";
    $sms->next();
}


// PHP Fatal error:  Uncaught OutOfRangeException: Offset invalid or out of range

 

Popping items of the stack

You can retrieve the last inserted node using the pop() method:

$sms = new SplStack();

$sms->push("new sms Message 1");
$sms->push("new sms Message 2");
$sms->push("new sms Message 3");


echo $sms->pop() . "<br/>\n"; 


// output
// new sms Message 3

If the data structure is empty any attempt to call pop() will throw RuntimeException. So whenever you invoke pop() make sure the stack is not empty with isEmpty() method:

if(!$sms->isEmpty()) {
   echo $sms->pop();
}

 

Real World Example: Undo Functionality

From the real world examples of stacks is the undo functionality of any software, as any task is pushed into a stack and whenever you undo an operation the stack is popped with the previous value.

So in this example i build a simple calculator class with four operations (addition, subtract, multiply, divide):

<?php

class Calculator
{
    private $operationStack;
    
    public function __construct(\SplStack $operationStack)
    {
        $this->operationStack = $operationStack;
    }
    
    function add($number1, $number2)
    {
        $result = $number1 + $number2;
        
        $this->operationStack->push(['op' => __METHOD__, 'params' => func_get_args(), 'result' => $result]);
        
        return $result;
    }
    
    function subtract($number1, $number2) 
    {
        $result = $number1 - $number2;
        
        $this->operationStack->push(['op' => __METHOD__, 'params' => func_get_args(), 'result' => $result]);
        
        return $result;
    }
    
    function multiply($number1, $number2) 
    {
        $result = $number1 * $number2;
        
        $this->operationStack->push(['op' => __METHOD__, 'params' => func_get_args(), 'result' => $result]);
        
        return $result;
    }
    
    function divide($number1, $number2) 
    {
        if($number2 == 0) {
            return;
        }
        
        $result = $number1 / $number2;
        
        $this->operationStack->push(['op' => __METHOD__, 'params' => func_get_args(), 'result' => $result]);
        
        return $result;
    }
    
    function undo()
    {
        if(!$this->operationStack->isEmpty()) {
            $lastOperation = $this->operationStack->pop();
            
            echo $lastOperation["op"] . " with parameters (" . implode(",", $lastOperation["params"]) . ") result: " . $lastOperation["result"] . "\n";
            return;
        }
        
        echo "no more operations to undo!\n";
    }
}

$calc = new Calculator(new \SplStack());

echo "Calculating: \n";

$result = $calc->add(2, 5);

echo $result . "\n";

$result = $calc->subtract($result, 3);

echo $result . "\n";

$result = $calc->multiply($result, 10);

echo $result . "\n";

$result = $calc->divide($result, 4);

echo $result . "\n";

echo "\n\n Undoing pervious operations: \n";

$calc->undo() . "\n";
$calc->undo() . "\n";
$calc->undo() . "\n";
$calc->undo() . "\n";
$calc->undo() . "\n";

The constructor accepts an instance of Splstack so that we can access the push() and pop() methods. The Calculator class contains four methods for doing the four mathematic operations and an additional method undo() which undo each previous operation.

In each method i am doing the required calculation between two numbers and then push into the stack an array containing the operation type and the function arguments and the result, if we take the add() method as an example:

function add($number1, $number2)
{
    $result = $number1 + $number2;
        
    $this->operationStack->push(['op' => __METHOD__, 'params' => func_get_args(), 'result' => $result]);
        
    return $result;
}

Then the undo function simply check if the stack is not empty using !$this->operationStack->isEmpty() method and then pop() the value like so:

if(!$this->operationStack->isEmpty()) {
    $lastOperation = $this->operationStack->pop();
            
    echo $lastOperation["op"] . " with parameters (" . implode(",", $lastOperation["params"]) . ") result: " . $lastOperation["result"] . "\n";
    return;
}

Now run the example in the command line, you will something like this output:

Calculating:
7
4
40
10


 Undoing pervious operations:
Calculator::divide with parameters (40,4) result: 10
Calculator::multiply with parameters (4,10) result: 40
Calculator::subtract with parameters (7,3) result: 4
Calculator::add with parameters (2,5) result: 7
no more operations to undo!

You can utilize this example to build a fully undo functionality in your project, and also you can combine this with some kind of javascript code and ajax.

 

0 0 votes
Article Rating

What's your reaction?

Excited
0
Happy
1
Not Sure
0
Confused
0

You may also like

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments