Implement Queue with Limited Size of Array - Airbnb

https://leetcode.com/discuss/interview-question/156969/Implement-Queue-using-fixed-size-array/

Assume in your programming language you only have a fixed size array of length 5. Implement a queue datastructure that can get unlimitted number of elements.

Assumption: The arrays hold 5 elements, each of which is the size of a pointer.
Our first level of abstraction is to use our stupid arrays to make a less stupid array, which has access in log(N) time.
Once we have an Array, with all of the capabilities of your typical array, implementing a queue, stack, deque, whatever, will be the normal way of doing so.

class Array {
    Array(int size) {
        this->size = size;
        
        depth = max(0, log5(size)-1); // Depth 0 is for size <= 5
        build_array(depth, head);
    }

    // Will hold 5^depth elements, which is likely greater than size, but you know
    // what they say about premature optimization
    void build_array(int depth, stupid_array arr) {
        if (depth == 0) return;
        for i = 0 to 4 {
            arr[i] = new stupid_array;
            build_array(depth-1, arr[i]);
        }
    }

    (stupid_array, int) find_index(int idx)
    {
        return find_index(0, idx, head);
    }

    (stupid_array, int) find_index(int d, int idx, stupid_array arr)
    {
        int net_depth = depth - d;
        int subarray_size = pow(5, net_depth-1);
        if (subarray_size == 1) {
            return (head, idx);
        }

        return find_index(d+1, idx % subarray_size, arr[idx / subarray_size]);
    }

    insert(void * value, int idx) {
        stupid_array subarr;
        int subidx;
        (subarr, subidx) =  find_index(idx);
        subarr[subidx] = value;
    } 

    void * get(int idx) {
        stupid_array subarr;
        int subidx;
        (subarr, subidx) =  find_index(idx);
        return subarr[subidx];
    }

    stupid_array head;
    int size, depth;
}

Now that we have an array that has a normal interface, and which has reasonably fast access of O(log(N)), we can easily create a queue

https://github.com/allaboutjst/airbnb

Implement a queue with a number of arrays, in which each array has fixed size.

2.Implement Queue with limited size of array: 使用double linkedlist

2. Implement Queue with limited size of array：方法二 ListNode with fixed size of array

https://github.com/allaboutjst/airbnb/blob/master/src/main/java/implement_queue_with_fixed_size_of_arrays/ImplementQueuewithFixedSizeofArrays.java

    public class QueueWithFixedArray {
        private int fixedSize;

        private int count;
        private int head;
        private int tail;
        private List<Object> headList;
        private List<Object> tailList;

        public QueueWithFixedArray(int fixedSize) {
            this.fixedSize = fixedSize;
            this.count = 0;
            this.head = 0;
            this.tail = 0;
            this.headList = new ArrayList<>();
            this.tailList = this.headList;
        }

        public void offer(int num) {
            if (tail == fixedSize - 1) {
                List<Object> newList = new ArrayList<>();
                newList.add(num);
                tailList.add(newList);
                tailList = (List<Object>) tailList.get(tail);
                tail = 0;
            } else {
                tailList.add(num);
            }
            count++;
            tail++;
        }

        public Integer poll() {
            if (count == 0) {
                return null;
            }

            int num = (int) headList.get(head);
            head++;
            count--;

            if (head == fixedSize - 1) {
                List<Object> newList = (List<Object>) headList.get(head);
                headList.clear();
                headList = newList;
                head = 0;
            }

            return num;
        }

        public int size() {
            return count;
        }
    }

TODO:
http://fabian-kostadinov.github.io/2014/11/25/implementing-a-fixed-length-fifo-queue-in-java/