Taking Stock of the Stack in PHP

29 03 2014

flickr: by cvfyne

Introduction

You may have heard about ‘the stack’ or call stack, part of a computer’s random access memory (RAM), wherein a function, including its parameters and return value, reside temporarily. One retrieves them on the basis of FILO (First In, Last Out), synonymous with LIFO (Last In, First Out). Users of high-level languages like C and PHP are much less likely to directly handle this stack.

The stack available to PHP users, allows an application to sequentially add values or access them singly in reverse order. If you examine the internals of array_push, i.e. its C-based source code, you will note that the variable *stack points to an array in which the code adds elements to its end by means of the macro zend_hash_next_index_insert. How surprising that a mere array may constitute a stack in PHP! Is this sort of stack really legitimate? Many technical articles identify the portion of the stack with the latest value as the top, not its end.

PHP does support a bona fide stack because a stack’s top is relative to whatever way it grows, which may be vertically in either direction or horizontally from left to right (see Wikipedia article). If you prefer a more traditional stack, this SitePoint article shows how you may create one using oddly enough PHP’s support for another data structure, a queue. Apparently, what defines a stack is its interface more than its implementation, which may be an array or a linked list, as long as the only operations related to data involve pushing or popping “…with few other helper operations” (see Wikipedia article).

A Use-Case for the Stack?

Consider the problem of converting 11 in base ten to its equivalent binary value. Suppose, you had to ditch the handy albeit error prone base_convert (it fails to meaningfully convert some real numbers; see bug report #65212), and create code from scratch to handle base conversion. How would you approach such a challenge? Solving this problem requires more than knowledge of PHP; one must possess a mathematical understanding of what base conversion entails. Fortunately, the math is trivial, involving only simple arithmetic, namely division, According to the following chart, one should divide the number by two, note the result and remainder. Then, repeat the process until the number reaches zero, as follows:

2 11 R
2 5 1
2 2 1
2 1 0
2 0 1

Note: the “R” column list designates the remainders. Once you have the values in the remainder column, a question arises as to how to display them, take the commonplace top-down approach or observe the seemingly unnatural bottom-up? Let’s find out!

Two Non-stacked Solutions

The following proposes one way for PHP to solve the problem:

<?php
$base = 2;
$num = 11;
for ($i=0; $num &gt; 0; $i++) {
  $arr[$i] = $num % $base;   // store remainder in array
  $num = (int) ($num/$base); // int cast eliminates floor()
 }
 echo join('',$arr);       // wrong result: 1101

The int cast results in setting $num to an integer. If you fail to enclose the division expression in parentheses, then the int cast will only apply to $num instead of the expression’s result. Note that per the Manual: “There is no integer division operator in PHP.” The result will be a real number, i.e. a float. This aspect of PHP contrasts greatly with the language which underlies it, the C Programming Language. Let’s take a brief detour, by reviewing the following C script, noting that the fractional portion is discarded:


#include
int main(void){
int num = 11;
int base = 2;
int res = num / base;
printf("\nResult is %d",res); // 5
return 0;
}

Returning to the base conversion example, the last statement joins the array values into a string which displays as 1101 or 13 in base ten, due to the order of the remainder values. This peculiar error arises owing to the fact that each successive remainder represents a greater multiple of two, so the correct rendering of the remainders must display them in reverse order, as follows: 1011. Correcting the way PHP displays the array values is easy if one uses array_reverse:

<?php
$base = 2;
$num = 11;

for ($i=0; $num &gt; 0; $i++) {
  $arr[$i] = $num % $base;         // store remainder in array
  $num = (int) ($num/$base);       // no integer division
}

echo join('',array_reverse($arr)); // 1011

Once the binary number appears with the reversed remainders its value clearly equals 11. The following expression deciphers the binary number using the caret symbol to express exponentiation:

(1 * 2^3) + (0 *2^2) + (1* 2^1) + (1*2^0)

Using a Stack

While competency as a coder is important for a successful outcome with the base conversion problem, beyond skill, one needs to recognize that the nature of the problem lends itself to a stack. By utilizing PHP’s support for this data structure, the first example’s incorrect result would have been avoided and the second example would not have incurred the expense of an extra function. Consider the following code:

<?php

$num = 11;
$base = 2;
$stack = [];

while( $num &gt; 0) {

 array_push($stack,($num % $base)); // push remainder onto stack
 $num = (int) ($num/$base); 
}

while($stack) {
 echo array_pop($stack);           // 1011 in final iteration
}
echo &quot;\n&quot;;

This code could still benefit from a slight tweaking. According to the manual, if you use array_push just to add one element to an array, you could save yourself the overhead of the function call by using this syntax “$array[] =” for assignment. So, the following enhancement improves the code:

<?php

$num = 11;
$base = 2;
$stack = [];             

while( $num &gt; 0) {
  $stack[] = $num % $base;  // push remainder onto stack
  $num = (int) ($num/$base); 
}

while($stack) {
  echo array_pop($stack); // 1011 after final iteration
}
echo &quot;\n&quot;;

The Other Stack

The Standard PHP Library (SPL) implements a stack of sorts using a doubly linked list to offer an OOP solution in its SplStack class, which includes methods for pushing and popping. You may wish to review the aforementioned SitePoint article since it graphically depicts a doubly linked list and shows how to easily extend a class to take advantage of the SplStack class. The following is a rewrite of the previous example, using the SplStack class:

<?php 

$num = 11; 
$base = 2; 
$stack = new SplStack();
while( $num &gt; 0) {
    $stack-&gt;push($num % $base);
    $num = (int) ($num/$base); // no integer division 
}
$stack-&gt;setIteratorMode(SplDoublyLinkedList::IT_MODE_LIFO);
for ($stack-&gt;rewind(); $stack-&gt;valid(); $stack-&gt;next()) { 
    echo $stack-&gt;current();
}
// Output: 1011 

If you have zero interest in the details of linked-lists, let alone a doubly-linked list, the SplStack class stands on its own merit; expertise with doubly-linked lists is unnecessary. The class has a slew of helpful methods at your disposal, depending on what you wish to do. Matthew Turland wrote in 2011 a criticism of the SplStack, in which he objects to its performance and points out that it does not strictly conform to the idea of a stack. Try it out for yourself to see if you agree with his assessment. Perhaps, this unconventional stack may suit your purposes.

Other Links of Interest:

http://www.php.net/manual/en/spl.datastructures.php
http://www.php.net/manual/en/class.splstack.php
http://www.programmerinterview.com/index.php/data-structures/difference-between-stack-and-heap/
http://gribblelab.org/CBootcamp/7_Memory_Stack_vs_Heap.html#sec-2

This work is licensed under a Creative Commons License

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: