რა არის წრიული ბუფერი (ring buffer) და როდის გამოიყენებდით მას?

Question

IT Interview Practice · Accepted Answer

**წრიული ბუფერი** არის ფიქსირებული ზომის მასივი, რომელიც ისე იქცევა, თითქოს მისი ბოლოები ქმნიან რგოლს. ორი ინდექსი — **head** (წაკითხვა) და **tail** (ჩაწერა) — წინ მოძრაობენ და ბრუნდებიან მოდულო არითმეტიკის გამოყენებით, რაც აძლევს O(1) FIFO რიგს **განაწილების გარეშე** შექმნის შემდეგ.

## როგორ მუშაობს რტალი

```text
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)
```

## Code

```python
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) ფიქსირებული |

## როდის გამოიყენება

- **სტრიმინგის / აუდიო / ვიდეო ბუფერები** — შეზღუდული, მდგრადი გამტარობა.
- **პროდიუსერი–კონსუმერი** კონვეიერები უკუწნევით.
- **ბოლო N მოვლენის ჟურნალი** (უძველესი გადაწერა).

## რატომ არის ეს მნიშვნელოვანი

წრიული ბუფერი უზრუნველყოფს წინასწარმეტყველ, განაწილების გარეშე FIFO ქცევას, რაც გადამწერი და ჩაშენებული სისტემებში ან ზღვარი რეალურ დროში, სადაც დინამიური განაწილება ძალიან ნელი ან სახطерი.

მისი შეზღუდული ზომა ასევე ემსახურება ბუნებრივ უკუწნევას, რაც მხეთ არ იძლევა სწრაფი პროდიუსერებისთვის მეხსიერების გამოწურვა.

ოპერაცია	დრო
enqueue / dequeue	O(1)
სივრცე	O(n) ფიქსირებული

როგორ მუშაობს რტალი

Code

როდის გამოიყენება

რატომ არის ეს მნიშვნელოვანი

დაკავშირებული კითხვები