Queue in PHP Tutorial

Udemy Generic 728x90

A queue is an ordered collection of items in which new items are added from one end known as “rear” and  deleted from another end known as “front”.

The item at the front (this item enqueued before all existing item in queue) will wait least and most recently added item will wait until all items before it are served .This ordering principle is called as FIFO (first in ,first serve) . It is also known as “ first-come first-serve” .

Example

  • At railway station, number of person waiting in a line to book their ticket before booking window is an example of queue as who came first will get a chance to book ticket first .

The Queue ADT(Abstract Data type)

The Queue ADT means specification of queue and basic operation that can be performed on queue . The Queue ADT is given below.

  • Queue(limit) - creates a new queue that is empty. We can pass an optional  integer parameter to queue  and returns an empty queue.If limit is not given , infinite queue is created otherwise queue size is fixed upto limit. Optional parameter must be integer and greater than zero otherwise infinite queue is created.
  • enqueue(item)- adds a new item to the rear of the queue. It needs the item to be enqueued . On success it returns nothing and on failure it throws exception .
  • dequeue()-removes the front item from the queue. It needs no parameters. The queue is modified. On success it returns front element and on failure it throws exception
  • isEmpty()- tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
  • size()- returns the number of items in the queue. It needs no parameters and returns an integer.
  • used data type /data structure-  To implement queue we have used array as underlying data structure.

PHP Implementation of Queue

<br />
&lt;?php</p>
<p>class Queue{</p>
<p> private $queue = NULL;<br />
 private $limit ;</p>
<p> function __construct($limit = -1){<br />
   $this-&gt;queue = array();<br />
   $this-&gt;limit = $this-&gt;getLimit($limit);<br />
 }</p>
<p> function enqueue($item){</p>
<p>   /**<br />
     There are two scenario when data can be enqueued.<br />
       1)- created queue is infinite queue then element can be enqueued<br />
       2)- created queue is finite means has a limit then element can be enqueued only when queue size<br />
           is less than given limit.<br />
   */<br />
   $isInfiniteQueue        = ($this-&gt;limit == -1);<br />
   $isSizeSmallerThanLimit = (count($this-&gt;queue) &lt; ($this-&gt;limit));<br />
   if(($isInfiniteQueue) || ((!$isInfiniteQueue) &amp;&amp; $isSizeSmallerThanLimit) ) {<br />
        array_push($this-&gt;queue,$item);<br />
   }else {<br />
        throw new Exception(&quot;Queue is already full&quot;);<br />
   }<br />
 }</p>
<p> function dequeue(){<br />
    if(!empty($this-&gt;queue)){<br />
        $frontItem   = array_shift($this-&gt;queue);<br />
        return $frontItem;<br />
    } else {<br />
        throw new Exception(&quot;Trying to dequeue on empty queue&quot;);<br />
    }<br />
 }</p>
<p> function isEmpty(){<br />
     $isEmpty = empty($this-&gt;queue);<br />
     return $isEmpty;<br />
 }</p>
<p> function size(){<br />
    $size = count($this-&gt;queue);<br />
    return $size;<br />
 }</p>
<p> private function getLimit($limit)<br />
    if(!((gettype($limit) == 'integer') &amp;&amp; $limit &gt; 0)){<br />
        $limit = -1;<br />
    }<br />
    return $limit;<br />
 }</p>
<p>}<br />

Complexity analysis of Queue ADT

  • Queue(limit) -  Time complexity of this function is O(1).
  • enqueue(item)-  Time complexity of this function is O(1) as enqueuing an item do not require array rearrangement.
  • dequeue()-    In  dequeue  operation  array is rearranged so it   takes time in order of total item in queue . Thus its time complexity is O(n).
  • isEmpty()-  Time complexity of this function is O(1).
  • size()- Time complexity of this function is O(1).

Selection criteria for Queue implemented using Array

Queue is powerful data structure and implementing it using array is simple and easy. Array implementation of queue has some drawbacks also.
Dequeuing operation in queue is costly as its time complexity is proportional to number of element in queue .Thus we should use queue (implemented using array) when size of queue is relatively small.
If we analyze that in our case size of queue will be relatively large ,we should use queue implemented using linklist.

Udemy Generic 728x90

Spread the word. Share this post!