346.Moving Average from Data Stream

Solution 1circular queue On

class MovingAverage {
    int windowSize = 0;
    int[] queue;
    int queueHead;
    int queueTail;
    int elementNum;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        windowSize = size;
        queue = new int[size];
        queueHead = 0;
        queueTail = 0;
        elementNum = 0;
    }

    public double next(int val) {
        if((queueTail + 1) % windowSize == queueHead){
            queueHead = (queueHead + 1) % windowSize;
        }
        queue[queueTail] = val;
        elementNum += 1;
        queueTail = (queueTail + 1) % windowSize;
        if(elementNum > windowSize){
            elementNum = windowSize;
        }
        double sum = 0.0;
        for(int index = queueHead, i = 1; i <= elementNum ; i++){
            sum += queue[index];
            index++;
            if(index == windowSize){
                index = 0;
            }
        }
        return sum / elementNum;
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

Solution 2:O(1)

class MovingAverage {
    int windowSize = 0;
    int[] queue;
    int queueHead;
    int queueTail;
    int elementNum;
    double sum;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        windowSize = size;
        queue = new int[size];
        queueHead = 0;
        queueTail = 0;
        elementNum = 0;
        sum = 0.0;
    }

    public double next(int val) {
        if(windowSize == 0){
            return 0.0;
        }
        if(elementNum == windowSize){
            sum -= queue[queueHead];
            queueHead = (queueHead + 1) % windowSize;
        }
        queue[queueTail] = val;
        sum += val;
        elementNum += 1;
        queueTail = (queueTail + 1) % windowSize;
        if(elementNum > windowSize){
            elementNum = windowSize;
        }
        return sum / elementNum;
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */