diff options
-rw-r--r-- | front_middle_back_queue.c | 182 | ||||
-rw-r--r-- | front_middle_back_queue.py | 64 |
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()) |