2024-09-28 Daily Challenge

Today I have done leetcode's September LeetCoding Challenge with cpp.

September LeetCoding Challenge 28

Description

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.

Solution

class MyCircularDeque {
  int front = 0;
  int back = 0;
  int sz = 0;
  int cap = 0;
  vector<int> c;
public:
  MyCircularDeque(int k): cap(k) {
    c.resize(k, -1);
  }
  
  bool insertFront(int value) {
    if(isFull()) return false;
    front += cap - 1;
    front %= cap;
    c[front] = value;
    sz += 1;
    return true;
  }
  
  bool insertLast(int value) {
    if(isFull()) return false;
    c[back] = value;
    back += 1;
    back %= cap;
    sz += 1;
    return true;
  }
  
  bool deleteFront() {
    if(isEmpty()) return false;
    front += 1;
    front %= cap;
    sz -= 1;
    return true;
  }
  
  bool deleteLast() {
    if(isEmpty()) return false;
    back += cap - 1;
    back %= cap;
    sz -= 1;
    return true;
  }
  
  int getFront() {
    if(isEmpty()) return -1;
    return c[front];
  }
  
  int getRear() {
    if(isEmpty()) return -1;
    return c[(back + cap - 1) % cap];
  }
  
  bool isEmpty() {
    return !sz;
  }
  
  bool isFull() {
    return sz == cap;
  }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */