环形缓冲区在数据结构中是一种特殊的线性数据结构，具有以下特点和优势：
结构特点
- 固定大小：环形缓冲区通常具有固定的容量，一旦创建，其大小就不能改变。这使得在内存使用方面更加可控，避免了动态分配内存带来的开销和不确定性。
- 循环利用空间：正因为其环形的特性，当写指针到达缓冲区的末尾时，会自动回绕到开头继续写入数据；读指针在读取完数据后也会相应地移动，实现空间的循环利用。
操作方式
- 写入操作：当向环形缓冲区写入数据时，首先检查缓冲区是否已满。如果未满，则将数据写入写指针所指的位置，然后写指针向前移动一位。如果写指针移动到缓冲区的末尾，它会回绕到开头。
- 读取操作：从环形缓冲区读取数据时，先检查缓冲区是否为空。如果不为空，则读取读指针所指位置的数据，然后读指针向前移动一位。同样，当读指针到达缓冲区的末尾时，会回绕到开头。
应用场景
- 实时数据处理：在需要对连续产生的实时数据进行处理的场景中，环形缓冲区可以作为数据的暂存区域。例如，音频和视频流的处理，数据采集系统等。
- 多生产者 - 多消费者模型：环形缓冲区可以方便地在多个生产者和多个消费者之间共享数据。生产者将数据写入缓冲区，消费者从缓冲区读取数据，通过合理的同步机制，可以实现高效的数据交换。
- 缓存数据：可以用作缓存，存储最近使用的数据，以提高数据的访问速度。例如，在数据库查询中，可以将最近查询的结果存储在环形缓冲区中，以便下次相同的查询可以直接从缓冲区中获取结果。
实现要点
- 指针管理：准确地管理写指针和读指针是实现环形缓冲区的关键。需要确保指针的移动正确无误，并且在进行读写操作时不会出现越界的情况。
- 同步机制：在多线程环境下使用环形缓冲区时，需要考虑同步问题。可以使用互斥锁、条件变量等同步机制来确保线程安全。
- 空满判断：需要有可靠的方法来判断环形缓冲区是为空还是已满。常见的方法有使用计数器、位运算等。
示例：错误日志记录
描述
https://www.nowcoder.com/practice/2baa6aba39214d6ea91a2e03dff3fbeb
开发一个简单错误记录功能小模块，能够记录出错的代码所在的文件名称和行号。
处理：
- 记录最多8条错误记录，循环记录，最后只用输出最后出现的八条错误记录。对相同的错误记录只记录一条，但是错误计数增加。最后一个斜杠后面的带后缀名的部分（保留最后16位）和行号完全匹配的记录才做算是“相同”的错误记录。
- 超过16个字符的文件名称，只记录文件的最后有效16个字符；
- 输入的文件可能带路径，记录文件名称不能带路径。也就是说，哪怕不同路径下的文件，如果它们的名字的后16个字符相同，也被视为相同的错误记录
- 循环记录时，只以第一次出现的顺序为准，后面重复的不会更新它的出现时间，仍以第一次为准
数据范围：错误记录数量满足 1≤n≤100 1≤n≤100 ，每条记录长度满足 1≤len≤100 1≤len≤100
输入描述：
每组只包含一个测试用例。一个测试用例包含一行或多行字符串。每行包括带路径文件名称，行号，以空格隔开。
输出描述：
将所有的记录统计并将结果输出，格式：文件名 代码行数 数目，一个空格隔开，如：
代码语言：javascript复制输入：
D:zwtymjxccbljjcqzlyaszjvlsjmkwoqijggmybr 645
E:jerzuwnjvnuz 633
C:kmtgjwpbgyatl 637
F:weiojhaddconnshrwyfvzsopsuiqjnr 647
E:nsmfwjwqkokieez 648
D:cfmwafhhgeyawnool 649
E:cztopwiposnllc 637
G:ntf 633
F:fopywzqaop 631
F:yayjcywzqaop 631
D:zwtymjxccbljjcqzlyaszjvlsjmkwoqijggmybr 645
输出：
rzuwnjvnuz 633 1
atl 637 1
rwyfvzsopsuiqjnr 647 1
eez 648 1
fmwafhhgeyawnool 649 1
c 637 1
f 633 1
ywzqaop 631 2import sys
SIZE = 8
def formatFileName(f, size = 16):
if len(f) > size:
return f[-16:]
else:
return f
class RingBuffer:
def __init__(self, size) -> None:
self.buffer = []
self.legacy = []
self.head = 0
self.size = size
def put(self, item):
if item is not None: # 跳过已经淘汰的日志
for l in self.legacy:
if l["file"] == item["file"] and l["line"] == item["line"]:
return
if len(self.buffer) < self.size: # 缓冲区没有满，追加即可
self.buffer.append(item)
else: # 缓冲区已满，把要添加的元素放到队尾
self.legacy.append(self.buffer[self.head]) # 记录已经淘汰的日志
self.buffer[self.head] = item
self.head = (self.head 1) % self.size
def findItem(self, file, line):
for idx, i in enumerate(self.buffer):
if i["file"] == file and i["line"] == line: # 文件名和行号都相同才可以
return idx
return None
def showItem(self, idx):
if idx < len(self.buffer):
return self.buffer[idx]
else:
return None
def updateItem(self, idx, key, value):
self.buffer[idx][key] = value
def print(self):
if not len(self.buffer):
return
headNode = self.buffer[self.head]
print(f'{headNode.get("file")} {headNode.get("line")} {headNode.get("count")}')
h = (self.head 1) % len(self.buffer)
while (h != self.head):
node = self.buffer[h]
print(f'{node.get("file")} {node.get("line")} {node.get("count")}')
h = (h 1) % len(self.buffer)
def filterLog(log):
if not log or not isinstance(log, str):
return None, None
[path, line] = log.split()
return path.split("\")[-1], line
buffer = RingBuffer(SIZE)
for line in sys.stdin:
f, l = filterLog(line.strip())
if f is None or l is None:
continue
f = formatFileName(f) # 题目出的很奇怪，尾十六位相同的文件竟然被当成同一个文件
idx = buffer.findItem(f, l)
if idx is not None:
item = buffer.showItem(idx)
if item:
buffer.updateItem(idx, "count", item["count"] 1)
else:
buffer.put({"file": f, "line": l, "count": 1})
buffer.print()
