المخزن المؤقت الدائري هو مصفوفة بحجم ثابت يتم التعامل معها كما لو أن نهاياتها متصلة في حلقة. يتقدم مؤشران — 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) |
| space | O(n) ثابت |
يوفر المخزن المؤقت الدائري سلوك FIFO متنبأ به وخالي من التخصيص، وهو أمر ضروري في الأنظمة ذات الوقت الفعلي والمدمجة حيث يكون التخصيص الديناميكي بطيئًا جدًا أو محفوفًا بالمخاطر.
حجمه المحدود أيضًا يعمل كـ backpressure طبيعي، مما يمنع المنتجين السريعين من استنزاف الذاكرة.