641. Design Circular Deque

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.

Approach 01:

class MyCircularDeque {
 public:
  /** Initialize your data structure here. Set the size of the deque to be k. */
  MyCircularDeque(int capacity) : capacity(capacity), dequeArray(capacity), rear(capacity - 1) {}

  /** Adds an item at the front of Deque. Return true if the operation is successful. */
  bool insertFront(int value) {
    if (isFull())
      return false;

    front = (--front + capacity) % capacity;
    dequeArray[front] = value;
    ++currentSize;
    return true;
  }

  /** Adds an item at the rear of Deque. Return true if the operation is successful. */
  bool insertLast(int value) {
    if (isFull())
      return false;

    rear = ++rear % capacity;
    dequeArray[rear] = value;
    ++currentSize;
    return true;
  }

  /** Deletes an item from the front of Deque. Return true if the operation is successful. */
  bool deleteFront() {
    if (isEmpty())
      return false;

    front = ++front % capacity;
    --currentSize;
    return true;
  }

  /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
  bool deleteLast() {
    if (isEmpty())
      return false;

    rear = (--rear + capacity) % capacity;
    --currentSize;
    return true;
  }

  /** Get the front item from the deque. */
  int getFront() {
    return isEmpty() ? -1 : dequeArray[front];
  }

  /** Get the last item from the deque. */
  int getRear() {
    return isEmpty() ? -1 : dequeArray[rear];
  }

  /** Checks whether the circular deque is empty or not. */
  bool isEmpty() {
    return currentSize == 0;
  }

  /** Checks whether the circular deque is full or not. */
  bool isFull() {
    return currentSize == capacity;
  }

 private:
  const int capacity;                // Capacity of the deque
  vector<int> dequeArray;            // Array to store deque elements
  int currentSize = 0;               // Number of elements in the deque
  int front = 0;                     // Index of the front element
  int rear;                          // Index of the rear element
};

class MyCircularDeque:

    def __init__(self, capacity: int):
        """Initialize your data structure here. Set the size of the deque to be capacity."""
        self.capacity = capacity
        self.dequeArray = [0] * capacity
        self.size = 0
        self.front = 0
        self.rear = capacity - 1

    def insertFront(self, value: int) -> bool:
        """Adds an item at the front of Deque. Return true if the operation is successful."""
        if self.isFull():
            return False
        self.front = (self.front - 1 + self.capacity) % self.capacity
        self.dequeArray[self.front] = value
        self.size += 1
        return True

    def insertLast(self, value: int) -> bool:
        """Adds an item at the rear of Deque. Return true if the operation is successful."""
        if self.isFull():
            return False
        self.rear = (self.rear + 1) % self.capacity
        self.dequeArray[self.rear] = value
        self.size += 1
        return True

    def deleteFront(self) -> bool:
        """Deletes an item from the front of Deque. Return true if the operation is successful."""
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True

    def deleteLast(self) -> bool:
        """Deletes an item from the rear of Deque. Return true if the operation is successful."""
        if self.isEmpty():
            return False
        self.rear = (self.rear - 1 + self.capacity) % self.capacity
        self.size -= 1
        return True

    def getFront(self) -> int:
        """Get the front item from the deque."""
        return -1 if self.isEmpty() else self.dequeArray[self.front]

    def getRear(self) -> int:
        """Get the last item from the deque."""
        return -1 if self.isEmpty() else self.dequeArray[self.rear]

    def isEmpty(self) -> bool:
        """Checks whether the circular deque is empty or not."""
        return self.size == 0

    def isFull(self) -> bool:
        """Checks whether the circular deque is full or not."""
        return self.size == self.capacity

Time Complexity

• Insert Operations (insertFront and insertLast):

  Both operations involve updating the front or rear pointers and adding an element to the internal array, which are constant-time operations. Hence, both have a time complexity of \(O(1)\).

• Delete Operations (deleteFront and deleteLast):

  These operations involve updating the front or rear pointers and adjusting the current size, which are also constant-time operations. Therefore, both have a time complexity of \(O(1)\).

• Access Operations (getFront and getRear):

  Accessing the front or rear element is a direct array access, which takes constant time. Thus, the time complexity for both is \(O(1)\).

• Check Operations (isEmpty and isFull):

  Both operations involve a simple comparison, making them constant-time operations with a time complexity of \(O(1)\).

• Overall Time Complexity:

  Each operation in the deque (insertion, deletion, access, and check) runs in constant time, resulting in an overall time complexity of \(O(1)\) for all operations.

Space Complexity

• Auxiliary Space:

  The space complexity is dominated by the storage required for the internal array dequeArray, which is used to store the elements of the deque. The size of this array is proportional to the capacity of the deque, resulting in a space complexity of \(O(k)\), where k is the capacity of the deque.

• Overall Space Complexity:

  The overall space complexity is \(O(k)\), where k is the capacity of the deque, as the storage requirement grows linearly with the number of elements that can be stored.