Implementing a circular queue

When we use a standard queue, every time we dequeue an item, we have to re-buffer the whole queue. In order to solve this problem, we can use a circular queue, where the rear is followed by the front, forming a circle. This special type of queue requires a special calculation for the enqueue and dequeue operations, with consideration of the rear, front, and limit of the queue. Circular queues are always fixed queues, and are also known as circular buffers, or ring buffers. The following figure shows a representation of a circular queue:

We can implement a circular queue using a PHP array. Since we have to calculate the positions of the rear and front part, the array can be used efficiently for this purpose. Here is an example of a circular queue:

class CircularQueue implements Queue { 

private $queue;
private $limit;
private $front = 0;
private $rear = 0;

public function __construct(int $limit = 5) {
$this->limit = $limit;
$this->queue = [];
}

public function size() {
if ($this->rear > $this->front)
return $this->rear - $this->front;
return $this->limit - $this->front + $this->rear;
}

public function isEmpty() {
return $this->rear == $this->front;
}

public function isFull() {
$diff = $this->rear - $this->front;
if ($diff == -1 || $diff == ($this->limit - 1))
return true;
return false;
}

public function enqueue(string $item) {
if ($this->isFull()) {
throw new OverflowException("Queue is Full.");
} else {
$this->queue[$this->rear] = $item;
$this->rear = ($this->rear + 1) % $this->limit;
}
}

public function dequeue() {
$item = "";
if ($this->isEmpty()) {
throw new UnderflowException("Queue is empty");
} else {
$item = $this->queue[$this->front];
$this->queue[$this->front] = NULL;
$this->front = ($this->front + 1) % $this->limit;
}
return $item;
}

public function peek() {
return $this->queue[$this->front];
}

}
Since we are considering 0 as a front marker, the total size of the queue will be of the limit -1.

 

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset