ਇੱਕ circular buffer ਇੱਕ ਸਥਿਰ ਆਕਾਰ ਦੀ array ਹੈ ਜਿਸ ਨੂੰ ਇਸ ਤਰਾਂ ਮੰਨਿਆ ਜਾਂਦਾ ਹੈ ਜਿਵੇਂ ਇਸ ਦੇ ਸਿਰੇ ਇੱਕ ਰਿੰਗ ਵਿੱਚ ਜੁੜੇ ਹਨ। ਦੋ ਇੰਡੀਸਜ਼ — head (ਪੜ੍ਹਨਾ) ਅਤੇ tail (ਲਿਖਣਾ) — ਅੱਗੇ ਵਧਦੇ ਹਨ ਅਤੇ modulo ਗਣਿਤ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਘੁੰਮਦੇ ਹਨ, ਜਿਸ ਨਾਲ ਸਿਰਜਣ ਤੋਂ ਬਾਅਦ ਕੋਈ allocation ਨਹੀਂ ਹਨ ਇੱਕ 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) ਸਥਿਰ |
ਇੱਕ ring buffer ਅਨੁਮਾਨਯੋਗ, allocation-ਮੁਕਤ FIFO ਵਿਵਹਾਰ ਫ਼ਰਾਹਮ ਕਰਦਾ ਹੈ, ਜੋ real-time ਅਤੇ embedded systems ਵਿੱਚ ਜ਼ਰੂਰੀ ਹੈ ਜਿੱਥੇ dynamic allocation ਬਹੁਤ ਹੌਲਾ ਜਾਂ ਖਤਰਨਾਕ ਹੁੰਦਾ ਹੈ।
ਇਸ ਦਾ ਸੀਮਾਬੱਧ ਆਕਾਰ ਕੁਦਰਤੀ ਬੈਕਪ੍ਰੈਸ਼ਰ ਵੀ ਕੰਮ ਕਰਦਾ ਹੈ, ਤੇਜ਼ producers ਨੂੰ ਮੈਮੋਰੀ ਸਮਾਪਤ ਕਰਨ ਤੋਂ ਰੋਕਦਾ ਹੈ।