Two-dequeue C solution using single array, beats 100%
We can store two floating dequeues in a single array.  This gives us O(1) push/pop times withough the list processing overhead.\n\nGiven that at most 1000 calls
We can store two floating dequeues in a single array.  This gives us O(1) push/pop times withough the list processing overhead.\n\nGiven that at most 1000 calls will be made, and that in the worst-case all of them will be pushes, we simply need to ensure that there is a gap of 1000 between the two dequeues, and between the dequeues and the ends of the array.\n\nWe allocate an array of 3000 slots and place the (initially zero-size) dequeues at positions 1000 and 2000.  That way each dequeue can grow by 1000 at either end without any collision.\n\n```\n/* Since at most 1000 items will be pushed, we can accommodate them in an\n   array containing two chunks, each delimited by a front and back index\n   (A and B delimit the left chunk, C and D the right, both inclusive/exclusive\n   respectively), with a clearance of 1000 between the front of the array and the\n   initial position of the front of the first chunk, and also between the two\n   chunks and between the end of the second chunk and the end of the array.\n   We always keep the two chunks the same size (differing by at most 1).\n*/\n\ntypedef struct {\n    int *array; int a,b,c,d;\n} FrontMiddleBackQueue;\n\n#define leftsize (obj->b - obj->a)\n#define rightsize (obj->d - obj->c)\n#define empty (leftsize + rightsize == 0)\n#define pusha(x) obj->array[--obj->a] = x\n#define pushb(x) obj->array[obj->b++] = x\n#define pushc(x) obj->array[--obj->c] = x\n#define pushd(x) obj->array[obj->d++] = x\n#define popa obj->array[obj->a++]\n#define popb obj->array[--obj->b]\n#define popc obj->array[obj->c++]\n#define popd obj->array[--obj->d]\n#define shiftleft pushb(popc)\n#define shiftright pushc(popb)\n\nFrontMiddleBackQueue* frontMiddleBackQueueCreate() {\nFrontMiddleBackQueue *obj = malloc(sizeof *obj);\n    obj->array = malloc(3000*sizeof(int));\n    obj->a = 1000; obj->b = 1000; obj->c = 2000; obj->d = 2000;\n    return obj;\n}\n\nvoid frontMiddleBackQueuePushFront(FrontMiddleBackQueue* obj, int val) {\n    if (leftsize > rightsize) shiftright;\n    pusha(val);\n}\n\nvoid frontMiddleBackQueuePushMiddle(FrontMiddleBackQueue* obj, int val) {\n    if (leftsize > rightsize) shiftright;\n    pushb(val);\n}\n\nvoid frontMiddleBackQueuePushBack(FrontMiddleBackQueue* obj, int val) {\n    if (rightsize > leftsize) shiftleft;\n    pushd(val);\n}\n\nint frontMiddleBackQueuePopFront(FrontMiddleBackQueue* obj) {\n    if empty return -1;\n    if (rightsize > leftsize) shiftleft;\n    return popa;\n}\n\nint frontMiddleBackQueuePopMiddle(FrontMiddleBackQueue* obj) {\n    if empty return -1;\n    if (leftsize>=rightsize) return popb;\n    return popc;\n}\n\nint frontMiddleBackQueuePopBack(FrontMiddleBackQueue* obj) {\n    if empty return -1;\n    if (leftsize > rightsize) shiftright;\n    return popd;\n}\n\nvoid frontMiddleBackQueueFree(FrontMiddleBackQueue* obj) {\n    free(obj->array); free(obj);\n}\n```\n
[]