# Moving Average of Data Stream

### 描述​

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

### 代码​

#### 双端队列​

# Moving Average of Data Stream# Time Complexity O(1), Space Complexity O(n)class MovingAverage:    def __init__(self, size: int):        self.size = size        self.queue = deque()        self.window_sum = 0.0        self.count = 0    def next(self, val: int) -> float:        self.count += 1        self.queue.append(val)        head = self.queue.popleft() if self.count > self.size else 0        self.window_sum = self.window_sum - head + val        return self.window_sum / min(self.size, self.count)

#### 循环队列​

# Moving Average of Data Stream# Time Complexity O(1), Space Complexity O(n)class MovingAverage:    def __init__(self, size: int):        self.size = size        self.queue = [0] * size        self.tail = 0        self.window_sum = 0.0        self.count = 0    def next(self, val: int) -> float:        self.count += 1        head_index = (self.tail + 1) % self.size        self.window_sum = self.window_sum - self.queue[head_index] + val        # move forward for one step        self.tail = (self.tail + 1) % self.size        self.queue[self.tail] = val        return self.window_sum / min(self.size, self.count)