એક 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 અનુમાનિત અને ફાળવણી-મુક્ત પ્રદાન કરે છે, જે વાસ્તવિક-સમય અને એમ્બેડેડ સિસ્ટમમાં આવશ્યક છે જ્યાં ગતિશીલ ફાળવણી ખૂબ ધીમી અથવા જોખમી છે.
તેનું બંધાયેલ કદ પણ કુદરતી પાછાથી દબાણ તરીકે કાર્ય કરે છે, ઝડપી નિર્માતાઓને મેમરી સમાપ્ત થતું અટકાવે છે.