So far, we have implemented queues where one end is used for enqueuer, and is known as the rear, and the other end is used for dequeuer, and is known as the front. So, in general, each end should be used for a specific purpose. But what if we need to enqueuer and dequeuer from both ends? This is possible by using a concept called the double-ended queue or deque. In deque, both ends can be used for enqueue and dequeue operations. If we look at our queue implementation using linked list, we find that we can insert at last, insert at first, delete at last, and delete at first using our linked list implementation. If we implement a new deque class based on that, we can easily achieve our desired goals. The following figure depicts a double-ended queue:

Here is the implementation of a deque:

class DeQueue { 

    private $limit; 
    private $queue; 

    public function __construct(int $limit = 20) { 
      $this->limit = $limit; 
      $this->queue = new LinkedList(); 
    } 

    public function dequeueFromFront(): string { 

      if ($this->isEmpty()) { 
          throw new UnderflowException('Queue is empty'); 
      } else { 
          $lastItem = $this->peekFront(); 
          $this->queue->deleteFirst(); 
          return $lastItem; 
      } 
    } 

    public function dequeueFromBack(): string { 

      if ($this->isEmpty()) { 
          throw new UnderflowException('Queue is empty'); 
      } else { 
          $lastItem = $this->peekBack(); 
          $this->queue->deleteLast(); 
          return $lastItem; 
      } 
    } 

    public function enqueueAtBack(string $newItem) { 

      if ($this->queue->getSize() < $this->limit) { 
          $this->queue->insert($newItem); 
      } else { 
          throw new OverflowException('Queue is full'); 
      } 
    } 

    public function enqueueAtFront(string $newItem) { 

      if ($this->queue->getSize() < $this->limit) { 
          $this->queue->insertAtFirst($newItem); 
      } else { 
          throw new OverflowException('Queue is full'); 
      } 
    } 

    public function peekFront(): string { 
      return $this->queue->getNthNode(1)->data; 
    } 

    public function peekBack(): string { 
      return $this->queue->getNthNode($this->queue->getSize())->data; 
    } 

    public function isEmpty(): bool { 
      return $this->queue->getSize() == 0; 
    } 

}

Now we are going to use this class to check the operations of a double-ended queue:

try { 
    $agents = new DeQueue(10); 
    $agents->enqueueAtFront("Fred"); 
    $agents->enqueueAtFront("John"); 
    $agents->enqueueAtBack("Keith"); 
    $agents->enqueueAtBack("Adiyan"); 
    $agents->enqueueAtFront("Mikhael"); 
    echo $agents->dequeueFromBack() . "
"; 
    echo $agents->dequeueFromFront() . "
"; 
    echo $agents->peekFront() . "
"; 
} catch (Exception $e) { 
    echo $e->getMessage(); 
}

If we look at the preceding code example, first we add Fred at the front, then we add John at the front again. So the sequence is now John, Fred. Then we add Keith at the back, followed by Adiyan at the back. So now we have the sequence John, Fred, Keith, Adiyan. Lastly, we add Mikhael at the beginning. So the final sequence is Mikhael, John, Fred, Keith, Adiyan.

Since we are performing a dequeue from the back first, Adiyan will be out first, and then Mikhael from the front. The new peek at the front will be John. Here is the output when you run the code:

Adiyan
Mikhael
John