641. Design Circular Deque

[mah-shamim]

Topics: Array, Linked List, Design, Queue

Design your implementation of the circular double-ended queue (deque).

Implement the MyCircularDeque class:

• MyCircularDeque(int k) Initializes the deque with a maximum size of k.
• boolean insertFront() Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.
• boolean insertLast() Adds an item at the rear of Deque. Returns true if the operation is successful, or false otherwise.
• boolean deleteFront() Deletes an item from the front of Deque. Returns true if the operation is successful, or false otherwise.
• boolean deleteLast() Deletes an item from the rear of Deque. Returns true if the operation is successful, or false otherwise.
• int getFront() Returns the front item from the Deque. Returns -1 if the deque is empty.
• int getRear() Returns the last item from Deque. Returns -1 if the deque is empty.
• boolean isEmpty() Returns true if the deque is empty, or false otherwise.
• boolean isFull() Returns true if the deque is full, or false otherwise.

Example 1:

• Input:
  ["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
  [[3], [1], [2], [3], [4], [], [], [], [4], []]
• Output: [null, true, true, true, false, 2, true, true, true, 4]
• Explanation:
  MyCircularDeque myCircularDeque = new MyCircularDeque(3);
  myCircularDeque.insertLast(1); // return True
  myCircularDeque.insertLast(2); // return True
  myCircularDeque.insertFront(3); // return True
  myCircularDeque.insertFront(4); // return False, the queue is full.
  myCircularDeque.getRear(); // return 2
  myCircularDeque.isFull(); // return True
  myCircularDeque.deleteLast(); // return True
  myCircularDeque.insertFront(4); // return True
  myCircularDeque.getFront(); // return 4

Constraints:

• 1 <= k <= 1000
• 0 <= value <= 1000
• At most 2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.

[kovatz]

e can use an array to represent the deque structure. We'll maintain a head and tail pointer that will help us track the front and rear of the deque, wrapping around when necessary to achieve the circular behavior.

Let's implement this solution in PHP: 641. Design Circular Deque

Here's a step-by-step solution for the MyCircularDeque class:

<?php
class MyCircularDeque {
    /**
     * @var array
     */
    private $deque;
    /**
     * @var int
     */
    private $maxSize;
    /**
     * @var int
     */
    private $front;
    /**
     * @var int
     */
    private $rear;
    /**
     * @var int
     */
    private $size;

    /**
     * Initialize your data structure here. Set the size of the deque to be k.
     *
     * @param Integer $k
     */
    function __construct($k) {
        $this->deque = array_fill(0, $k, -1);
        $this->maxSize = $k;
        $this->front = 0;
        $this->rear = 0;
        $this->size = 0;
    }

    /**
     * Adds an item at the front of Deque. Return true if the operation is successful.
     *
     * @param Integer $value
     * @return Boolean
     */
    function insertFront($value) {
        if ($this->isFull()) {
            return false;
        }
        // Move the front pointer backward
        $this->front = ($this->front - 1 + $this->maxSize) % $this->maxSize;
        $this->deque[$this->front] = $value;
        $this->size++;
        return true;
    }

    /**
     * Adds an item at the rear of Deque. Return true if the operation is successful.
     *
     * @param Integer $value
     * @return Boolean
     */
    function insertLast($value) {
        if ($this->isFull()) {
            return false;
        }
        $this->deque[$this->rear] = $value;
        $this->rear = ($this->rear + 1) % $this->maxSize;
        $this->size++;
        return true;
    }

    /**
     * Deletes an item from the front of Deque. Return true if the operation is successful.
     *
     * @return Boolean
     */
    function deleteFront() {
        if ($this->isEmpty()) {
            return false;
        }
        // Move the front pointer forward
        $this->front = ($this->front + 1) % $this->maxSize;
        $this->size--;
        return true;
    }

    /**
     * Deletes an item from the rear of Deque. Return true if the operation is successful.
     *
     * @return Boolean
     */
    function deleteLast() {
        if ($this->isEmpty()) {
            return false;
        }
        // Move the rear pointer backward
        $this->rear = ($this->rear - 1 + $this->maxSize) % $this->maxSize;
        $this->size--;
        return true;
    }

    /**
     * Get the front item from the deque. If the deque is empty, return -1.
     *
     * @return Integer
     */
    function getFront() {
        if ($this->isEmpty()) {
            return -1;
        }
        return $this->deque[$this->front];
    }

    /**
     * Get the last item from the deque. If the deque is empty, return -1.
     *
     * @return Integer
     */
    function getRear() {
        if ($this->isEmpty()) {
            return -1;
        }
        // Get the element before the current rear position
        return $this->deque[($this->rear - 1 + $this->maxSize) % $this->maxSize];
    }

    /**
     * Checks whether the deque is empty or not.
     *
     * @return Boolean
     */
    function isEmpty() {
        return $this->size == 0;
    }

    /**
     * Checks whether the deque is full or not.
     * 
     * @return Boolean
     */
    function isFull() {
        return $this->size == $this->maxSize;
    }
}

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * $obj = MyCircularDeque($k);
 * $ret_1 = $obj->insertFront($value);
 * $ret_2 = $obj->insertLast($value);
 * $ret_3 = $obj->deleteFront();
 * $ret_4 = $obj->deleteLast();
 * $ret_5 = $obj->getFront();
 * $ret_6 = $obj->getRear();
 * $ret_7 = $obj->isEmpty();
 * $ret_8 = $obj->isFull();
 */

?>

Explanation:

1. Initialization:

   • We initialize the deque using an array of size k and set all values to -1 initially.
   • The front and rear pointers are initialized to 0.
   • size keeps track of the current number of elements in the deque.

2. insertFront($value):

   • Check if the deque is full using isFull().
   • If not, decrement the front pointer (with circular wrap-around using modulo).
   • Place the value at the new front and increment the size.

3. insertLast($value):

   • Check if the deque is full.
   • If not, place the value at the rear and move the rear pointer forward (again using modulo for wrap-around).
   • Increment the size.

4. deleteFront():

   • Check if the deque is empty using isEmpty().
   • If not, increment the front pointer (circular wrap-around) and decrement the size.

5. deleteLast():

   • Check if the deque is empty.
   • If not, decrement the rear pointer and reduce the size.

6. getFront():

   • If the deque is empty, return -1.
   • Otherwise, return the element at the front pointer.

7. getRear():

   • If the deque is empty, return -1.
   • Otherwise, return the element before the current rear pointer (since rear points to the next available position).

8. isEmpty():

   • Returns true if the deque is empty (size is 0).

9. isFull():

   • Returns true if the deque is full (size equals maxSize).

Example Walkthrough

$myCircularDeque = new MyCircularDeque(3);  // Initialize deque with size 3

$myCircularDeque->insertLast(1);  // return true
$myCircularDeque->insertLast(2);  // return true
$myCircularDeque->insertFront(3); // return true
$myCircularDeque->insertFront(4); // return false, deque is full
echo $myCircularDeque->getRear(); // return 2
echo $myCircularDeque->isFull();  // return true
$myCircularDeque->deleteLast();   // return true
$myCircularDeque->insertFront(4); // return true
echo $myCircularDeque->getFront(); // return 4

Time Complexity:

• Each operation (insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull) runs in O(1) time since they all involve constant-time array operations and pointer manipulations.

Space Complexity:

• The space complexity is O(k), where k is the size of the deque. We allocate space for k elements in the deque array.

[mah-shamim]

Thanks to implement a circular deque

[kovatz]

Thanks