# Moving Average from Data Stream

`Queue`, `Design`

**Easy**

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

**Example:**

```
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3
```

## Analysis

用Queue来实现先进先出这样的模式，同时根据应用场景，只需要计算均值，因此额外存一个元素总和sum即可，随着poll(), offer()来更新sum。

可用LinkedList，或者固定长度的array。

算法复杂度 **O(1) time, O(k) space**

## Solution

### Queue (Implemented with LinkedList)

(137ms 59.29%)

```java
class MovingAverage {
    private int sum;
    private Queue<Integer> queue;
    private int capacity;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        queue = new LinkedList<Integer>();
        sum = 0;
        capacity = size;
    }

    public double next(int val) {
        if (queue.size() == capacity) {
            int sub = queue.poll();
            sum = sum - sub;
        }
        queue.offer(val);
        sum = sum + val;

        return (double) sum / queue.size();
    }
}

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

### Another **simpler** **implementation** using **LinkedList as Queue**

```java
class MovingAverage {

    Queue<Integer> q;
    double sum = 0;
    int size;

    public MovingAverage(int s) {
        q = new LinkedList();
        size = s;
    }

    public double next(int val) {
        if(q.size() == size){
            sum = sum - q.poll();
        }
        q.offer(val);
        sum += val;
        return sum/q.size();
    }
}
```

#### Using ArrayDeque

```java
class MovingAverage {
    Deque<Integer> q;
    int sum;
    int size;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        this.size = size;
        sum = 0;
        q = new ArrayDeque<Integer>();
    }

    public double next(int val) {
        if (size == q.size()) {
            sum -= q.poll();
        }
        sum += val;
        q.offer(val);
        return 1.0 * sum / q.size();
    }
}

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

### **Using fixed length Array (Circular Queue)**

**(74 ms, faster than 100.00%, 43 MB, less than 59.43%**)

用固定长度Array，insertIdx作为下一个数字的位置，每次next()时，要先更新当前sum，再加上新的val。同时要注意的是追踪目前填入了多少个数字，如果小于window长度，则需要用当前填入数字的计数作为分母计算average。

```java
public class MovingAverage {
    private int [] window;
    private int n, insert;
    private long sum;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        window = new int[size];
        insert = 0;
        sum = 0;
    }

    public double next(int val) {
        if (n < window.length)  n++;
        sum -= window[insert];
        sum += val;
        window[insert] = val;
        insert = (insert + 1) % window.length;

        return (double)sum / n;
    }
}
```

#### Another implementation

```java
class MovingAverage {
    int[] window;
    int count;
    int capacity;
    int insertIdx;
    int sum;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        window = new int[size];
        count = 0;
        capacity = size;
        insertIdx = 0;
        sum = 0;
    }

    public double next(int val) {
        if (count < capacity) {
            count++;
        } else {
            sum -= window[insertIdx];
        }
        window[insertIdx] = val;
        sum += val;
        insertIdx = (insertIdx + 1) % capacity;
        int size = Math.min(count, capacity);
        return 1.0 * sum / size;
    }
}

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/queue/moving-average-from-data-stream.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.