Phabstractic: Queue Data Type

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):

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

AbstractList

As noted Queue inherits from AbstractList (github):

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:

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 work-around.

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:

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:

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.

If you appreciate my programming please help support me through my Patreon.

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

kadar

I'm just a wunk, trying to enjoy life. I am a cofounder of http//originalpursuitssoc.com/ and I like computers, code, creativity, and friends.

You may also like...

Leave a Reply

%d bloggers like this: