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

Solution Explanation for Design Circular Deque

This problem requires designing a circular deque data structure. A circular deque is a double-ended queue where the beginning and end are connected, allowing for efficient insertion and deletion at both ends. The solution utilizes an array to implement this structure.

Approach

The core idea is to use a fixed-size array to store the deque elements and track the front and size of the deque. The front index points to the first element, and size indicates the number of elements currently in the deque. Circular behavior is achieved using the modulo operator (%) when calculating indices.

Key Data Structures:

• q: An array to store the deque elements.
• front: An integer representing the index of the front element.
• size: An integer representing the number of elements in the deque.
• capacity: An integer representing the maximum capacity of the deque.

Operations:

• insertFront(value): Inserts an element at the front of the deque. If the deque is full, it returns false. Otherwise, it adjusts the front index, places the value, and increments size.
• insertLast(value): Inserts an element at the rear of the deque. Similar logic as insertFront, but it calculates the rear index using (front + size) % capacity.
• deleteFront(): Deletes the front element. If the deque is empty, it returns false. Otherwise, it adjusts the front index and decrements size.
• deleteLast(): Deletes the last element. Similar logic as deleteFront, but it only decrements size as the front index doesn't change when deleting from the end.
• getFront(): Returns the front element. If the deque is empty, it returns -1.
• getRear(): Returns the rear element. If the deque is empty, it returns -1.
• isEmpty(): Returns true if the deque is empty (size == 0), otherwise false.
• isFull(): Returns true if the deque is full (size == capacity), otherwise false.

Time and Space Complexity

Time Complexity:

• All operations (insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull) have a time complexity of O(1). This is because they involve a constant number of operations regardless of the size of the deque.

Space Complexity:

• The space complexity is O(k), where k is the maximum size of the deque, due to the fixed-size array used to store the elements.

Code Explanation (Python Example)

The Python code implements the above logic directly. The modulo operator (%) ensures that the indices wrap around the circular buffer, simulating circular behavior. For example, self.front = (self.front - 1 + self.capacity) % self.capacity correctly handles wrapping when the front pointer reaches the beginning of the array. Similar logic is used for insertLast and getting the rear element.

The other methods are straightforward implementations of the operations described above, always checking for empty or full conditions before proceeding.

Conclusion

The provided solution efficiently implements a circular deque using a fixed-size array. The use of the modulo operator and careful tracking of front and size ensure that all operations maintain O(1) time complexity, making it suitable for applications requiring fast insertion and deletion at both ends of a queue-like structure.