aboutsummaryrefslogtreecommitdiff
path: root/design_circular_queue.c
diff options
context:
space:
mode:
Diffstat (limited to 'design_circular_queue.c')
-rw-r--r--design_circular_queue.c118
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);
+}