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 ofk
.boolean insertFront()
Adds an item at the front of Deque. Returnstrue
if the operation is successful, orfalse
otherwise.boolean insertLast()
Adds an item at the rear of Deque. Returnstrue
if the operation is successful, orfalse
otherwise.boolean deleteFront()
Deletes an item from the front of Deque. Returnstrue
if the operation is successful, orfalse
otherwise.boolean deleteLast()
Deletes an item from the rear of Deque. Returnstrue
if the operation is successful, orfalse
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()
Returnstrue
if the deque is empty, orfalse
otherwise.boolean isFull()
Returnstrue
if the deque is full, orfalse
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 toinsertFront
,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();
*/