// 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); }