1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
// 641. Design Circular Deque
#include "leetcode.h"
/*
* design your implementation of the circular double ended queue (deque).
* implement the 'MyCircularDeque' class
*/
struct node {
struct node *next;
struct node *prev;
int val;
};
typedef struct {
struct node *head;
struct node *tail;
int size;
int max_size;
} MyCircularDeque;
MyCircularDeque *myCircularDequeCreate(int k) {
MyCircularDeque *dq = (MyCircularDeque *)malloc(sizeof(MyCircularDeque));
dq->head = (struct node *)malloc(sizeof(struct node));
dq->tail = (struct node *)malloc(sizeof(struct node));
dq->head->next = dq->tail;
dq->head->prev = NULL;
dq->tail->prev = dq->head;
dq->tail->next = NULL;
dq->size = 0;
dq->max_size = k;
return dq;
}
bool myCircularDequeInsertFront(MyCircularDeque *obj, int value) {
if (obj->size == obj->max_size)
return false;
struct node *n = (struct node *)malloc(sizeof(struct node));
n->val = value;
n->prev = obj->head;
n->next = obj->head->next;
obj->head->next->prev = n;
obj->head->next = n;
obj->size++;
return true;
}
bool myCircularDequeInsertLast(MyCircularDeque *obj, int value) {
if (obj->size == obj->max_size)
return false;
struct node *n = (struct node *)malloc(sizeof(struct node));
n->val = value;
n->prev = obj->tail->prev;
n->next = obj->tail;
obj->tail->prev->next = n;
obj->tail->prev = n;
obj->size++;
return true;
}
bool myCircularDequeDeleteFront(MyCircularDeque *obj) {
if (!obj->size)
return false;
struct node *back = obj->head->next;
obj->head->next->next->prev = obj->head;
obj->head->next = obj->head->next->next;
obj->size--;
free(back);
return true;
}
bool myCircularDequeDeleteLast(MyCircularDeque *obj) {
if (!obj->size)
return false;
struct node *back = obj->tail->prev;
obj->tail->prev->prev->next = obj->tail;
obj->tail->prev = obj->tail->prev->prev;
obj->size--;
free(back);
return true;
}
int myCircularDequeGetFront(MyCircularDeque *obj) {
return !obj->size ? -1 : obj->head->next->val;
}
int myCircularDequeGetRear(MyCircularDeque *obj) {
return !obj->size ? -1 : obj->tail->prev->val;
}
bool myCircularDequeIsEmpty(MyCircularDeque *obj) { return !obj->size; }
bool myCircularDequeIsFull(MyCircularDeque *obj) {
return obj->size == obj->max_size;
}
void myCircularDequeFree(MyCircularDeque *obj) {
struct node *curr = obj->head;
while (curr) {
struct node *back = curr;
curr = curr->next;
free(back);
}
}
int main() {
MyCircularDeque *obj = myCircularDequeCreate(3);
printf("%d\n", myCircularDequeInsertLast(obj, 1)); // expect: 1
printf("%d\n", myCircularDequeInsertLast(obj, 2)); // expect: 1
printf("%d\n", myCircularDequeInsertFront(obj, 3)); // expect: 1
printf("%d\n", myCircularDequeInsertFront(obj, 4)); // expect: 0
printf("%d\n", myCircularDequeGetRear(obj)); // expect: 2
printf("%d\n", myCircularDequeIsFull(obj)); // expect: 1
printf("%d\n", myCircularDequeDeleteLast(obj)); // expect: 1
printf("%d\n", myCircularDequeInsertFront(obj, 4)); // expect: 1
printf("%d\n", myCircularDequeGetFront(obj)); // expect: 4
myCircularDequeFree(obj);
}
|