4. 队列 | 星城哈哈

# 4. 队列

队列是一种遵从先进先出 (FIFO) 原则的有序集合

队列一个线性结构，特点是在某一端添加数据，在另一端删除数据，遵循先进先出的原则。

插入（insert）操作也称作入队（enqueue）

删除（delete）操作也被称为出队（dequeue)

class Queue {
  constructor() {
    this.queue = []
  }
  enQueue(item) {
    return this.queue.push(item)
  }
  deQueue() {
    return this.queue.shift()
  }
  getHeader() {
    return this.queue[0]
  }
  getSize() {
    return this.queue.length
  }
  isEmpty() {
    return this.getSize() === 0
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

队列的应用：

# 数据流中的移动平均值 (opens new window)

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。

示例:
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
1
2
3
4
5

解题思路：

分析测试用例

窗口大小固定，并且为整数
调用 next 添加数字并求平均值
超过窗口大小，最先添加的数字优先移除（先进先出）

算法原理

使用队列添加整数
创建成员变量来保存计算的值

算法流程

新增整数，进行入队操作
累加整数并保存
如果队列大小超出窗口大小，进行出队操作，并对成员变量进行减法。
返回平均值

← 3. 栈 5. 链表 →