Deque In PHP Tutorial

Udemy Generic 728x90

DEQUE /DECK

Deque or Deck is  a double-ended  queue. It allows element to be enqueued or dequeued on either end. New item can be inserted on both front and rear .In the same way item can be dequeued on both front and rear .

Example

Lets say that n person are waiting for health check up and suddenly a serious patient arrives . What to do now?. Should he been waited or checked up before all waiting candidate?. Obviously  before all waiting candidate.To model  such scenarios in real word we need Deque.

 The Deque ADT(Abstract data type)

Deque ADT refers to specification and basic operations that can be performed on deque. The Deque ADT is given below.

  • Deque(limit)  creates a empty deque. It uses a parameter that is optional . If limit parameter is passed at the time of object creation , deque with fixed sized(equal to given limit) is created otherwise deque with infinite size is created.
  • insert_front(item) is a function that pushes given item to the front of deque.On success it returns nothing and on failure it throws exception.
  • insert_back(item) is a function that pushes given item to the rear of deque.On success it returns nothing and on failure it throws exception.
  • remove_front() is a function that pops item from front of the deque.The queue is modified. On success it returns nothing and on failure it throws exception.
  • remove_back() is a function that pops item from rear of the deque.The queue is modified. On success it returns nothing and on failure it throws exception.
  • isEmpty() This function test whether deque is empty.It requires no parameter and returns boolean value.
  • size() This function returns number of items in deque.It requires no parameter and returns a integer.
  • Underlying data structure To implement deque in PHP we will array as underlying data structure.

 PHP implementation of Deque Using Array

<br />
&lt;?php<br />
class Deque{</p>
<p> private $deque = NULL;<br />
 private $limit ;</p>
<p> function __construct($limit = -1){<br />
     $this-&gt;deque = array();<br />
     $this-&gt;limit = $this-&gt;getLimit($limit);<br />
     echo $this-&gt;limit;<br />
 }</p>
<p> function insert_front($item){<br />
     if($this-&gt;getInsertStatus()) {<br />
         array_unshift($this-&gt;deque, $item);<br />
     }else {<br />
         throw new Exception(&quot;Deque is already full&quot;);<br />
     }<br />
 }</p>
<p> function insert_back($item){<br />
     if($this-&gt;getInsertStatus()) {<br />
         array_push($this-&gt;deque,$item);<br />
     }else {<br />
         throw new Exception(&quot;Deque is already full&quot;);<br />
     }<br />
 }</p>
<p> function remove_front(){<br />
      if(!empty($this-&gt;deque)){<br />
          array_shift($this-&gt;deque);<br />
      }else {<br />
          throw new Exception(&quot;Trying to pop element from empty deque&quot;);<br />
     }<br />
 }</p>
<p> function remove_back(){<br />
      if(!empty($this-&gt;deque)){<br />
          array_pop($this-&gt;deque);<br />
      }else {<br />
          throw new Exception(&quot;Trying to pop element from empty deque&quot;);<br />
      }<br />
 }</p>
<p> function isEmpty(){<br />
      $isEmpty = empty($this-&gt;deque);<br />
      return $isEmpty;<br />
 }</p>
<p> function size(){<br />
      $size = count($this-&gt;deque);<br />
      return $size;<br />
 }</p>
<p> private function getInsertStatus(){<br />
 /**<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<br />
          queue size is less than given limit.<br />
    */</p>
<p>     $isInfiniteQueue        = ($this-&gt;limit == -1);<br />
     $isSizeSmallerThanLimit = (count($this-&gt;deque) &lt; ($this-&gt;limit));<br />
     $status = ($isInfiniteQueue) || ((!$isInfiniteQueue) &amp;&amp; $isSizeSmallerThanLimit);<br />
     return $status;<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 />
     }<br />
 }<br />

Complexity analysis of Deque ADT

  • Deque(limit)  Time complexity of this function is O(1).
  • insert_front(item)  To insert element at front all element in deque are shifted right and time taken in this process is proportional to number of elements in deque thus  its time complexity is  O(n).
  • insert_back(item) Time complexity of this function is O(1) as it do not require array rearrangement.
  • remove_front() To remove front element all element in deque are shifted left and time taken in this process is proportional to number of elements in deque thus  its time complexity is  O(n).
  • remove_back() Time complexity of this function is O(1) as it do not require array rearrangement.
  • isEmpty()  Time complexity of this function is O(1).
  • size()  Time complexity of this function is O(1).

Selection criteria for Deque implemented using Array

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

Udemy Generic 728x90

Spread the word. Share this post!