Design Circular Queue

Description

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

Your implementation should support following operations:

• MyCircularDeque(k): Constructor, set the size of the deque to be k.

• insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.

• insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.

• deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.

• deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.

• getFront(): Gets the front item from the Deque. If the deque is empty, return -1.

• getRear(): Gets the last item from Deque. If the deque is empty, return -1.

• isEmpty(): Checks whether Deque is empty or not.

• isFull(): Checks whether Deque is full or not.

Example:

MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1);			// return true
circularDeque.insertLast(2);			// return true
circularDeque.insertFront(3);			// return true
circularDeque.insertFront(4);			// return false, the queue is full
circularDeque.getRear();  			// return 2
circularDeque.isFull();				// return true
circularDeque.deleteLast();			// return true
circularDeque.insertFront(4);			// return true
circularDeque.getFront();			// return 4

Note:

• All values will be in the range of [0, 1000].

• The number of operations will be in the range of [1, 1000].

• Please do not use the built-in Deque library.

Solution

class MyCircularQueue {
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k): v(vector<int>(k)) {
        i = 0;
        n = 0;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if(n < v.size()) {
            v[(i + n) % v.size()] = value;
            ++n;
            return true;
        }
        return false;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if(n > 0) {
            i = (i + 1) % v.size();
            --n;
            return true;
        }
        return false;
    }
    
    /** Get the front item from the queue. */
    int Front() {
        if(n > 0)
            return v[i];
        return -1;
    }
    
    /** Get the last item from the queue. */
    int Rear() {
        if(n > 0)
            return v[(i + n - 1) % v.size()];
        return -1;
    }
    
    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        return n == 0;
    }
    
    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        return n == v.size();
    }

    vector<int> v;
    int i;
    int n;
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */