循环队列 - wangshengliang

循环队列是一种利用 固定大小 的数组实现队列操作的数据结构，但它采用了**“环形”思想**，使得数组的末尾与开头相连，从而充分利用了所有存储空间。

普通队列与循环队列的差异

普通队列：使用数组来实现，随着元素不断出队，数组前面部分就空闲了（特别是像 Java、C++ 这一类有标准数组数据结构的语言）。当然，可以将后面的元素往前面移动，但是这里又涉及到了移动相关的操作。
循环队列：利用环形结构，队尾到达数组末尾之后，新的入队操作会自动写入到数组起始的位置。

循环队列特点

固定容量与环形结构
- 固定容量
- 环形思想：实际上都是通过模运算来计算新入队的元素的下标位置
指针管理：通常使用两个变量：
- 队头指针（front）：指向队列的第一个元素
- 元素计数（rear/count）：记录当前队列有多少个元素，方便后面做模运算
- 模运算，使得指针在数组边界“循环”，避免了普通队列中出队后前部空间无法再利用的问题。
高效操作

具体示例

假设有一个大小为 5 的队列，我们依次对队列执行以下操作：

普通队列#

基于固定数组，未使用循环策略

入队操作：将元素 A、B、C 依次入队
```
[A, B, C, _, _]
```
出队操作：出队两次，把 A 和 B 出队
```
[_, _, C, _, _]
```
现在随着 A 和 B 的出队，前面两个位置就空出来了
再次入队操作：入队 D 和 E 元素
```
[_, _, C, D, E]
```
现在这个结构就没有办法再入队新元素，已经满了。除非将后面的元素全部往前面移动：
```
[C, D, E, _, _]
```

循环队列#

同样大小为 5 的循环队列，进行相同的操作：

入队操作：将元素 A、B、C 依次入队
```
[A, B, C, _, _]
```
- frontIndex：0
- count：3
- maxSize：5
出队操作：出队两次，把 A 和 B 出队
```
[_, _, C, _, _]
```
这里就会更新队首指针：新队首指针 = (旧队首指针 + 1) % maxSize
- A元素出队的时候：新队首指针 = (0 + 1) % 5 = 1
- B元素出队的时候：新队首指针 = (1 + 1) % 5 = 2
再次入队操作：之后新元素入队，放入位置的计算公式 (队首指针 + count) % maxSize
- 新元素 D 入队：(2 + 1) % 5 = 3
```
[_, _, C, D, _]
```
  - frontIndex：0
  - count : 2
- 新元素 E 入队：(2 + 2) % 5 = 4
```
[_, _, C, D, E]
```
  - count：3
- 新元素 F 入队：(2 + 3) % 5 = 0
```
[F, _, C, D, E]
```
  - count: 4
- 新元素G 入队：(2 + 4) % 5 = 1
```
[F, G, C, D, E]
```
  - count: 5

通过循环队列这种计算方式，就不需要将后面的元素全部往前面移动，可以通过模运算计算出每次新元素应该入队的正确位置。

代码实现

class CircularQueue {
  constructor(maxSize = 10) {
    this.maxSize = maxSize
    this.queue = new Array(maxSize)
    // 队首指针
    this.frontIndex = 0
    // 队列元素计数
    this.count = 0
  }

  // 一些辅助方法：size、isEmpty、isFull
  size() {
    return this.count
  }
  isEmpty() {
    return this.count === 0
  }
  isFull() {
    return this.count === this.maxSize
  }

  // 新元素入队
  enqueue(item) {
    if (this.isFull()) {
      // 进入此分支，说明队列已满
      throw new Error('队列已满')
    }

    // 计算新元素应该存储的索引位置
    let index = (this.frontIndex + this.count) % this.maxSize
    this.queue[index] = item
    this.count++
  }

  // 元素出队
  dequeue() {
    if (this.isEmpty()) {
      return undefined
    }
    // 取出队首的元素
    let item = this.queue[this.frontIndex]
    this.queue[this.frontIndex] = undefined
    // 更新存储队首位置的变量
    this.frontIndex = (this.frontIndex + 1) % this.maxSize
    this.count--
    return item
  }

  // 获取队首的元素，但是不移除
  front() {
    return this.isEmpty() ? undefined : this.queue[this.frontIndex]
  }

  // 获取队尾的元素，但是不移除
  // 队尾元素的索引计算公式：(frontIndex + count - 1) % maxSize
  back() {
    if (this.isEmpty()) return undefined
    let index = (this.frontIndex + this.count - 1) % this.maxSize
    return this.queue[index]
  }

  clear() {
    // 清空队列，全部还原
    this.queue = new Array(this.maxSize)
    this.frontIndex = 0
    this.count = 0
  }

  print() {
    // 显示当前队列信息
    // 1. 当前数组里面的元素  2. 元素的正确顺序
    console.log(this.queue)
    // 还需要显示元素正确的顺序
    for (let i = 0; i < this.count; i++) {
      // 计算正确的下标，然后打印出来
      let index = (this.frontIndex + i) % this.maxSize
      console.log(this.queue[index] + ' ')
    }
  }
}