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.
1 private int[] data;
private int front;
private int rear;
private int size;
private int capacity;
public MyCircularDeque(int k) {
data = new int[k];
front = 0;
rear = 0;
size = 0;
capacity = k;
}
public bool InsertFront(int value) {
if (IsFull()) return false;
front = (front - 1 + capacity) % capacity;
data[front] = value;
size++;
return true;
}
public bool InsertLast(int value) {
if (IsFull()) return false;
data[rear] = value;
rear = (rear + 1) % capacity;
size++;
return true;
}
public bool DeleteFront() {
if (IsEmpty()) return false;
front = (front + 1) % capacity;
size--;
return true;
}
public bool DeleteLast() {
if (IsEmpty()) return false;
rear = (rear - 1 + capacity) % capacity;
size--;
return true;
}
public int GetFront() {
if (IsEmpty()) return -1;
return data[front];
}
public int GetRear() {
if (IsEmpty()) return -1;
return data[(rear - 1 + capacity) % capacity];
}
public bool IsEmpty() {
return size == 0;
}
public bool IsFull() {
return size == capacity;
}
}The C# solution implements the circular deque using an array, managing the front and rear positions using indices and supports circular adjustments when reaching the end of the array.
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#include <stdbool.h>
2#include <stdlib.h>
3
4typedef struct Node {
5 int value;
6 struct Node *next;
7 struct Node *prev;
8} Node;
9
10typedef struct {
11 Node *front;
12 Node *rear;
13 int size;
14 int capacity;
15} MyCircularDeque;
16
17MyCircularDeque* myCircularDequeCreate(int k) {
18 MyCircularDeque* obj = (MyCircularDeque*) malloc(sizeof(MyCircularDeque));
19 obj->front = obj->rear = NULL;
20 obj->size = 0;
21 obj->capacity = k;
22 return obj;
23}
24
25bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
26 if (obj->size == obj->capacity) return false;
27 Node *node = (Node*) malloc(sizeof(Node));
28 node->value = value;
29 node->next = obj->front;
30 node->prev = NULL;
31 if (obj->front != NULL) {
32 obj->front->prev = node;
33 }
34 obj->front = node;
35 if (obj->rear == NULL) {
36 obj->rear = node;
37 }
38 obj->size++;
39 return true;
40}
41
42bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
43 if (obj->size == obj->capacity) return false;
44 Node *node = (Node*) malloc(sizeof(Node));
45 node->value = value;
46 node->prev = obj->rear;
47 node->next = NULL;
48 if (obj->rear != NULL) {
49 obj->rear->next = node;
50 }
51 obj->rear = node;
52 if (obj->front == NULL) {
53 obj->front = node;
54 }
55 obj->size++;
56 return true;
57}
58
59bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
60 if (obj->size == 0) return false;
61 Node *temp = obj->front;
62 obj->front = obj->front->next;
63 if (obj->front != NULL) {
64 obj->front->prev = NULL;
65 } else {
66 obj->rear = NULL;
67 }
68 free(temp);
69 obj->size--;
70 return true;
71}
72
73bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
74 if (obj->size == 0) return false;
75 Node *temp = obj->rear;
76 obj->rear = obj->rear->prev;
77 if (obj->rear != NULL) {
78 obj->rear->next = NULL;
79 } else {
80 obj->front = NULL;
81 }
82 free(temp);
83 obj->size--;
84 return true;
85}
86
87int myCircularDequeGetFront(MyCircularDeque* obj) {
88 return (obj->size == 0) ? -1 : obj->front->value;
89}
90
91int myCircularDequeGetRear(MyCircularDeque* obj) {
92 return (obj->size == 0) ? -1 : obj->rear->value;
93}
94
95bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
96 return obj->size == 0;
97}
98
99bool myCircularDequeIsFull(MyCircularDeque* obj) {
100 return obj->size == obj->capacity;
101}
102
103void myCircularDequeFree(MyCircularDeque* obj) {
104 while (obj->front != NULL) {
105 Node *temp = obj->front;
106 obj->front = obj->front->next;
107 free(temp);
108 }
109 free(obj);
110}Using a linked list in C allows dynamic memory management for each element in the deque. Nodes are created or deleted dynamically, with pointers next and prev facilitating easy front and rear operations.