บัฟเฟอร์เป็นวงกลม คืออาร์เรย์ขนาดคงที่ที่ถูกมองว่าปลายทั้งสองของมันเชื่อมต่อเป็นวงแหวน ดัชนีสองตัว — head (อ่าน) และ tail (เขียน) — เคลื่อนไปข้างหน้าและห่อเบิ้มโดยใช้เลขคณิต modulo ให้ FIFO คิว O(1) ที่ไม่มี การจัดสรร หลังจากสร้าง
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)
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) คงที่ |
บัฟเฟอร์วงแหวนให้พฤติกรรม FIFO ที่คาดเดาได้และปราศจากการจัดสรร ซึ่งจำเป็นในระบบเรียลไทม์และระบบฝังตัว ซึ่งการจัดสรรแบบไดนามิกช้าเกินไปหรือเสี่ยง
ขนาดที่มีขอบเขตของมันยังทำหน้าที่เป็นแรงกดดันย้อนกลับตามธรรมชาติ ป้องกันไม่ให้ผู้ผลิตที่เร็วกว่าใช้เนื้อที่ของหน่วยความจำ