Design Circular Deque

Problem Statement

The task is to design a circular double-ended queue (deque) using a class called MyCircularDeque. This custom data structure allows you to:

• Initialize the deque with a specified maximum size using the constructor MyCircularDeque(int k).
• Add an item at the front of the deque with insertFront().
• Add an item at the rear of the deque with insertLast().
• Remove an item from the front of the deque with deleteFront().
• Remove an item from the rear of the deque with deleteLast().
• Retrieve the item at the front of the deque with getFront(), which returns -1 if the deque is empty.
• Retrieve the item at the rear of the deque with getRear(), which also returns -1 if the deque is empty.
• Check if the deque is empty using isEmpty(), which returns true if it is empty and false otherwise.
• Check if the deque is full using isFull(), which returns true if it is full and false otherwise.

This implementation must handle up to 2000 operations efficiently and maintain all properties typical to a deque, with the added complexity that it is circular, meaning the ends are conceptually connected.

Examples

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.

Approach and Intuition

1. Data Structure Setup:

   • The fundamental structure will likely consist of an array to simulate the deque since direct access to the front and rear elements is crucial.
   • Two pointers or indices (for the front and rear) will help manage where the next elements will be inserted or removed.

2. Method Implementations:

   • insertFront and insertLast need boundary checks to see if the deque is full before inserting a new item.
   • deleteFront and deleteLast should check if the deque is empty before attempting to remove an item.
   • For the isFull method, a comparison of the number of items in the deque and its maximum capacity will be necessary.
   • The isEmpty method simply checks if the front is in the same position as the rear and that position holds no valid item.
   • getFront and getRear return values based on the front and rear pointers but handle cases where the deque might be empty.

3. Circularity Management:

   • As operations may cause the front or rear indices to potentially "wrap around" the fixed-size array boundary, modular arithmetic can be used (mod k) during insertions and deletions to rotate back to the start or end of the array.

4. Example Walkthrough:

   • The initialization assigns an array of size k with all elements set to indicate inactive/deleted slots.
   • Insertions adjust the respective pointer, insert the value, and handle the wrapping if needed.
   • Deletions make the slot inactive and adjust the pointer with modular adjustments for wrapping.
   • Status checks directly derive from pointer positions and active counts.

This implementation highlights a tailored approach to efficiently manage inserts and deletes from both ends of a dynamically adjusting circular structure. The operations are designed to run in constant time O(1), crucial for high-performance requirements where rapid access and modifications are frequent.

Solutions

class CircularDeque {
private:
    vector<int> deque;
    int head;
    int tail;
    int count;
    int maxCapacity;
    
public:
    CircularDeque(int k) {
        deque = vector<int>(k);
        count = 0;
        maxCapacity = k;
        head = 0;
        tail = k - 1;
    }
    
    bool insertFront(int value) {
        if (isFull()) return false;
        head = (head - 1 + maxCapacity) % maxCapacity;
        deque[head] = value;
        count++;
        return true;
    }
    
    bool insertLast(int value) {
        if (isFull()) return false;
        tail = (tail + 1) % maxCapacity;
        deque[tail] = value;
        count++;
        return true;
    }
    
    bool deleteFront() {
        if (isEmpty()) return false;
        head = (head + 1) % maxCapacity;
        count--;
        return true;
    }
    
    bool deleteLast() {
        if (isEmpty()) return false;
        tail = (tail - 1 + maxCapacity) % maxCapacity;
        count--;
        return true;
    }
    
    int getFront() {
        if (isEmpty()) return -1;
        return deque[head];
    }
    
    int getRear() {
        if (isEmpty()) return -1;
        return deque[tail];
    }
    
    bool isEmpty() { return count == 0; }
    
    bool isFull() { return count == maxCapacity; }
};