Serverless, ReactPHP, and Expanding Frontiers, May 2019

30 \ May 2019 \ http://www.phparch.com

Education Station

Data Structures, Part One

any values. We have to manually push() things into the queue.
The second is SplQueue does not remove the items like array_
shift() does. Why?
SplQueue (and other things based off of SplDoublyLinkedList,
another data structure) can run in a variety of modes. While
SqlQueue is locked into a FIFO mode, we can tell it to keep or
destroy the values as it iterates by using the setIteratorMode()
method on the object as you can see in Listing 5.
I don’t like that SplQueue defaults to keeping values, although
it does make them behave more like a traditional array. You
can also see that the count() does not drop to 0 until the loop
actually exits. Iterators generally don’t remove items until the
loop fully completes.

LIFO: Last In, First Out
So FIFO is great until you need LIFO, or “Last In, First Out.”
This acronym means that the newest value added to the queue
is retrieved first. I generally do not use this, but LIFO is useful
for recursion, or for dealing with undo/redo states. I find their
use much less general than FIFO, but under the right condi-
tions, a LIFO stack can be useful.
It is normally called a stack. With a stack, you add values to
the top of the list, and then retrieve those items from the top
down. Think of a stack of plates—as you stack the plates, you
stack them bottom to top. When you need a plate, you take a
plate from the top, and the top plate is the last plate you added
to the stack.
With an array, we can use array_pop() to “pop” the value
off the end of the array, and we can use array_push() to add
things to the array. These functions simulate a stack (see
Listing 6).
Since 4 is the value at the end of the array, it’s the first value
returned. 1 is the last value returned because it is the first value
added. Conceptually, this should be pretty easy to follow, but
most likely you will not use this as much as a FIFO queue.

As with SplQueue, PHP does come with a SplStack to

simulate a proper LIFO structure (Listing 7). Since a stack is

“top-down,” you can not iterate over it in a traditional foreach

loop like a queue. This is because, semantically, you are going

in reverse down a stack.

The big difference here is that the $stack->rewind() line.

This method resets the pointer for the iterator that SplStack

uses internally so you can iterate over it. Once you rewind

the stack, you can iterate over it like normal. Keep in mind

that like SplQueue, by default values are not removed from the

stack. You need to manually set that iterator mode if you want

it to delete the values as it iterates.

Listing 5

1. $queue = new \SplQueue();


2. $queue->setIteratorMode(


3. \SplDoublyLinkedList::IT_MODE_DELETE


4. );


5. $queue->push( 1 );


6. $queue->push( 2 );


7. $queue->push( 3 );


8. foreach ($queue as $value) {


9. echo PHP_EOL. "Value: ". $value;


10. echo "Count: ". count($queue);


11. }


12. echo PHP_EOL. "Count: ". count($queue). PHP_EOL;


13. // Output


14. // Value: 1, Count: 3


15. // Value: 2, Count: 2


16. // Value: 3, Count: 1


17. // Count: 0

Listing 6

1. $a = [ 1 , 2 , 3 , 4 ];


2. while (!empty($a)) {


3. $value = array_pop($a);


4. echo PHP_EOL. "Value: ". $value;


5. echo "Count: ". count($a);


6. }


7. // Output


8. // Value: 4, Count: 3


9. // Value: 3, Count: 2


10. // Value: 2, Count: 1


11. // Value: 1, Count: 0

Listing 7

1. $stack = new \SplStack();


2. $stack->push( 1 );


3. $stack->push( 2 );


4. $stack->push( 3 );


5. $stack->rewind();


6. foreach ($stack as $value) {


7. echo $value. PHP_EOL;


8. }


9. // Output


10. // 3


11. // 2


12. // 1

Listing 8

1. $a = [ 6 , 5 , 10 , 1 ];


2. // Simulate a heap sorted by minimum value


3. usort($a, function ($a, $b) {


4. return $a > $b;


5. });


6. foreach($a as $value) {


7. echo $value. PHP_EOL;


8. }


9. // Output


10. // 1


11. // 5


12. // 6


13. // 10