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.
using namespace std;
class MyCircularDeque {
vector<int> data;
int front;
int rear;
int size;
int capacity;
public:
MyCircularDeque(int k) : data(k), front(0), rear(0), size(0), capacity(k) {}
bool insertFront(int value) {
if (isFull()) return false;
front = (front - 1 + capacity) % capacity;
data[front] = value;
size++;
return true;
}
bool insertLast(int value) {
if (isFull()) return false;
data[rear] = value;
rear = (rear + 1) % capacity;
size++;
return true;
}
bool deleteFront() {
if (isEmpty()) return false;
front = (front + 1) % capacity;
size--;
return true;
}
bool deleteLast() {
if (isEmpty()) return false;
rear = (rear - 1 + capacity) % capacity;
size--;
return true;
}
int getFront() {
if (isEmpty()) return -1;
return data[front];
}
int getRear() {
if (isEmpty()) return -1;
return data[(rear - 1 + capacity) % capacity];
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == capacity;
}
};C++ implementation utilizes a vector for the circular array. All deque operations are facilitated using vector functions. Insertions and deletions adjust the front and rear indices while checking the size for fullness or emptiness.
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).
1class Node:
2 def __init__(self, value=None):
3 self.value = value
4 self.next = None
5 self.prev = None
6
7class MyCircularDeque:
8 def __init__(self, k):
9 self.front = None
10 self.rear = None
11 self.size = 0
12 self.capacity = k
13
14 def insertFront(self, value):
15 if self.isFull():
16 return False
17 node = Node(value)
18 node.next = self.front
19 if self.front:
20 self.front.prev = node
21 self.front = node
22 if self.rear is None:
23 self.rear = node
24 self.size += 1
25 return True
26
27 def insertLast(self, value):
28 if self.isFull():
29 return False
30 node = Node(value)
31 node.prev = self.rear
32 if self.rear:
33 self.rear.next = node
34 self.rear = node
35 if self.front is None:
36 self.front = node
37 self.size += 1
38 return True
39
40 def deleteFront(self):
41 if self.isEmpty():
42 return False
43 self.front = self.front.next
44 if self.front:
45 self.front.prev = None
46 else:
47 self.rear = None
48 self.size -= 1
49 return True
50
51 def deleteLast(self):
52 if self.isEmpty():
53 return False
54 self.rear = self.rear.prev
55 if self.rear:
56 self.rear.next = None
57 else:
58 self.front = None
59 self.size -= 1
60 return True
61
62 def getFront(self):
63 return -1 if self.isEmpty() else self.front.value
64
65 def getRear(self):
66 return -1 if self.isEmpty() else self.rear.value
67
68 def isEmpty(self):
69 return self.size == 0
70
71 def isFull(self):
72 return self.size == self.capacityPython's linked list approach enables a flexible allocation for deques with nodes connecting backward and forward, simplifying insertions/deletions by just adjusting node pointers. Each operation reacts in constant time, not hindered by array resizing constraints.