Moving Average from Data Stream

题目：

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

For 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

分析：

这道题允许任选数据结构，我选择了用Queue实现，因为我觉得Queue应该使用基本的链表实现的。然而lintcode上面有一道题目说是用2个stack实现Queue，搞得我有点纠结。干脆再找个链表做一遍，底层一点。

题目来自leetcode, lintcode上没有，但是lintcode有个更有意思点的，叫做median of data stream

解法：

class MovingAverage {
public:
    int q_size = 0;
    int curr_size = 0;
    double sum = 0;
    queue<int> Q;

    /** Initialize your data structure here. */
    MovingAverage(int size) {
        q_size = size;
    }

    double next(int val) {
        curr_size += 1;
        curr_size = min(curr_size, q_size);

        if (curr_size == q_size) {
            sum -= Q.front();
            Q.pop();
        }

        sum += val;
        Q.push(val);

        double res = sum / curr_size;
        return res;
    }
};

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