সার্কুলার বাফার একটি নির্দিষ্ট আকারের অ্যারে যা এমনভাবে বিবেচনা করা হয় যেন এর প্রান্তগুলি একটি রিংয়ে সংযুক্ত। দুটি ইনডেক্স — head (পড়া) এবং tail (লেখা) — modulo গাণিতিকতা ব্যবহার করে এগিয়ে যায় এবং মোড়ায়, যা সৃষ্টির পরে কোনো বরাদ্দ ছাড়াই 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) |
| space | O(n) নির্দিষ্ট |
রিং বাফার অনুমানযোগ্য, বরাদ্দ-মুক্ত FIFO আচরণ প্রদান করে, যা রিয়েল-টাইম এবং এম্বেডেড সিস্টেমে প্রয়োজনীয় যেখানে গতিশীল বরাদ্দ খুব ধীর বা ঝুঁকিপূর্ণ।
এর সীমাবদ্ধ আকার প্রাকৃতিক backpressure হিসাবেও কাজ করে, দ্রুত প্রযোজকদের মেমরি সম্পূর্ণ করা থেকে রক্ষা করে।