వృత్తాకార బఫర్ అనేది స్థిర-పరిమాణ శ్రేణి, దీని చివరలను ఒక వలయంలో కలుపుకొని ఉన్నట్లుగా పరిగణించబడుతుంది. రెండు సూచికలు — 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 ప్రవర్తనను అందిస్తుంది, ఇది రియల్-టైమ్ మరియు ఎంబెడెడ్ సిస్టమ్లలో అవసరమైనది, ఇక్కడ డైనమిక్ కేటాయింపు చాలా నెమ్మదిగా లేదా ప్రమాదకరమైనది.
ఇది బౌండ్ చేయబడిన పరిమాణం కూడా సహజ బ్యాక్ప్రెషర్గా పనిచేస్తుంది, వేగవంతమైన ఉత్పత్తిదారులను మెమరీని ఖালీ చేయకుండా నిరోధిస్తుంది.