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#include <stdbool.h>
2
3typedef struct {
4 int* data;
5 int front;
6 int rear;
7 int size;
8 int capacity;
9} MyCircularDeque;
10
11MyCircularDeque* myCircularDequeCreate(int k) {
12 MyCircularDeque* obj = (MyCircularDeque*) malloc(sizeof(MyCircularDeque));
13 obj->data = (int*) malloc(sizeof(int) * k);
14 obj->front = 0;
15 obj->rear = 0;
16 obj->size = 0;
17 obj->capacity = k;
18 return obj;
19}
20
21bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) {
22 if (obj->size == obj->capacity) return false;
23 obj->front = (obj->front - 1 + obj->capacity) % obj->capacity;
24 obj->data[obj->front] = value;
25 obj->size++;
26 return true;
27}
28
29bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) {
30 if (obj->size == obj->capacity) return false;
31 obj->data[obj->rear] = value;
32 obj->rear = (obj->rear + 1) % obj->capacity;
33 obj->size++;
34 return true;
35}
36
37bool myCircularDequeDeleteFront(MyCircularDeque* obj) {
38 if (obj->size == 0) return false;
39 obj->front = (obj->front + 1) % obj->capacity;
40 obj->size--;
41 return true;
42}
43
44bool myCircularDequeDeleteLast(MyCircularDeque* obj) {
45 if (obj->size == 0) return false;
46 obj->rear = (obj->rear - 1 + obj->capacity) % obj->capacity;
47 obj->size--;
48 return true;
49}
50
51int myCircularDequeGetFront(MyCircularDeque* obj) {
52 if (obj->size == 0) return -1;
53 return obj->data[obj->front];
54}
55
56int myCircularDequeGetRear(MyCircularDeque* obj) {
57 if (obj->size == 0) return -1;
58 return obj->data[(obj->rear - 1 + obj->capacity) % obj->capacity];
59}
60
61bool myCircularDequeIsEmpty(MyCircularDeque* obj) {
62 return obj->size == 0;
63}
64
65bool myCircularDequeIsFull(MyCircularDeque* obj) {
66 return obj->size == obj->capacity;
67}
68
69void myCircularDequeFree(MyCircularDeque* obj) {
70 free(obj->data);
71 free(obj);
72}This implementation uses a circular array to manage the deque operations. The array is of fixed size, calculated by the given capacity, and follows the circular method to use the front and rear indices effectively. The modulo operation is crucial to wrap around these indices and prevent them from exceeding array bounds.
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
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.