aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--front_middle_back_queue.c182
-rw-r--r--front_middle_back_queue.py64
2 files changed, 246 insertions, 0 deletions
diff --git a/front_middle_back_queue.c b/front_middle_back_queue.c
new file mode 100644
index 0000000..073622c
--- /dev/null
+++ b/front_middle_back_queue.c
@@ -0,0 +1,182 @@
+// 1670. Design Front Middle Back Queue
+#include "leetcode.h"
+
+/*
+ * design a queue that supports 'push' and 'pop' operations in the front,
+ * middle, and back. notice that when there are two middle position choices, the
+ * operation is performed on the frontmost middle position choice.
+ */
+
+struct node {
+ int val;
+ struct node *next;
+};
+
+typedef struct {
+ struct node *front;
+ struct node *rear;
+ int cnt;
+} FrontMiddleBackQueue;
+
+FrontMiddleBackQueue *frontMiddleBackQueueCreate() {
+ FrontMiddleBackQueue *q =
+ (FrontMiddleBackQueue *)malloc(sizeof(FrontMiddleBackQueue));
+ q->front = NULL;
+ q->rear = NULL;
+ q->cnt = 0;
+ return q;
+}
+
+void frontMiddleBackQueuePushFront(FrontMiddleBackQueue *obj, int val) {
+ struct node *new = (struct node *)malloc(sizeof(struct node));
+ new->val = val;
+ new->next = obj->front;
+ obj->front = new;
+ if (!obj->rear)
+ obj->rear = obj->front;
+ obj->cnt++;
+}
+
+void frontMiddleBackQueuePushMiddle(FrontMiddleBackQueue *obj, int val) {
+ struct node *slow = obj->front;
+ if (!slow) {
+ struct node *new = (struct node *)malloc(sizeof(struct node));
+ new->val = val;
+ new->next = NULL;
+ obj->front = new;
+ obj->rear = new;
+ obj->cnt++;
+ } else if (!slow->next) {
+ struct node *new = (struct node *)malloc(sizeof(struct node));
+ new->val = val;
+ obj->front = new;
+ new->next = slow;
+ obj->cnt++;
+ return;
+ }
+ struct node *prev_slow = NULL, *fast = obj->front->next;
+ while (fast) {
+ prev_slow = slow;
+ slow = slow->next;
+ fast = fast->next;
+ if (fast)
+ fast = fast->next;
+ }
+ struct node *new = (struct node *)malloc(sizeof(struct node));
+ new->val = val;
+ prev_slow->next = new;
+ new->next = slow;
+ obj->cnt++;
+}
+
+void frontMiddleBackQueuePushBack(FrontMiddleBackQueue *obj, int val) {
+ struct node *new = (struct node *)malloc(sizeof(struct node));
+ new->val = val;
+ if (obj->rear)
+ obj->rear->next = new;
+ else
+ obj->front = new;
+ obj->rear = new;
+ new->next = NULL;
+ obj->cnt++;
+}
+
+int frontMiddleBackQueuePopFront(FrontMiddleBackQueue *obj) {
+ if (!obj->front)
+ return -1;
+ int res = obj->front->val;
+ struct node *del = obj->front;
+ obj->front = obj->front->next;
+ free(del);
+ if (!obj->front)
+ obj->rear = NULL;
+ obj->cnt--;
+ return res;
+}
+
+int frontMiddleBackQueuePopMiddle(FrontMiddleBackQueue *obj) {
+ struct node *slow = obj->front;
+ int res;
+ if (!slow)
+ return -1;
+ if (!slow->next) {
+ res = slow->val;
+ obj->front = NULL;
+ obj->rear = NULL;
+ obj->cnt--;
+ free(slow);
+ return res;
+ }
+ struct node *prev_slow = NULL, *prev_prev_slow = NULL,
+ *fast = obj->front->next;
+ while (fast) {
+ prev_prev_slow = prev_slow;
+ prev_slow = slow;
+ slow = slow->next;
+ fast = fast->next;
+ if (fast)
+ fast = fast->next;
+ }
+ if (!(obj->cnt % 2)) {
+ res = prev_slow->val;
+ if (obj->cnt == 2) {
+ free(prev_slow);
+ obj->front = slow;
+ } else {
+ prev_prev_slow->next = slow;
+ free(prev_slow);
+ }
+ } else {
+ res = slow->val;
+ prev_slow->next = slow->next;
+ free(slow);
+ }
+ obj->cnt--;
+ return res;
+}
+
+int frontMiddleBackQueuePopBack(FrontMiddleBackQueue *obj) {
+ if (!obj->rear)
+ return -1;
+ int res = obj->rear->val;
+ struct node *trav = obj->front;
+ if (trav == obj->rear) {
+ obj->front = NULL;
+ obj->rear = NULL;
+ free(trav);
+ } else {
+ while (trav->next != obj->rear)
+ trav = trav->next;
+ trav->next = NULL;
+ free(obj->rear);
+ obj->rear = trav;
+ }
+ obj->cnt--;
+ return res;
+}
+
+void frontMiddleBackQueueFree(FrontMiddleBackQueue *obj) {
+ struct node *trav = obj->front, *del = NULL;
+ while (trav) {
+ del = trav;
+ trav = trav->next;
+ free(del);
+ }
+ obj->front = NULL;
+ obj->rear = NULL;
+ obj->cnt = 0;
+}
+
+int main() {
+ FrontMiddleBackQueue *obj = frontMiddleBackQueueCreate();
+ frontMiddleBackQueuePushFront(obj, 1);
+ frontMiddleBackQueuePushBack(obj, 2);
+ frontMiddleBackQueuePushMiddle(obj, 3);
+ frontMiddleBackQueuePushMiddle(obj, 4);
+ printf("%d\n", frontMiddleBackQueuePopFront(obj)); // expect: 1
+ printf("%d\n", frontMiddleBackQueuePopMiddle(obj)); // expect: 3
+ printf("%d\n", frontMiddleBackQueuePopMiddle(obj)); // expect: 4
+ printf("%d\n", frontMiddleBackQueuePopBack(obj)); // expect: 2
+ printf("%d\n", frontMiddleBackQueuePopFront(obj)); // expect: -1
+ frontMiddleBackQueueFree(obj);
+}
diff --git a/front_middle_back_queue.py b/front_middle_back_queue.py
new file mode 100644
index 0000000..cc3e619
--- /dev/null
+++ b/front_middle_back_queue.py
@@ -0,0 +1,64 @@
+# 1670. Design Front Middle Back Queue
+
+"""
+design a queue that supports 'push' and 'pop' operations in the front,
+middle, and back. notice that when there are two middle position choices, the
+operation is performed on the frontmost middle position choice.
+"""
+
+
+class FrontMiddleBackQueue(object):
+ def __init__(self):
+ self.a = []
+
+ def pushFront(self, val):
+ """
+ :type val: int
+ :rtype: None
+ """
+ self.a.insert(0, val)
+
+ def pushMiddle(self, val):
+ """
+ :type val: int
+ :rtype: None
+ """
+ self.a.insert(len(self.a) / 2, val)
+
+ def pushBack(self, val):
+ """
+ :type val: int
+ :rtype: None
+ """
+ self.a.append(val)
+
+ def popFront(self):
+ """
+ :rtype: int
+ """
+ return self.a or [-1].pop(0)
+
+ def popMiddle(self):
+ """
+ :rtype: int
+ """
+ return self.a or [-1].pop((len(self.a) - 1) / 2)
+
+ def popBack(self):
+ """
+ :rtype: int
+ """
+ return self.a or [-1].pop()
+
+
+if __name__ == "__main__":
+ obj = FrontMiddleBackQueue()
+ obj.pushFront(1)
+ obj.pushBack(2)
+ obj.pushMiddle(3)
+ obj.pushMiddle(4)
+ print(obj.popFront())
+ print(obj.popMiddle())
+ print(obj.popMiddle())
+ print(obj.popBack())
+ print(obj.popFront())