Problem
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 1
/**
* @param {number} k
*/
var MyCircularDeque = function(k) {
this.limit = k;
this.count = 0;
this.front = null;
this.last = null;
};
/**
* @param {number} value
* @return {boolean}
*/
MyCircularDeque.prototype.insertFront = function(value) {
if (this.count === this.limit) return false;
var node = {
value,
prev: null,
next: null,
};
if (!this.front) {
this.front = node;
this.last = node;
} else {
node.next = this.front;
this.front.prev = node;
this.front = node;
}
this.count += 1;
return true;
};
/**
* @param {number} value
* @return {boolean}
*/
MyCircularDeque.prototype.insertLast = function(value) {
if (this.count === this.limit) return false;
var node = {
value,
prev: null,
next: null,
};
if (!this.last) {
this.front = node;
this.last = node;
} else {
node.prev = this.last;
this.last.next = node;
this.last = node;
}
this.count += 1;
return true;
};
/**
* @return {boolean}
*/
MyCircularDeque.prototype.deleteFront = function() {
if (!this.front) return false;
if (this.front === this.last) {
this.front = null;
this.last = null;
} else {
this.front.next.prev = null;
this.front = this.front.next;
}
this.count -= 1;
return true;
};
/**
* @return {boolean}
*/
MyCircularDeque.prototype.deleteLast = function() {
if (!this.last) return false;
if (this.front === this.last) {
this.front = null;
this.last = null;
} else {
this.last.prev.next = null;
this.last = this.last.prev;
}
this.count -= 1;
return true;
};
/**
* @return {number}
*/
MyCircularDeque.prototype.getFront = function() {
return this.front ? this.front.value : -1;
};
/**
* @return {number}
*/
MyCircularDeque.prototype.getRear = function() {
return this.last ? this.last.value : -1;
};
/**
* @return {boolean}
*/
MyCircularDeque.prototype.isEmpty = function() {
return this.count === 0;
};
/**
* @return {boolean}
*/
MyCircularDeque.prototype.isFull = function() {
return this.count === this.limit;
};
/**
* Your MyCircularDeque object will be instantiated and called as such:
* var obj = new MyCircularDeque(k)
* var param_1 = obj.insertFront(value)
* var param_2 = obj.insertLast(value)
* var param_3 = obj.deleteFront()
* var param_4 = obj.deleteLast()
* var param_5 = obj.getFront()
* var param_6 = obj.getRear()
* var param_7 = obj.isEmpty()
* var param_8 = obj.isFull()
*/
Explain:
nope.
Complexity:
- Time complexity : O(1).
- Space complexity : O(n).
Solution 2
/**
* @param {number} k
*/
var MyCircularDeque = function(k) {
this.limit = k;
this.count = 0;
this.arr = Array(k);
this.front = -1;
this.last = -1;
};
/**
* @param {number} value
* @return {boolean}
*/
MyCircularDeque.prototype.insertFront = function(value) {
if (this.count === this.limit) return false;
if (this.count === 0) {
this.front = 0;
this.last = 0;
} else {
this.front -= 1;
if (this.front < 0) {
this.front += this.arr.length;
}
}
this.arr[this.front] = value;
this.count += 1;
return true;
};
/**
* @param {number} value
* @return {boolean}
*/
MyCircularDeque.prototype.insertLast = function(value) {
if (this.count === this.limit) return false;
if (this.count === 0) {
this.front = 0;
this.last = 0;
} else {
this.last += 1;
if (this.last >= this.arr.length) {
this.last -= this.arr.length;
}
}
this.arr[this.last] = value;
this.count += 1;
return true;
};
/**
* @return {boolean}
*/
MyCircularDeque.prototype.deleteFront = function() {
if (this.count === 0) return false;
if (this.count === 1) {
this.front = -1;
this.last = -1;
} else {
this.front += 1;
if (this.front >= this.arr.length) {
this.front -= this.arr.length;
}
}
this.count -= 1;
return true;
};
/**
* @return {boolean}
*/
MyCircularDeque.prototype.deleteLast = function() {
if (this.count === 0) return false;
if (this.count === 1) {
this.front = -1;
this.last = -1;
} else {
this.last -= 1;
if (this.last < 0) {
this.last += this.arr.length;
}
}
this.count -= 1;
return true;
};
/**
* @return {number}
*/
MyCircularDeque.prototype.getFront = function() {
return this.front === -1 ? -1 : this.arr[this.front];
};
/**
* @return {number}
*/
MyCircularDeque.prototype.getRear = function() {
return this.last === -1 ? -1 : this.arr[this.last];
};
/**
* @return {boolean}
*/
MyCircularDeque.prototype.isEmpty = function() {
return this.count === 0;
};
/**
* @return {boolean}
*/
MyCircularDeque.prototype.isFull = function() {
return this.count === this.limit;
};
/**
* Your MyCircularDeque object will be instantiated and called as such:
* var obj = new MyCircularDeque(k)
* var param_1 = obj.insertFront(value)
* var param_2 = obj.insertLast(value)
* var param_3 = obj.deleteFront()
* var param_4 = obj.deleteLast()
* var param_5 = obj.getFront()
* var param_6 = obj.getRear()
* var param_7 = obj.isEmpty()
* var param_8 = obj.isFull()
*/
Explain:
nope.
Complexity:
- Time complexity : O(1).
- Space complexity : O(n).