## Algorithm

Problem Name: 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`.

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class MyCircularDeque {

private Node tail;
private int k;
private int currSize;

public MyCircularDeque(int k) {
this.k = k;
this.currSize = 0;
this.head = new Node(-1);
this.tail = new Node(-1);
}

public boolean insertFront(int value) {
if (isFull()) {
return false;
}
Node node = new Node(value);
currSize++;
return true;
}

public boolean insertLast(int value) {
if (isFull()) {
return false;
}
Node node = new Node(value);
Node prevToTail = tail.prev;
tail.prev = node;
node.next = tail;
prevToTail.next = node;
node.prev = prevToTail;
currSize++;
return true;
}

public boolean deleteFront() {
if (isEmpty()) {
return false;
}
Node toDelete = head.next;
deleteNode(toDelete);
return true;
}

public boolean deleteLast() {
if (isEmpty()) {
return false;
}
Node toDelete = tail.prev;
deleteNode(toDelete);
return true;
}

public int getFront() {
if (isEmpty()) {
return -1;
}
}

public int getRear() {
if (isEmpty()) {
return -1;
}
return tail.prev.val;
}

public boolean isEmpty() {
return currSize == 0;
}

public boolean isFull() {
return currSize == k;
}

private void deleteNode(Node node) {
Node prevToNode = node.prev;
Node nextToNode = node.next;
prevToNode.next = nextToNode;
nextToNode.prev = prevToNode;
currSize--;
}

private static class Node {
int val;
Node next;
Node prev;

public Node(int val) {
this.val = val;
}
}
}
``````
Copy The Code &

Input

cmd
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []]

Output

cmd
[null, true, true, true, false, 2, true, true, true, 4]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const MyCircularDeque = function(k) {
this.q = []
this.k = k
};

MyCircularDeque.prototype.insertFront = function(value) {
if(this.q.length < this.k) {
this.q.unshift(value)
return true
}
return false
};

MyCircularDeque.prototype.insertLast = function(value) {
if(this.q.length  <  this.k) {
this.q.push(value)
return true
}
return false
};

MyCircularDeque.prototype.deleteFront = function() {
if(this.q.length) {
this.q.shift()
return true
}
return false
};

MyCircularDeque.prototype.deleteLast = function() {
if(this.q.length) {
this.q.pop()
return true
}
return false
};

MyCircularDeque.prototype.getFront = function() {
return this.q[0] === undefined ? -1 : this.q[0]
};

MyCircularDeque.prototype.getRear = function() {
return this.q[this.q.length - 1] === undefined ? -1 : this.q[this.q.length - 1]
};

MyCircularDeque.prototype.isEmpty = function() {
return this.q.length === 0
};

MyCircularDeque.prototype.isFull = function(> {
return this.q.length === this.k
};
``````
Copy The Code &

Input

cmd
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []]

Output

cmd
[null, true, true, true, false, 2, true, true, true, 4]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Node:
def __init__(self, value):
self.val = value
self.next = self.pre = None

class MyCircularDeque:

def __init__(self, k):
self.head = self.tail = Node(-1)
self.size = k
self.curSize = 0

def add(self, value, preNode):
new = Node(value)
new.pre = preNode
new.next = preNode.next
new.pre.next = new.next.pre = new
self.curSize += 1

def remove(self, preNode):
node = preNode.next
node.pre.next = node.next
node.next.pre = node.pre
self.curSize -= 1

def insertFront(self, value):
if self.curSize < self.size:
return True
return False

def insertLast(self, value):
if self.curSize < self.size:
return True
return False

def deleteFront(self):
if self.curSize:
return True
return False

def deleteLast(self):
if self.curSize:
self.remove(self.tail.pre.pre)
return True
return False

def getFront(self):
if self.curSize:
return -1

def getRear(self):
if self.curSize:
return self.tail.pre.val
return -1

def isEmpty(self):
return self.curSize == 0

def isFull(self):
return self.curSize == self.size
``````
Copy The Code &

Input

cmd
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"] [[3], [1], [2], [3], [4], [], [], [], [4], []]

Output

cmd
[null, true, true, true, false, 2, true, true, true, 4]