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.
The Java solution uses an array and manages the front and rear indices to perform the required deque operations. It checks for both capacity and current size to determine the ability to insert or delete elements.
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 int value;
3 Node next;
4 Node prev;
5 Node(int value) {
6 this.value = value;
7 }
8}
9
10class MyCircularDeque {
11 Node front;
12 Node rear;
13 int size;
14 int capacity;
15
16 public MyCircularDeque(int k) {
17 this.size = 0;
18 this.capacity = k;
19 this.front = this.rear = null;
20 }
21
22 public boolean insertFront(int value) {
23 if (isFull()) return false;
24 Node node = new Node(value);
25 node.next = front;
26 if (front != null) front.prev = node;
27 front = node;
28 if (rear == null) rear = node;
29 size++;
30 return true;
31 }
32
33 public boolean insertLast(int value) {
34 if (isFull()) return false;
35 Node node = new Node(value);
36 node.prev = rear;
37 if (rear != null) rear.next = node;
38 rear = node;
39 if (front == null) front = node;
40 size++;
41 return true;
42 }
43
44 public boolean deleteFront() {
45 if (isEmpty()) return false;
46 front = front.next;
47 if (front != null) front.prev = null;
48 else rear = null;
49 size--;
50 return true;
51 }
52
53 public boolean deleteLast() {
54 if (isEmpty()) return false;
55 rear = rear.prev;
56 if (rear != null) rear.next = null;
57 else front = null;
58 size--;
59 return true;
60 }
61
62 public int getFront() {
63 return isEmpty() ? -1 : front.value;
64 }
65
66 public int getRear() {
67 return isEmpty() ? -1 : rear.value;
68 }
69
70 public boolean isEmpty() {
71 return size == 0;
72 }
73
74 public boolean isFull() {
75 return size == capacity;
76 }
77}The Java implementation exploits linked list nodes to hold deque data, which provides benefits of dynamic memory adjustments, ensuring operations like adding or removing at both ends are simple and efficient in terms of pointer rearrangements.