什么是循环缓冲区（环形缓冲区），你什么时候会使用它？

Question

IT Interview Practice · Accepted Answer

一个**循环缓冲区**是一个固定大小的数组，被视为其两端连接成一个环。两个索引——**head**（读）和 **tail**（写）——使用模运算向前推进并环绕，提供一个 O(1) FIFO 队列，创建后**无需再分配**。

## 环绕的工作原理

```text
capacity 5, after writing A,B,C,D and reading A,B:
index:  0   1   2   3   4
      [ . ][ . ][ C ][ D ][ . ]
              head^       tail^   (tail wraps to 0 next write)
```

## 代码

```python
class RingBuffer:
    def __init__(self, n):
        self.buf = [None]*n
        self.head = self.tail = self.size = 0
        self.cap = n
    def enqueue(self, x):                  # O(1)
        if self.size == self.cap: raise Exception("full")
        self.buf[self.tail] = x
        self.tail = (self.tail + 1) % self.cap   # wrap
        self.size += 1
    def dequeue(self):                     # O(1)
        x = self.buf[self.head]
        self.head = (self.head + 1) % self.cap    # wrap
        self.size -= 1
        return x
```

| 操作 | 时间 |
|---|---|
| enqueue / dequeue | O(1) |
| 空间 | O(n) 固定 |

## 何时使用

- **流式传输 / 音频 / 视频缓冲区** —— 有界、稳定的吞吐量。
- **生产者–消费者** 管道，具有背压机制。
- **记录最后 N 个事件**（覆盖最旧的）。

## 为什么这很重要

循环缓冲区提供可预测、无需分配的 FIFO 行为，这对实时和嵌入式系统至关重要，因为动态分配在这些系统中速度太慢或风险太大。

其有界的大小也充当自然的背压机制，防止快速生产者耗尽内存。

环绕的工作原理

代码

相关问题

何时使用

为什么这很重要