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 constructor(k) {
3 this.data = new Array(k).fill(-1);
4 this.front = 0;
5 this.rear = 0;
6 this.size = 0;
7 this.capacity = k;
8 }
9
10 insertFront(value) {
11 if (this.isFull()) return false;
12 this.front = (this.front - 1 + this.capacity) % this.capacity;
13 this.data[this.front] = value;
14 this.size++;
15 return true;
16 }
17
18 insertLast(value) {
19 if (this.isFull()) return false;
20 this.data[this.rear] = value;
21 this.rear = (this.rear + 1) % this.capacity;
22 this.size++;
23 return true;
24 }
25
26 deleteFront() {
27 if (this.isEmpty()) return false;
28 this.front = (this.front + 1) % this.capacity;
29 this.size--;
30 return true;
31 }
32
33 deleteLast() {
34 if (this.isEmpty()) return false;
35 this.rear = (this.rear - 1 + this.capacity) % this.capacity;
36 this.size--;
37 return true;
38 }
39
40 getFront() {
41 if (this.isEmpty()) return -1;
42 return this.data[this.front];
43 }
44
45 getRear() {
46 if (this.isEmpty()) return -1;
47 return this.data[(this.rear - 1 + this.capacity) % this.capacity];
48 }
49
50 isEmpty() {
51 return this.size === 0;
52 }
53
54 isFull() {
55 return this.size === this.capacity;
56 }
57}In the JavaScript version, a fixed-size array with circular indexing is used. Insertions and deletions manipulate front and rear pointers using a wraparound logic suitable for the circular nature of the deque.
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).
1
Python'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.