aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--design_circular_queue.c118
-rw-r--r--design_circular_queue.py111
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())