サーキュラーバッファ は固定サイズの配列で、その両端が環に繋がっているかのように扱われます。2つのインデックス — 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)
Code
python
:
():
.buf = []*n
.head = .tail = .size =
.cap = n
():
.size == .cap: Exception()
.buf[.tail] = x
.tail = (.tail + ) % .cap
.size +=
():
x = .buf[.head]
.head = (.head + ) % .cap
.size -=
x
