1. はじめに
循環バッファとは、リングバッファとも呼ばれ、先頭と末尾の要素の挿入・削除を高速に（時間計算量 $O(1)$）行うことができるデータ構造である。
循環バッファの概要
循環バッファとは、名前の通り、環の形をしており先頭と末尾の挿入・削除を高速に行うことができるデータ構造である。
環の形とあるように、配列の末尾に到達したあと、配列の先頭に戻って書き込みを続けることができる点が特徴である。
循環バッファでは要素の挿入・削除が $O(1)$ であるのに足して、通常の配列では、先頭から要素を削除すると後続の要素を詰める必要があり、$O(N)$ の計算量がかかる。
内部のインデックスは、mod 演算で管理される。
図1. リングバッファの模式図（出典：Implementing a Queue using a circular array）
3. Python による実装
循環バッファをPythonで実装したものを以下に示す。本実装では、循環バッファの挿入および削除を実装した。また、高水準言語の deque や VecDeque に見られるような、配列のサイズ変更（$=$ resize）も実装されている。
ただし、今回は循環参照の挙動を観察することを目的としているため、実装の一部は簡略化または冗長化されている。
class CircularBuffer:
def __init__(self, capacity=4):
self.buffer = [None] * capacity
self.capacity = capacity
self.head = 0
self.tail = 0
self.size = 0
def __resize(self):
new_cap = self.capacity * 2
new_buf = [None] * new_cap
for i in range(self.size):
new_buf[i] = self.buffer[(self.tail + i) % self.capacity]
self.buffer = new_buf
self.capacity = new_cap
self.head = self.size
self.tail = 0
def push(self, value):
if self.size == self.capacity:
self.__resize()
self.buffer[self.head] = value
self.head = (self.head + 1) % self.capacity
self.size += 1
def pop(self):
if self.size == 0:
raise IndexError("Buffer is empty")
value = self.buffer[self.tail]
self.buffer[self.tail] = None
self.tail = (self.tail + 1) % self.capacity
self.size -= 1
return value
def __repr__(self):
line = "=" * 24
buf = ", ".join(str(x) if x is not None else "_" for x in self.buffer)
meta = f"head = {self.head}\ntail = {self.tail}\nsize = {self.size}"
content = f"[ {buf} ]"
return f"\n{meta}\n\n{content}\n{line}"
print("=" * 24)
cb = CircularBuffer(5)
cb.push(10)
cb.push(20)
cb.push(30)
print(cb) # [10, 20, 30, _, _] (head=3, tail=0, size=3)
cb.pop()
print(cb) # [_, 20, 30, _, _] (head=3, tail=1, size=2)
cb.push(40)
cb.push(50)
cb.push(60)
print(cb) # [60, 20, 30, 40, 50] (head=1, tail=1, size=5)
cb.push(70) # 上書き発生
print(cb) # [60, 70, 30, 40, 50] (head=2, tail=2, size=5)
実行結果を次に示す。出力結果から、resize、pop、および push の各操作が、それぞれ期待通りに動作していることが確認できる。
特に、要素数がバッファ容量に達した際に resize が発生し、配列のサイズが自動的に倍増していることがわかる。
========================
head = 3
tail = 0
size = 3
[ 10, 20, 30, _, _ ]
========================
head = 3
tail = 1
size = 2
[ _, 20, 30, _, _ ]
========================
head = 1
tail = 1
size = 5
[ 60, 20, 30, 40, 50 ]
========================
head = 6
tail = 0
size = 6
[ 20, 30, 40, 50, 60, 70, _, _, _, _ ]
========================
4. まとめ
本記事では、Python を用いて循環バッファを実装し、挿入（push）、削除（pop）、および容量拡張（resize）の各操作を確認した。
実行結果から、インデックスを mod 演算で管理することで、配列の末尾に達しても先頭に戻って処理を継続できることが確認された。
このような構造は、リアルタイム通信やストリーム処理など、高速かつ連続的なデータ処理に適している。
5. 参考資料
[1]. Implementing a Queue using a circular array
[2]. 循環バッファ - アルゴリズムとデータ構造
[3]. 循環バッファとは