Serverless, ReactPHP, and Expanding Frontiers, May 2019

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

Education Station

Data Structures, Part One

Dictionaries can be called many

different things. JavaScript uses what

is essentially a dictionary for object

literals, while in ECMAScript 6 there is

a specific map data type. Lua once again

just uses a generic table datatype. Other

names for this data type are hash tables

or hash maps.

We start to see a significant diver-

gence in how languages actually specify

the setup. In a strongly-typed language

like Golang, we have to declare what

type both the key and data is. Different

languages also internally store these

data types differently.

The big takeaway is that you are

assigning a name to a value, and storing

it in a variable. This usage is different

than a list, where you’re shoving a value

into a variable and generating a key

automatically. This is important when

you have a set of data where you need to

pull specific values out, not just iterate

over.

$a = ["key" => "value",

"key2" => "value2"];

print $a[ "key"]. PHP_EOL;

// Output

// value

That is not to say you cannot iterate

over a Dictionary. Frequently when

iterating over a dictionary, you’re

working with both the key and value

of each data point. Both the key and

value hold some significance. If you do

not care about the key, a list might be a

better option.

Queues And Stacks

In PHP, there is not a whole lot of

difference between using an array as

either a list or dictionary. In fact, you

can switch between them at any time.

The example below is a perfectly valid

way to use a PHP array. The 1 , 2 and 3

keys get enumerated, while the value

gets a specified key of "key".

$a = [ 1 , 2 , "key" => "value", 3 ];

Generic lists and dictionaries are
handy when data retrieval is considered
“random,” or not always in a specific
direction. When you look up a value in

an associative array by key, this is a type

of random access, in that it is a lookup

that is not constrained to a specific

direction.

For the most part, Stacks and Queues

deal with a more List-like structure, and

you tend to care very little about the

actual key of the value. While you could

use an associative array/dictionary, they

tend to be overkill for a queue or a stack.

Stacks and queues are data structures

where we deal with data coming into a

list, and then how we get the data back

out. There are a few ways we can simu-

late different types of queues and stacks,

and PHP also supplies some classes that

can sometimes be more efficient, or at

least more clear, in their usage.

There are traditionally two types of

ways you pull data from a List: FIFO,

and LIFO. Which one you want to use

is determined by what order you want

to deal with the value you added to the

List.

FIFO Queues: First In, First Out

The first, and most common type, is

a queue or a list that is access “First In,

First Out” (FIFO). Data added to the

array first are the first values that come

back out. In a classic sense, this is much

like how a foreach loop in PHP works

(see Listing 2).

We added 1 first, and it was the first

value that came back out. 4 was added

last, and it was the last value that came

out. First in, first out.

It is not really a queue though. Gener-

ally, in a queue, you take a value out of

the list, manipulate it, and then remove

it from the list. A foreach loop does

not (generally) remove values from the

original list, so the above is not a queue.

We can, however, implement a proper

FIFO queue by using array_shift() as

in Listing 3. This function gets the first

value from an array and removes it

from the array.

We can see we decrease the size of

the array down as we shift things off the

front of the list. As I mentioned before,

with a queue, you generally are not

re-processing a queue more than once.

You may shift values to other queues,

but you will not usually iterate over a

queue multiple times.

The Standard PHP Library, or SPL,

does provide us with a SplQueue class

(Listing 4). This class enforces a FIFO

iteration much like using array_shift

on a bare array but has the added

advantage of being very explicit in what

you are doing.

There are a couple of things to note.

First, do not initialize the SqlQueue with

Listing 2

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


2. foreach($a as $value) {


3. echo $value. PHP_EOL;


4. }


5. // Output


6. // 1


7. // 2


8. // 3


9. // 4

Listing 3

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


2. // add (or push) a value to the end


3. array_push($a, 5 );


4. $a[] = 6; // shorthand for array push


5. 
   


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


7. $value = array_shift($a);


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


9. echo ", Count: ". count($a);


10. }


11. // Output


12. // Value: 1, Count: 5


13. // Value: 2, Count: 4


14. // Value: 3, Count: 3


15. // Value: 4, Count: 2


16. // Value: 5, Count: 1


17. // Value: 6, Count: 0

Listing 4

1. $queue = new \SplQueue();


2. $queue->push( 1 );


3. $queue->push( 2 );


4. $queue->push( 3 );


5. foreach ($queue as $value) {


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


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


8. }


9. // Output


10. // Value: 1, Count: 3


11. // Value: 2, Count: 3


12. // Value: 3, Count: 3