بافر حلقه‌ای

دستورالعمل‌ها

«بافر حلقه‌ای»، «بافر چرخه‌ای» یا «بافر حلقوی» یک ساختار داده است که از یک بافر واحد با اندازه‌ی ثابت استفاده می‌کند، طوری‌که انگار دو سر آن به هم متصل شده است.

بافر حلقه‌ای ابتدا خالی است و طولی از پیش تعیین‌شده دارد. برای مثال، این یک بافر ۷ عنصری است:

[ ][ ][ ][ ][ ][ ][ ]

فرض کنید عدد ۱ در میانه‌ی بافر نوشته می‌شود (مکان دقیق شروع در بافر حلقه‌ای اهمیتی ندارد):

[ ][ ][ ][1][ ][ ][ ]

سپس فرض کنید دو عنصر دیگر، ۲ و ۳، اضافه می‌شوند که بعد از ۱ قرار می‌گیرند:

[ ][ ][ ][1][2][3][ ]

اگر سپس دو عنصر از بافر حذف شوند، قدیمی‌ترین مقدارهای داخل بافر حذف می‌شوند. دو عنصری که در این حالت حذف می‌شوند ۱ و ۲ هستند و بافر تنها با ۳ باقی می‌ماند:

[ ][ ][ ][ ][ ][3][ ]

اگر بافر ۷ عنصر داشته باشد، کاملاً پر است:

[5][6][7][8][9][3][4]

وقتی بافر پر باشد، خطایی ایجاد می‌شود و به کاربر اطلاع می‌دهد که نوشتن‌های بعدی تا آزاد شدن یک خانه مسدود است.

وقتی بافر پر است، کاربر می‌تواند با یک نوشتن اجباری، قدیمی‌ترین داده را بازنویسی کند. در این حالت، دو عنصر دیگر، A و B، اضافه می‌شوند و ۳ و ۴ را بازنویسی می‌کنند:

[5][6][7][8][9][A][B]

۳ و ۴ با A و B جایگزین شده‌اند و اکنون ۵ قدیمی‌ترین داده‌ی بافر است. در پایان، اگر دو عنصر حذف شوند، آنچه برگردانده می‌شود ۵ و ۶ است و بافر زیر را به دست می‌دهد:

[ ][ ][7][8][9][A][B]

چون فضا موجود است، اگر کاربر دوباره از بازنویسی برای ذخیره‌ی C و D استفاده کند، فضایی که پیش‌تر ۵ و ۶ در آن ذخیره شده بودند استفاده می‌شود، نه محل ۷ و ۸. ۷ هنوز قدیمی‌ترین عنصر است و بافر دوباره پر شده است.

[C][D][7][8][9][A][B]

---

منبع

Wikipedia