641. Design Circular Deque

Difficulty:
Related Topics:
Similar Questions:

Problem

Design your implementation of the circular double-ended queue (deque).

Implement the MyCircularDeque class:

  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:

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:

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: