641. Design Circular Deque

Problem Description

The given problem asks us to design a particular data structure known as a circular double-ended queue, often abbreviated as deque. A deque is a dynamic data structure that allows insertion and deletion of elements from both ends (front and back). The circular aspect of the queue implies that it is designed in such a way that the positions in the queue "wrap around" such that the last position is followed by the first, making the data structure continuous and circular.

Specifically, we need to implement a class `MyCircularDeque` with the following operations and their respective constraints:

1. `MyCircularDeque(int k)` - Constructor which initializes the deque with a fixed maximum size `k`.
2. `boolean insertFront(int value)` - Inserts an item at the front of the deque and returns `true` if successful or `false` if the deque is full.
3. `boolean insertLast(int value)` - Inserts an item at the rear of the deque and also returns `true` if successful or `false` if the deque is full.
4. `boolean deleteFront()` - Deletes an item from the front of the deque and returns `true` if the operation is successful or `false` if the deque is empty.
5. `boolean deleteLast()` - Deletes an item from the rear of the deque with the same return semantics as `deleteFront`.
6. `int getFront()` - Provides the front item from the deque, returning `-1` if the deque is empty.
7. `int getRear()` - Provides the rear item from the deque, again returning `-1` if the deque is empty.
8. `boolean isEmpty()` - Checks whether the deque is empty and returns `true` if it is, or `false` otherwise.
9. `boolean isFull()` - Checks if the deque is full, returning `true` in such a case, or `false` otherwise.

The challenge is to implement a deque that uses fixed-size storage but operates as if it were dynamic thanks to its circular nature.

Intuition

To implement the `MyCircularDeque`, the solution should handle the "circular" part efficiently. Consequently, we use an array of size `k` to represent the deque and two pointers, one for the `front` of the deque and the other to keep track of the number of elements in the deque, referred to as `size`. Since the deque is circular, we need a strategy to navigate circularly within the fixed-size list, which is accomplished by using modulo arithmetic when updating the `front` pointer or calculating the index for insertions and deletions.

The intuition behind using modulo arithmetic is that when we reach the end of the array and need to wrap around to the beginning (or vice versa when going backwards), the modulo operation `index % capacity` will give us the correct index within the bounds of our fixed-size array.

During insertion at the front, we adjust the `front` index by subtracting one (to move to the front) and then use modulo to wrap around if necessary. Similarly, when inserting at the rear, we calculate the index based on `front` and `size` values. Deletion operations adjust the `front` index or reduce the `size` while avoiding underflow or overflow conditions.

For checking if the deque is full, we compare the `size` with the `capacity`. The deque is empty when `size` is zero. Peek operations at the front or rear involve calculating the index based on the `front` and `size` and then accessing the array element at that index, taking care to return `-1` when the deque is empty.

Solution Approach

The solution approach involves creating a fixed-size array and using two pointers ('front' and 'size') to efficiently manage the operations of the circular deque. Below is a detailed explanation of each operation implemented in `MyCircularDeque` class:

1. Constructor (`__init__`): Initializes the deque with an array (`self.q`) of size `k`, `self.front` pointing to 0 (the initial position) and `self.size` to track the current number of elements. Also, `self.capacity` is set to `k` to enforce the fixed size of the deque.

2. Insert Front (`insertFront`): When a new element is to be inserted at the front, first check if the deque is full using `self.isFull()`. If not full:

• Adjust the `front` pointer one step backward using modulo operation: `self.front = (self.front - 1 + self.capacity) % self.capacity`.
• Insert the new element at the `front`.
• Increment `size` to reflect the addition.
3. Insert Last (`insertLast`): To insert a new element at the rear, check if the deque is full. If there is space:

• Calculate the new index for inserting the element at the rear using: `idx = (self.front + self.size) % self.capacity`.
• Place the new element at the calculated `idx`.
• Increase `size` accordingly.
4. Delete Front (`deleteFront`): To delete the front element, first ensure that the deque is not empty by checking `self.isEmpty()`. If it contains elements:

• Move the `front` pointer to the next element using the modulo operation: `self.front = (self.front + 1) % self.capacity`.
• Decrease `size`.
5. Delete Last (`deleteLast`): To remove the element at the rear, first check if the deque is empty. If it has elements:

• No need to move any pointers because the next insertLast will overwrite the last element.
• Simply decrement `size`.
6. Get Front (`getFront`): Returns the value at the front of the deque. If empty, return `-1`. If not, return `self.q[self.front]`.

7. Get Rear (`getRear`): Returns the last element of the deque. If empty, return `-1`. If not, calculate the index of the rear element using: `idx = (self.front + self.size - 1) % self.capacity`, and return the element at this index.

8. Is Empty (`isEmpty`): A simple check comparing `self.size` to 0 to determine if the deque is empty.

9. Is Full (`isFull`): Check if the deque has reached its capacity by comparing `self.size` with `self.capacity`.

This implementation takes advantage of the modular arithmetic to wrap around the fixed-size array, thereby emulating a circular behavior. The array serves as the primary data structure, while the front and size pointers control access to the circular deque's elements.

๐ช
Level Up Your
Algo Skills

Example Walkthrough

Let's go through an example to illustrate how the `MyCircularDeque` operates using the solution approach.

Suppose we initialize our circular deque with a maximum size of `3`.

1. Initialization:

• `MyCircularDeque circularDeque = new MyCircularDeque(3);` // set the size to be 3.
• This creates an array `q` of size `3`, sets `front` to `0`, `size` to `0`, and `capacity` to `3`.
2. Insert Last:

• `circularDeque.insertLast(1);` // returns true.
• The rear index is calculated as `(front + size) % capacity` which translates to `(0 + 0) % 3 = 0`.
• The number 1 is inserted at index `0`. The `size` is incremented to 1.
3. Insert Last:

• `circularDeque.insertLast(2);` // returns true.
• The rear index is now `(0 + 1) % 3 = 1`.
• The number 2 is inserted at index `1`. The `size` is incremented to 2.
4. Insert Front:

• `circularDeque.insertFront(3);` // returns true.
• `front` is adjusted backwards: `(front - 1 + capacity) % capacity` which translates to `(0 - 1 + 3) % 3 = 2`.
• The number 3 is inserted at the new `front` which is index `2`. The `size` is incremented to 3.
5. Insert Front:

• `circularDeque.insertFront(4);` // returns false, the deque is full.
• Since `size` equals `capacity` (3), no insertion is possible and operation returns false.
6. Get Rear:

• `circularDeque.getRear();` // returns 2.
• The rear index is `(front + size - 1) % capacity` which is `(2 + 3 - 1) % 3 = 1`.
• Index `1` has the value `2`, which is returned.
7. Is Full:

• `circularDeque.isFull();` // returns true.
• This checks if `size` equals `capacity` which is `3 == 3`, hence the deque is full.
8. Delete Last:

• `circularDeque.deleteLast();` // returns true.
• Removes the last element which is `2`. `size` is decremented to 2.
9. Insert Front:

• `circularDeque.insertFront(4);` // returns true.
• Adjust `front` backward to index `1` (new `front` after decrement is `(2 - 1) % 3 = 1`).
• Insert number `4` at index `1`. The `size` is incremented to 3.
10. Get Front:

• `circularDeque.getFront();` // returns 4.
• Since our `front` is currently at `1`, and that's where we inserted the value `4` last, `4` is what gets returned.

The above step-by-step operations show how each method manipulates the `front`, `size`, and sometimes the `capacity` to perform their respective actions, while maintaining the integrity of a circular double-ended queue with fixed size. These examples also demonstrate how the operations are interdependent affecting the overall state of the queue.

Python Solution

``````1class MyCircularDeque:
2    def __init__(self, k: int):
3        """
4        Initialize the deque with a fixed size of 'k'.
5        """
6        self.queue = [0] * k
8        self.size = 0
9        self.capacity = k
10
11    def insertFront(self, value: int) -> bool:
12        """
13        Add an item at the front of the deque.
14        Returns True if the operation is successful, otherwise False.
15        """
16        if self.isFull():
17            return False
18        if not self.isEmpty():
21        self.size += 1
22        return True
23
24    def insertLast(self, value: int) -> bool:
25        """
26        Add an item at the rear of the deque.
27        Returns True if the operation is successful, otherwise False.
28        """
29        if self.isFull():
30            return False
31        tail_index = (self.head + self.size) % self.capacity
32        self.queue[tail_index] = value
33        self.size += 1
34        return True
35
36    def deleteFront(self) -> bool:
37        """
38        Delete an item from the front of the deque.
39        Returns True if the operation is successful, otherwise False.
40        """
41        if self.isEmpty():
42            return False
44        self.size -= 1
45        return True
46
47    def deleteLast(self) -> bool:
48        """
49        Delete an item from the rear of the deque.
50        Returns True if the operation is successful, otherwise False.
51        """
52        if self.isEmpty():
53            return False
54        self.size -= 1
55        return True
56
57    def getFront(self) -> int:
58        """
59        Get the front item from the deque.
60        Returns the front item, or -1 if the deque is empty.
61        """
62        if self.isEmpty():
63            return -1
65
66    def getRear(self) -> int:
67        """
68        Get the last item from the deque.
69        Returns the last item, or -1 if the deque is empty.
70        """
71        if self.isEmpty():
72            return -1
73        tail_index = (self.head + self.size - 1) % self.capacity
74        return self.queue[tail_index]
75
76    def isEmpty(self) -> bool:
77        """
78        Check whether the deque is empty.
79        Returns True if the deque is empty, otherwise False.
80        """
81        return self.size == 0
82
83    def isFull(self) -> bool:
84        """
85        Check whether the deque is full.
86        Returns True if the deque is at full capacity, otherwise False.
87        """
88        return self.size == self.capacity
89
90# Example of how to use the MyCircularDeque class
91# circular_deque = MyCircularDeque(3)
92# print(circular_deque.insertLast(1))  # returns True
93# print(circular_deque.insertLast(2))  # returns True
94# print(circular_deque.insertFront(3)) # returns True
95# print(circular_deque.insertFront(4)) # returns False, the queue is full
96# print(circular_deque.getRear())      # returns 2
97# print(circular_deque.isFull())       # returns True
98# print(circular_deque.deleteLast())   # returns True
99# print(circular_deque.insertFront(4)) # returns True
100# print(circular_deque.getFront())     # returns 4
101``````

Java Solution

``````1class MyCircularDeque {
2    private int[] queue;
3    private int front;
4    private int size;
5    private int capacity;
6
7    /**
8     * Constructor to initialize the circular deque.
9     * @param k The capacity of the deque.
10     */
11    public MyCircularDeque(int k) {
12        queue = new int[k];
13        capacity = k;
14        front = 0;
15        size = 0;
16    }
17
18    /**
19     * Inserts an item at the front of the deque.
20     * @param value The value to insert.
21     * @return true if the operation is successful, false otherwise.
22     */
23    public boolean insertFront(int value) {
24        if (isFull()) {
25            return false;
26        }
27        front = (front - 1 + capacity) % capacity;
28        queue[front] = value;
29        size++;
30        return true;
31    }
32
33    /**
34     * Inserts an item at the rear of the deque.
35     * @param value The value to insert.
36     * @return true if the operation is successful, false otherwise.
37     */
38    public boolean insertLast(int value) {
39        if (isFull()) {
40            return false;
41        }
42        int rear = (front + size) % capacity;
43        queue[rear] = value;
44        size++;
45        return true;
46    }
47
48    /**
49     * Deletes an item from the front of the deque.
50     * @return true if the operation is successful, false otherwise.
51     */
52    public boolean deleteFront() {
53        if (isEmpty()) {
54            return false;
55        }
56        front = (front + 1) % capacity;
57        size--;
58        return true;
59    }
60
61    /**
62     * Deletes an item from the rear of the deque.
63     * @return true if the operation is successful, false otherwise.
64     */
65    public boolean deleteLast() {
66        if (isEmpty()) {
67            return false;
68        }
69        size--;
70        return true;
71    }
72
73    /**
74     * Gets the item from the front of the deque.
75     * @return The front item, or -1 if the deque is empty.
76     */
77    public int getFront() {
78        if (isEmpty()) {
79            return -1;
80        }
81        return queue[front];
82    }
83
84    /**
85     * Gets the item from the rear of the deque.
86     * @return The rear item, or -1 if the deque is empty.
87     */
88    public int getRear() {
89        if (isEmpty()) {
90            return -1;
91        }
92        int rear = (front + size - 1) % capacity;
93        return queue[rear];
94    }
95
96    /**
97     * Checks whether the circular deque is empty.
98     * @return true if the deque is empty, false otherwise.
99     */
100    public boolean isEmpty() {
101        return size == 0;
102    }
103
104    /**
105     * Checks whether the circular deque is full.
106     * @return true if the deque is full, false otherwise.
107     */
108    public boolean isFull() {
109        return size == capacity;
110    }
111}
112``````

C++ Solution

``````1#include <vector>
2
3class MyCircularDeque {
4private:
5    std::vector<int> deque;   // Underlying container for the deque elements
6    int frontIndex;           // Index of the front element
7    int currentSize;          // Current number of elements in the deque
8    int maxCapacity;          // Maximum capacity of the deque
9
10public:
11    // Constructor to initialize the deque with a fixed capacity.
12    MyCircularDeque(int k) : frontIndex(0), currentSize(0), maxCapacity(k) {
13        deque.assign(k, 0);    // Initialize deque with zeros, using the specified capacity.
14    }
15
16    // Inserts an element at the front of the deque. Returns true if the operation is successful.
17    bool insertFront(int value) {
18        if (isFull()) {
19            return false; // Cannot insert when the deque is full.
20        }
21        // When not empty, decrement frontIndex circularly.
22        if (!isEmpty()) {
23            frontIndex = (frontIndex - 1 + maxCapacity) % maxCapacity;
24        }
25        deque[frontIndex] = value; // Assign value to new front position.
26        ++currentSize;             // Increment the size of the deque.
27        return true;
28    }
29
30    // Inserts an element at the rear of the deque. Returns true if the operation is successful.
31    bool insertLast(int value) {
32        if (isFull()) {
33            return false; // Cannot insert when the deque is full.
34        }
35        int rearIndex = (frontIndex + currentSize) % maxCapacity; // Calculate rear index.
36        deque[rearIndex] = value;  // Assign value to the rear position.
37        ++currentSize;             // Increment the size of the deque.
38        return true;
39    }
40
41    // Deletes an element from the front of the deque. Returns true if the operation is successful.
42    bool deleteFront() {
43        if (isEmpty()) {
44            return false; // Cannot delete when the deque is empty.
45        }
46        frontIndex = (frontIndex + 1) % maxCapacity; // Move front index forward circularly.
47        --currentSize;          // Decrement the size of the deque.
48        return true;
49    }
50
51    // Deletes an element from the rear of the deque. Returns true if the operation is successful.
52    bool deleteLast() {
53        if (isEmpty()) {
54            return false; // Cannot delete when the deque is empty.
55        }
56        --currentSize;  // Decrement the size of the deque. The rear element gets 'removed'.
57        return true;
58    }
59
60    // Gets the front item from the deque. Returns -1 if the deque is empty.
61    int getFront() {
62        return isEmpty() ? -1 : deque[frontIndex];
63    }
64
65    // Gets the last item from the deque. Returns -1 if the deque is empty.
66    int getRear() {
67        if (isEmpty()) {
68            return -1; // Return -1 when the deque is empty.
69        }
70        // Calculate the index of the last element and return the value.
71        int rearIndex = (frontIndex + currentSize - 1) % maxCapacity;
72        return deque[rearIndex];
73    }
74
75    // Checks whether the deque is empty.
76    bool isEmpty() {
77        return currentSize == 0;
78    }
79
80    // Checks whether the deque is full.
81    bool isFull() {
82        return currentSize == maxCapacity;
83    }
84};
85
86/**
87 * Usage of MyCircularDeque:
88 * MyCircularDeque* obj = new MyCircularDeque(k);
89 * bool param_1 = obj->insertFront(value);
90 * bool param_2 = obj->insertLast(value);
91 * bool param_3 = obj->deleteFront();
92 * bool param_4 = obj->deleteLast();
93 * int param_5 = obj->getFront();
94 * int param_6 = obj->getRear();
95 * bool param_7 = obj->isEmpty();
96 * bool param_8 = obj->isFull();
97 */
98``````

Typescript Solution

``````1const DEQUE_SIZE: number = 0;
2let deque_vals: number[] = [];
3let deque_start: number = 0;
4let deque_end: number = 0;
5let deque_length: number = 0;
6
7// Initializes the data structure with a maximum size 'k'.
8function initialize(k: number): void {
9    deque_vals = new Array(k).fill(0);
10    DEQUE_SIZE = k;
11    deque_start = 0;
12    deque_end = 0;
13    deque_length = 0;
14}
15
16// Inserts an element at the front of the deque. Returns true if the operation is successful.
17function insertFront(value: number): boolean {
18    if (isFull()) {
19        return false;
20    }
21    deque_start = deque_start === 0 ? DEQUE_SIZE - 1 : deque_start - 1;
22    deque_vals[deque_start] = value;
23    deque_length++;
24    return true;
25}
26
27// Inserts an element at the rear of the deque. Returns true if the operation is successful.
28function insertLast(value: number): boolean {
29    if (isFull()) {
30        return false;
31    }
32    deque_vals[deque_end] = value;
33    deque_end = (deque_end + 1) % DEQUE_SIZE;
34    deque_length++;
35    return true;
36}
37
38// Deletes an element from the front of the deque. Returns true if the operation is successful.
39function deleteFront(): boolean {
40    if (isEmpty()) {
41        return false;
42    }
43    deque_start = (deque_start + 1) % DEQUE_SIZE;
44    deque_length--;
45    return true;
46}
47
48// Deletes an element from the rear of the deque. Returns true if the operation is successful.
49function deleteLast(): boolean {
50    if (isEmpty()) {
51        return false;
52    }
53    deque_end = deque_end === 0 ? DEQUE_SIZE - 1 : deque_end - 1;
54    deque_length--;
55    return true;
56}
57
58// Gets the front item from the deque. Returns -1 if the deque is empty.
59function getFront(): number {
60    if (isEmpty()) {
61        return -1;
62    }
63    return deque_vals[deque_start];
64}
65
66// Gets the last item from the deque. Returns -1 if the deque is empty.
67function getRear(): number {
68    if (isEmpty()) {
69        return -1;
70    }
71    let last_index = deque_end === 0 ? DEQUE_SIZE - 1 : deque_end - 1;
72    return deque_vals[last_index];
73}
74
75// Checks whether the deque is empty or not.
76function isEmpty(): boolean {
77    return deque_length === 0;
78}
79
80// Checks whether the deque is full or not.
81function isFull(): boolean {
82    return deque_length === DEQUE_SIZE;
83}
84``````

Time and Space Complexity

Time Complexity

• `__init__(k: int)`: The initialization of the deque takes `O(k)` time since it initializes a list of size `k` with zeros.
• `insertFront(value: int) -> bool`: Inserting an item at the front takes `O(1)` time as it is done by updating an index and inserting the value.
• `insertLast(value: int) -> bool`: Inserting an item at the rear is also done in `O(1)` time, which involves calculating the index and inserting the value.
• `deleteFront() -> bool`: Deleting an item from the front takes `O(1)` time due to the update of the `front` index and decreasing the size.
• `deleteLast() -> bool`: Deleting an item from the rear takes `O(1)` time since it only involves decrementing the size.
• `getFront() -> int`: Retrieving the front item is `O(1)` because it simply accesses the element at the `front` index.
• `getRear() -> int`: Retrieving the rear item is `O(1)` by calculating the index of the last item based on `front` and `size` and then accessing it.
• `isEmpty() -> bool`: Checking if the deque is empty takes `O(1)` time as it checks if the size is `0`.
• `isFull() -> bool`: Checking if the deque is full also takes `O(1)` time by comparing `size` and `capacity`.

All operations of the deque are implemented in a way that ensures a constant time complexity.

Space Complexity

• The overall space complexity for the deque is `O(k)`, which is required for storing the elements of the deque. The variables `front`, `size`, and `capacity` use constant additional space, hence they do not affect the overall space complexity.
๐
Become an
Algo Monster

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ
โTA ๐จโ๐ซ