diff options
Diffstat (limited to 'design_circular_queue.c')
-rw-r--r-- | design_circular_queue.c | 118 |
1 files changed, 118 insertions, 0 deletions
diff --git a/design_circular_queue.c b/design_circular_queue.c new file mode 100644 index 0000000..ad1e353 --- /dev/null +++ b/design_circular_queue.c @@ -0,0 +1,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); +} |