LeetCode641. Design Circular Deque

[wupangyen]

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.

[wupangyen]

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

[wupangyen]

class MyCircularDeque {

int front, rear, size;
int[] array;

/** Initialize your data structure here. Set the size of the deque to be k. */
public MyCircularDeque(int k) {
    rear = 0;
    size = 0;
    front = k - 1;
    array = new int[k];

}

/** Adds an item at the front of Deque. Return true if the operation is successful. */
public boolean insertFront(int value) {

    if(!isFull()){
        array[front] = value;
        front = (front -1 + array.length) % array.length;

        size += 1;
        return true;
    }
    else{
        return false;
    }
}

/** Adds an item at the rear of Deque. Return true if the operation is successful. */
public boolean insertLast(int value) {
    // is like enqueue in the regular queue

    if(!isFull()){

         array[rear] = value;
        rear = (rear + 1 ) % array.length;

        size += 1;
        return true;

    }
    else{
        return false;
    }

}

/** Deletes an item from the front of Deque. Return true if the operation is successful. */
public boolean deleteFront() {

    if(!isEmpty()){

        front = (front + 1) % array.length;
        size-=1;
        return true;

    }
    else{
        return false;
    }
}

/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
public boolean deleteLast() {
    if(!isEmpty()){
        rear = (rear -1 + array.length ) % array.length;
        size-= 1;
        return true;
    }
    else{
        return false;
    }
}

/** Get the front item from the deque. */
public int getFront() {
    if(isEmpty()){
        return -1;
    }
    else{
        return array[(front + 1) % array.length];
    }

}

/** Get the last item from the deque. */
public int getRear() {
    if(isEmpty()){
        return -1;
    }
    else{
        return array[(rear - 1 + array.length) % array.length];
    }

}

/** Checks whether the circular deque is empty or not. */
public boolean isEmpty() {
    return size == 0;

}

/** Checks whether the circular deque is full or not. */
public boolean isFull() {
    return size == array.length;   
}

}

/**

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

[wupangyen]

https://leetcode.com/problems/design-circular-deque/discuss/155209/c%2B%2B-99-ring-buffer-no-edge-cases.-fb-interviewer-really-loves-it.-easy-to-impl-in-4mins.-cheers!