Share

In this blog post i will demonstrate a common data-structure from the SPL data structure which is the SplQueue.

In software engineering the queue data-structure is one of the important and commonly used data structures that allows to insert data in FIFO (First in First out) mode. In PHP The SPl data structures extension contains the queue data structure which is the SPLQueue.

The SPLQueue class extends from SPLDoublyLinkedList that we talked about in this article. We mentioned that SPLDoublyLinkedList combines the functionality of both the queue and the stack by using constants:

 public const int SplDoublyLinkedList::IT_MODE_LIFO;
public const int SplDoublyLinkedList::IT_MODE_FIFO;

These constants controls the behavior of the Linked List whether it behaves like a stack or queue.

The SplQueue is a doubly linked list with iteration mode FIFO (First In First Out) in other means the first inserted element is the first element on retrieval. 

Class Terminology

 class SplQueue extends SplDoublyLinkedList {
     /* Inherited constants */
     public const int SplDoublyLinkedList::IT_MODE_LIFO;
     public const int SplDoublyLinkedList::IT_MODE_FIFO;
     public const int SplDoublyLinkedList::IT_MODE_DELETE;
     public const int SplDoublyLinkedList::IT_MODE_KEEP;

     /* Methods */
     public dequeue(): mixed
     public enqueue(mixed $value): void
     
     /* Inherited methods */
     public SplDoublyLinkedList::add(int $index, mixed $value): void
     public SplDoublyLinkedList::bottom(): mixed
     public SplDoublyLinkedList::count(): int
     public SplDoublyLinkedList::current(): mixed
     public SplDoublyLinkedList::getIteratorMode(): int
     public SplDoublyLinkedList::isEmpty(): bool
     public SplDoublyLinkedList::key(): int
     public SplDoublyLinkedList::next(): void

....
....
....

}

the SplQueue extend from SplDoublyLinkedList. For this it contains the same methods provided in the SplDoublyLinkedList in addition to other methods relates to the queue it self where are SplQueue::dequeue() and SplQueue::enqueue().

Example:

<?php
$myQueue = new SplQueue();

$myQueue[] = 'First';
$myQueue[] = 'Second';
$myQueue[] = 'Third';

foreach ($myQueue as $item)  {
    echo $item."\n";
}

// output
First
Second
Third

As you from the output that the queue works using FIFO principle, so the first item inserted is the first on retrieval.

Another method to insert items into the queue using SplQueue::enqueue(value) method:

$myQueue->enqueue('First');
$myQueue->enqueue('Second');
$myQueue->enqueue('Third');

foreach ($myQueue as $item)  {
    echo $item."\n";
}

To dequeue a value from the top of the queue the SplQueue::dequeue() method can be used returning the dequeued value:

echo $myQueue->dequeue();
echo $myQueue->dequeue();
echo $myQueue->dequeue();

// output
First
Second
Third

Note: If you invoke dequeue() on an empty data structure you will get a RuntimeException:

Fatal error:  Uncaught RuntimeException: Can't shift from an empty datastructure

Iterating over the queue

To iterate over the queue we can use the foreach() loop as shown above or we can use a while() loop like so:

$myQueue->rewind();
while ($myQueue->valid()) {
    echo $myQueue->current() . ' ' . $myQueue->key() . "\n";
    $myQueue->next();
}

The SplQueue::rewind() method reset the iterator back to the start. The SplQueue::valid() method check whether the queue is valid and contains more nodes.

The SplQueue::current() method return the current array element. The key() method return the current node index and the next() method move to the next entry in the iterator.

Adding items at specific index

You can add items in specific index using the add() method:

$myQueue->add(3, "Fourth");

Also there is the unshift() method which prepends the queue with an element:

$myQueue->unshift("Zero");

$myQueue->rewind();
while ($myQueue->valid()) {
    echo $myQueue->current() . ' ' . $myQueue->key() . "\n";
    $myQueue->next();
}

// output
Top  0
First 1
Second 2
Third 3

Retrieving items from the specific index

Items can be retrieved from specified index using offsetGet() method:

echo $myQueue->offsetGet(3);   // Fourth

Removing items from the beginning of the queue

The SplQueue::shift() method shifts elements from the beginning of the queue:

$myQueue->shift();   

Queue Data Structure Real World Usage:

• Scheduling CPU Processes.
• Queuing heavy jobs in storage to be processed one by one.
• Handling queue of http requests in a web application.
• Printer jobs
• Handling website traffic.