Information structures or Advanced Data Types
Posted: Thu Oct 30, 2003 2:52 pm
I've been messing around with stacks and queues since I got "Fundamental Algorithms" by Donald Knuth. It's part one of a three part series. An awesome book!
Anyway, while I know that Sterlings ADT extension is most likely going to be part of P5 (php5), I couldn't help but throw together a couple of representations of queues and dequeues. I created a tiny number of functions for treating an array as a queue as well as a class. The class variant isn't any more powerful but it is likely to perform better as it doesn't need to do something like count() or sizeof() to be aware of the number of elements within it.
But enough talk. Here is the code.
Now while I know this isn't the kind of thing that's often talked about around here, I figured it's a good idea. As PHP starts being used from more and more general programming, the use of this kind of stuff will grow.
Tell me what you think, if anything at all. Please direct all flames to /dev/null.
Cheers,
BDRK
Anyway, while I know that Sterlings ADT extension is most likely going to be part of P5 (php5), I couldn't help but throw together a couple of representations of queues and dequeues. I created a tiny number of functions for treating an array as a queue as well as a class. The class variant isn't any more powerful but it is likely to perform better as it doesn't need to do something like count() or sizeof() to be aware of the number of elements within it.
But enough talk. Here is the code.
Code: Select all
<?
# The OO approach
class Que
{
var $q=array();
var $cntr;
function ingress($val)
{
$this->q[]=$val;
++$this->cntr;
}
function egress()
{
if($this->cntr>0)
{
--$this->cntr;
return array_shift($this->q);
}
else
{ return false; }
}
function drop()
{
if($this->cntr>0)
{
array_shift($this->q);
--$this->cntr;
}
else
{ return false; }
}
function depleted()
{
if($this->cntr==0)
{ return true; }
else
{ return false; }
}
}
$que = &new Que;
$list=array('Cey', 'Jordan', 'Sprewell', 'Plunkett', 'Iverson', 'Duncan');
# Enter data into the que
while(list($k, $v)=each($list))
{ $que->ingress($v); }
$que->drop();// Get rid of the baseball player
while($que->depleted()==false)
{
$val=$que->egress();
if($val=='Plunkett')
{ /* Who likes football anyways? */ }
else
{ echo $val."\n"; }
}
?>Tell me what you think, if anything at all. Please direct all flames to /dev/null.
Cheers,
BDRK