diff options
-rw-r--r-- | design_circular_queue.c | 118 | ||||
-rw-r--r-- | design_circular_queue.py | 111 |
2 files changed, 229 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); +} diff --git a/design_circular_queue.py b/design_circular_queue.py new file mode 100644 index 0000000..9e9db1e --- /dev/null +++ b/design_circular_queue.py @@ -0,0 +1,111 @@ +# 641. Design Circular Deque + +""" +design your implementation of the circular double ended queue (deque). +implement the 'MyCircularDeque' class +""" + + +class MyCircularDeque(object): + def __init__(self, k): + """ + :type k: int + """ + self.size = 0 + self.front = 0 + self.rear = 0 + self.capacity = k + self.data = [-1] * k + + def insertFront(self, value): + """ + :type value: int + :rtype: bool + """ + if self.isFull(): + return False + if self.isEmpty(): + self.data[self.front] = value + else: + self.front = (self.front - 1) % self.capacity + self.data[self.front] = value + self.size += 1 + return True + + def insertLast(self, value): + """ + :type value: int + :rtype: bool + """ + if self.isFull(): + return False + if self.isEmpty(): + self.data[self.rear] = value + else: + self.rear = (self.rear + 1) % self.capacity + self.data[self.rear] = value + self.size += 1 + return True + + def deleteFront(self): + """ + :rtype: bool + """ + if self.isEmpty(): + return False + self.data[self.front] = -1 + self.front = (self.front + 1) % self.capacity + self.size -= 1 + if self.isEmpty(): + self.rear = self.front + return True + + def deleteLast(self): + """ + :rtype: bool + """ + if self.isEmpty(): + return False + self.data[self.rear] = -1 + self.rear = (self.rear - 1) % self.capacity + self.size -= 1 + if self.isEmpty(): + self.front = self.rear + return True + + def getFront(self): + """ + :rtype: int + """ + return self.data[self.front] + + def getRear(self): + """ + :rtype: int + """ + return self.data[self.rear] + + def isEmpty(self): + """ + :rtype: bool + """ + return self.size == 0 + + def isFull(self): + """ + :rtype: bool + """ + return self.size == self.capacity + + +if __name__ == "__main__": + obj = MyCircularDeque(3) + print(obj.insertLast(1)) + print(obj.insertLast(2)) + print(obj.insertFront(3)) + print(obj.insertFront(4)) + print(obj.getRear()) + print(obj.isFull()) + print(obj.deleteLast()) + print(obj.insertFront(4)) + print(obj.getFront()) |