บัพเฟอร์วงกลม

บัพเฟอร์วงกลม (อังกฤษ: circular buffer) เป็นโครงสร้างข้อมูลประเภทหนึ่ง ซึ่งเป็นการจัดการข้อมูลในรูปแบบวงกลม แต่ขนาดหรือความจุของข้อมูลจะต้องจำกัดไม่สามารถเพิ่มขึ้นได้ หลักการทำงานส่วนใหญ่จะเป็นการเก็บข้อมูลแบบตามลำดับ จนข้อมูลเต็มก็จะทำการเพิ่มข้อมูลไปใหม่ โดยใช้หลักการ FIFO (FIRST IN FIRST OUT) หรือ มาก่อนก็ออกก่อน

หลักการทำงาน

• ในตอนแรกถ้า array หรือที่เก็บข้อมูลว่างเปล่า จะนำข้อมูลไปใส่ได้เลย ( จริง ๆแล้วตำแหน่งตอนเริ่มต้นไม่สำคัญ เพราะตอนอ่านข้อมูลพิจารณา Pointer เป็นหลัก )
• ถ้าใส่ข้อมูลไปจนเต็มแล้ว ถ้าต้องการใส่ข้อมูลเพิ่ม ก็ทำการใส่ในตำแหน่งถัดไป ( จะทับกับข้อมูลที่ใส่มาก่อนหน้า เพราะเป็นวงกลม )
• ซึ่งถ้ายิ่งใส่มาเรื่อย ๆ ข้อมูลก็จะทับกัน ไปเรื่อย ๆ ทำให้ข้อมูลเก่าที่ใส่เข้ามา หายไปแทนที่ด้วยข้อมูลใหม่
• ซึ่งตอนอ่านข้อมูลออกจากระบบ จะอ่านตามลำดับ ตัวที่มาก่อนจะออกมาก่อน ( โดยดูจาก Pointer )

ความซับซ้อนของการทำงาน

จะขึ้นอยู่กับขนาดของข้อมูลทั้งหมด ดังนั้นสรุปได้ว่า Big(o) = O(n) จะได้ว่า Best Case คือ ขนาดของข้อมูลมีน้อยที่สุดหรือไม่มีเลย และ Worst Case คือ ขนาดของข้อมูลมีมากที่สุด

ตัวอย่างการเขียนโปรแกรม

ตัวอย่างการเขียนโปรแกรมด้วยภาษาไพทอน (Python)

class CircularBuffer:
    def __init__(self, size):
        self.size = size
        self.data = [None]*size
        self.cur = 0

    def append(self, x):
        self.data[self.cur] = x
        self.cur = (self.cur + 1) % self.size


    def get(self):
        return self.data[self.cur:]+self.data[:self.cur]

อ้างอิง

O'Reilly Media. (2002). Implementing a Ring Buffer. Python Cookbook. Retrieved 30 April 2018.