एक circular buffer एक निश्चित-आकार की सरणी है जिसे इस तरह माना जाता है मानो इसके सिरे एक वलय में जुड़े हुए हों। दो सूचकांक — head (पढ़ना) और tail (लिखना) — आगे बढ़ते हैं और मॉड्यूलो अंकगणित का उपयोग करके लपेटते हैं, O(1) FIFO कतार प्रदान करते हैं निर्माण के बाद कोई आवंटन नहीं।
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 व्यवहार प्रदान करता है, जो वास्तविक समय और एम्बेडेड सिस्टम में आवश्यक है जहां गतिशील आवंटन बहुत धीमा या जोखिम भरा है।
इसका सीमित आकार प्राकृतिक बैकप्रेशर के रूप में भी कार्य करता है, तेज निर्माताओं को मेमोरी समाप्त करने से रोकता है।