Editors Note, February 14th 2022: This project is now ABANDONED and no longer supported or updated.

asherwunk/phabstractic now implements a queue data type (an extension of AbstractList implementing ListInterface)

Queue

I quote Wikipedia in my explanation of a stack data structure:

In computer science, a queue (/ˈkjuː/ kyew) is a particular kind of abstract data type or collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position, known as enqueue, and removal of entities from the front terminal position, known as dequeue. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that once a new element is added, all elements that were added before have to be removed before the new element can be removed. Often a peek or front operation is also entered, returning the value of the front element without dequeuing it. A queue is an example of a linear data structure, or more abstractly a sequential collection.

Queues are extremely useful abstract data types.  They are implemented in many programming languages, and sometimes even make up the core of another structure.  One application they have is in sequence ordering.  Items can be lined up to be dealt with and processed in an orderly fashion, such as multi-tasking.

A queue can be visualized as the following (also from Wikipedia):

ListInterface

First Queue inherits from AbstractList and thus implements ListInterface (github):

namespace Phabstractic\Data\Types\Resource
{
    interface ListInterface extends \Countable {
        public function top(); 
        
        public function &topReference();
        
        public function push();
        
        public function pushReference(&$a); 
        
        public function pop();
        
        public function &popReference(); 
        
        public function index($i);
        
        public function &indexReference($i); 
        
        public function count();
        
        public function isEmpty();
        
        public function clear();
        
        public function getList();
        
    }
    
}

NOTE – ::top() is like ::peek() as reference in Wikipedia.

AbstractList

As noted Queue inherits from AbstractList (github):

namespace Phabstractic\Data\Types\Resource
{
    abstract class AbstractList implements ListInterface
    {
        protected $list = array();
        
        public function __construct($data = null) 
        {
            // ...
        } 
        
        abstract public function top();
        
        abstract public function &topReference();
        
        abstract public function push();
        
        abstract public function pushReference( &$a );
        
        abstract public function pop();
        
        abstract public function &popReference();
        
        abstract public function index($i);
        
        abstract public function &indexReference($i); 
        
        public function count()
        {
            return count($this->list);
        }
        
        public function isEmpty()
        { 
            return empty($this->list); 
        } 
    
        public function clear()
        { 
            $this->list = array();
            return $this;
        }
        
        public function remove($value)
        {
            if ($key = array_search($value, $this->list)) {
                unset($this->list[$key]);
            }
            
            // resets indices
            $this->list = array_merge($this->list, array());
            return $this->list;
        }
        
        public function getList()
        {
            return $this->list;
        }
        
        abstract public function exchange();
         
        abstract public function duplicate();
        
        abstract function roll($i);

    }     

}

Queue Specifics

We implement the Queue FIFO by simply using an array in PHP.  This array grows and shrinks accordingly.  We mostly just wrap functionality around the idea that the first element of the internal array is the end of the queue.  Doing that, it’s simply a matter of shifting and unshifting an array using the built-in PHP array functions.  A function of interest, however, would be exchange and roll:

public function exchange() { 
    $m1 = &$this->popReference();
    $m2 = &$this->popReference();
    // http://php.net/manual/en/function.array-unshift.php#40270
    array_unshift($this->list, '');
    $this->list[0] = &$m1;
    array_unshift($this->list, '');
    $this->list[0] = &$m2;
    return $this;
}

Of particular note, you’ll see how I added a reference to the beginning of an array. The unshift PHP function doesn’t apply or understand references, so this was a workaround.

public function roll($c)
{
    if (!is_int($c)) {
        if ($this->conf->strict) {
            throw new TypesException\InvalidArgumentException(
                'Phabstractic\\Data\\Types\\Queue->roll: ' .
                'argument not integer');
        } else {
            return false;
        }
        
    }
    
    if (abs($c) > ($l = count($this->list))) { 
        if ($c < 0) {
            $c = (abs($c) % $l) * -1;
        } else {
            $c %= $l;
        }
        
    }
    
    // rotate right
    if ($c > 0) { 
        $this->list = array_merge(array_slice($this->list, $c), 
                                  array_slice($this->list, 0, $c)); 
    } else if ( $c < 0 ) {
        // rotate left
        $c = abs($c);
        $this->list = array_merge(array_slice($this->list, $l - $c),
                                  array_slice($this->list, 0, $l - $c)); 
    }
    
    return true;
}

Something to note about indexing that’s very important.  Unlike a Stack, we index from the beginning of the private array. You can observe this here:

public function index($i)
{
    if ($i > (count($this->list) - 1) || $i < 0) {
        if ($this->conf->strict) {
            throw new TypesException\RangeException(
                'Phabstractic\\Data\\Types\\Queue->index: ' .
                'out of range');
        } else {
            return new None();
        }
        
    } else {
        return $this->list[$i];
    }
    
}

We also define a bottom method as well as a top method.

A nice thing about concrete implementation is you can do things like implement \ArrayAccess.  Note that ArrayAccess methods index using the index() method, which accesses the private array from the beginning:

public function offsetSet($key, $value)
{ 
    if (is_numeric($key)) { 
        if ($this->offsetExists($key)) {
            // incorporate indexing logic
            $r =& $this->indexReference($key);
            $r = $value; 
            return count($this->list);
        }
        
    }
    
    // If the key is empty: queue[], push value
    if (!$key) {
        return $this->push($value);
    }
    
    if ($this->conf->strict) {
        throw new TypesException\RangeException(
            'Phabstractic\\Data\\Types\\Queue->offsetSet: ' .
            'offsetSet key ' . $key . ' out of range.');
    }
}

public function offsetGet($key)
{ 
    if (!is_numeric($key)) {
        if ($this->conf->strict) {
            throw new TypesException\RangeException(
                'Phabstractic\\Dat\\Type\\Queue->offsetGet: ' .
                'Invalid Argument Key');
        }
    }
    
    // can also return Types\None
    return $this->index($key);
}

public function offsetUnset($key)
{ 
    if (is_numeric($key)) { 
        if ($key > (count($this->list) - 1) || $key < 0)
        { 
            return false; 
        } else { 
            unset($this->list[$key]);
            // reset keys
            $this->list = array_merge($this->list, array());
            return true; 
        }
        
    } 
     
    return false; 
}

public function offsetExists($key)
{ 
    if (is_numeric($key)) { 
        if ($key > (count($this->list) - 1) || $key < 0) {
            return false; 
        } else {
            return isset($this->list[$key]);
        }
        
    }
    
}

Conclusion

Queues are very important pieces of code.  They are used in numerous many places including web services, transactions, and multi-process operating systems.

(View on GitHub)

This is part of the Phabstractic Library.

photo credit: People queuing at Shake Shack in Tokyo, Japan via photopin (license)

Asher Wolfstein

Metaverse Resident

About the Author

A metaverse resident, you can find me on Second Life (kadar.talbot) and other online platforms. I write about my digital life, my musings, and my projects as a programmer, webmaster, artist, and game designer. (exist (be wunk) (use rational imagination) (import artist coder maker furry) (conditional (if (eq you asshole) (me (block you))))

View Articles