Sponsored
Sponsored
This approach involves using a fixed-size array to represent the deque. We'll maintain two indices, front and rear, to manage the current front and last positions in the deque. Operations like insertions and deletions are performed by adjusting these indices while ensuring they wrap around using the modulo operation as necessary to remain within the array bounds.
Time Complexity: O(1) for each operation.
Space Complexity: O(k), where k is the capacity of the deque.
1class MyCircularDeque:
2 def __init__(self, k: int):
3 self.data = [-1] * k
4 self.front = 0
5 self.rear = 0
6 self.size = 0
7 self.capacity = k
8
9 def insertFront(self, value: int) -> bool:
10 if self.isFull():
11 return False
12 self.front = (self.front - 1 + self.capacity) % self.capacity
13 self.data[self.front] = value
14 self.size += 1
15 return True
16
17 def insertLast(self, value: int) -> bool:
18 if self.isFull():
19 return False
20 self.data[self.rear] = value
21 self.rear = (self.rear + 1) % self.capacity
22 self.size += 1
23 return True
24
25 def deleteFront(self) -> bool:
26 if self.isEmpty():
27 return False
28 self.front = (self.front + 1) % self.capacity
29 self.size -= 1
30 return True
31
32 def deleteLast(self) -> bool:
33 if self.isEmpty():
34 return False
35 self.rear = (self.rear - 1 + self.capacity) % self.capacity
36 self.size -= 1
37 return True
38
39 def getFront(self) -> int:
40 if self.isEmpty():
41 return -1
42 return self.data[self.front]
43
44 def getRear(self) -> int:
45 if self.isEmpty():
46 return -1
47 return self.data[(self.rear - 1 + self.capacity) % self.capacity]
48
49 def isEmpty(self) -> bool:
50 return self.size == 0
51
52 def isFull(self) -> bool:
53 return self.size == self.capacityPython solution uses a list to simulate the circular deque operations. It utilizes the modulo operation to keep track of the indices effectively and allows wrap-around of front and rear. The solution checks if the deque is full or empty before insertions or deletions, respectively.
This approach makes use of a doubly linked list to implement the deque. This is particularly effective because it offers dynamic memory usage which can grow or shrink with the number of elements, instead of relying on a pre-allocated fixed-size structure as with arrays.
Time Complexity: O(1) for all operations.
Space Complexity: O(n), where n is the number of elements currently in the deque (potentially more efficient if n is much less than the initial capacity).
1using namespace std;
class Node {
public:
int value;
Node* next;
Node* prev;
Node(int value): value(value), next(nullptr), prev(nullptr) {}
};
class MyCircularDeque {
Node* front;
Node* rear;
int size;
int capacity;
public:
MyCircularDeque(int k): size(0), capacity(k), front(nullptr), rear(nullptr) {}
bool insertFront(int value) {
if (isFull()) return false;
Node* node = new Node(value);
node->next = front;
if (front != nullptr) front->prev = node;
front = node;
if (rear == nullptr) rear = node;
size++;
return true;
}
bool insertLast(int value) {
if (isFull()) return false;
Node* node = new Node(value);
node->prev = rear;
if (rear != nullptr) rear->next = node;
rear = node;
if (front == nullptr) front = node;
size++;
return true;
}
bool deleteFront() {
if (isEmpty()) return false;
Node* temp = front;
front = front->next;
if (front != nullptr) front->prev = nullptr;
else rear = nullptr;
delete temp;
size--;
return true;
}
bool deleteLast() {
if (isEmpty()) return false;
Node* temp = rear;
rear = rear->prev;
if (rear != nullptr) rear->next = nullptr;
else front = nullptr;
delete temp;
size--;
return true;
}
int getFront() {
return isEmpty() ? -1 : front->value;
}
int getRear() {
return isEmpty() ? -1 : rear->value;
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == capacity;
}
};The C++ implementation uses a doubly linked list, making it flexible in memory usage. Each operation—whether insertion or deletion—adjusts pointers accordingly, ensuring seamless front or rear element manipulation.