[TH] Queue Data Structure

บทความนี้แนะนำการใช้คลาส list ใน Micropython มาประยุกต์เป็นโครงสร้างข้อมูลคิวที่มีจำนวนสมาชิกจำกัด และทำงานตามหลักการ FIFO (First-In-First-Out) ซึ่งสามารถนำไปประยุกต์ใช้ได้หลากหลาย เช่น ใช้เป็นที่เก็บข้อมูลและเมื่อข้อมูลมีเต็มแล้วแต่ต้องการนำข้อมูลใหม่ใส่เข้าไป ดังนั้น จึงต้องนำข้อมูลเก่าอันดับที่ 1 ที่ใส่เข้ามาออกไป ซึ่งตรงกับหลักการของ FIFO เป็นต้น โดยตัวอย่างในบทความนี้ใช้บอร์ด dCore-miniML (ในภาพที่ 1) อ่านข้อมูลอุณหภูมิของชิพมาเก็บไว้ในโครงสร้างแบบคิวและแสดงผลออกมาในลักษณะของกราฟแท่ง และไมโครไพธอนที่นำมาใช้เป็นเฟิร์มแวร์รุ่น 1.16 (2021-06-23) สำหรับ ESP Module (SPIRAM)

โครงสร้างข้อมูลแบบคิว

โครงสร้างข้อมูลแบบคิว (Queue) เป็นการเก็บข้อมูลตามลำดับและนำออกข้อมูลตามลำดับด้วยหลักการใครมาก่อนเก็บก่อนและใครมาก่อนได้ออกไปก่อน หรือ FIFO ซึ่งคำสั่งสำหรับสั่งการโครงสร้างข้อมูลแบบคิวประกอบด้วย

• push( x ) สำหรับการนำเข้าข้อมูล x ไปเก็บในคิว ดังภาพที่ 2
• ค่าที่นำออก = pop() สำหรับนำออกข้อมูลตัวแรกสุดในคิว ดังภาพที่ 3

การนำเข้าข้อมูลในคิวจะเกิดผลลัพธ์ของการทำงาน 2 ลักษณะ คือ

• การนำเข้าสำเร็จถ้าคิวยังไม่เต็ม
• การนำเข้าล้มเหลวถ้าข้อมูลในนคิวมีเต็มแล้ว หรือเกิด Queue Overflow

สำหรับการนำออกข้อมูลจากคิวมีผลลัพธ์ของการทำงาน 2 ลักษณะเช่นกัน คือ

• การนำออกสำเร็จ
• การนำออกล้มเกลวเนื่องจากคิวไม่มีข้อมูลใด ๆ มาก่อน หรือถูกนำออกไปจนหมดแล้ว หรือเกิด Queue Empty

จากแนวคิดที่กล่าวมาสรุปได้ว่า ต้องอาศัยการใช้คลาส list เป็นที่เก็บข้อมูล โดยต้องมีการจำกัดจำนวนสมาชิกของ list และต้องมีคำสั่ง push และ pop ที่ทำงานตามหลักการที่กล่าวมา ซึ่งโครงสร้างของคลาสที่จะสร้างขึ้นเป็นดังนี้

class Queue:
    def __init__(self,maxN=10):
        self.idx = 0
class Queue:
    def __init__(self,maxN=10):
        self.items = []
        self.idx = 0
        self.topOfQ = maxN
    def push(self,x):
        pass
    def pop(self):
        return 0

ในคลาสที่สร้างได้สร้างตัวแปร idx สำหรับเก็บจำนวนสมาชิกในคิว และตัวแปร topOfQ สำหรับเก็บจำนวนสมาชิกสูงสุดที่คิวรองรับได้ พร้อมทั้งสร้างวัตถุประเภทลิสต์ชื่อ items สำหรับเก็บข้อมูลที่นำเข้าด้วยคำสั่ง push() และนำออกด้วยคำสั่ง pop()

การนำข้อมูลเข้าคิว

ขั้นตอนวิธีการนำเข้าข้อมูล x เก็บลงในโครงสร้างข้อมูลคิวโดยเก็บในวัตถุประเภทลิสต์ด้วยคำสั่ง append() เป็นดังนี้

1. ถ้า idx เท่ากับ topOfQ หมายถึงคิวเต็มแล้วให้เตือน Queue Overflow
2. ถ้าไม่ใช่
   1. เพิ่มข้อมูลลงคิว
   2. เพิ่มค่า idx

ดังนั้น โค้ดของเมธอดหรือฟังก์ชัน push(x) จึงเป็นดังนี้

    def push(self,x):
        if self.idx == self.topOfQ:
            print("Queue Overflow!")
            return
        self.items.append(x)
        self.idx += 1

เมื่อทดสอบโปรแกรมตามโค้ดต่อไปนี้ด้วยการสร้างคิวขนาด 5 สมาชิกแต่ใส่ข้อมูล 0,1,2,3,4,5,6 ซึ่งเกินจะพบว่าในคิวมีเพียง 0,1,2,3 และ 4 พร้อมทั้งแจ้งเตือน 2 ครั้งเนื่องจากคิวเต็มแล้วดังภาพที่ 4

class Queue:
    def __init__(self,maxN=10):
        self.items = []
        self.idx = 0
        self.topOfQ = maxN
    def push(self,x):
        if self.idx == self.topOfQ:
            print("Queue Overflow!")
            return
        self.items.append(x)
        self.idx += 1
    def pop(self):
        return 0
myQueue = Queue(5)

for i in range(7):
    myQueue.push(i)
    print(myQueue.items)

การนำข้อมูลออกจากคิว

หลักการทำงานของการนำข้อมูลออกจากคิวคือ นำสมาชิกตัวแรกออกไปก่อน ดังขั้นตอนวิธีต่อไปนี้

1. ถ้าสมาชิกในคิวเป็น 0 ให้แจ้งเตือนว่า คิวว่าง และออกจากการทำงาน
2. ถ้าไม่ใช่
   1. ทำการกลับค่าข้อมูลในลิสต์
   2. นำข้อมูลที่ถูกนำออกด้วย pop()
   3. ทำการกลับค่าข้อมูลในลิสต์อีกครั้ง
   4. คืนค่าที่อ่านมาในขั้นตอน 2

ด้วยเหตุนี้จึงเขียนโค้ดสำหรับเมธอด pop ได้ดังโค้ดด้านล่าง ซึ่งจะพบว่าการทำงานจะช้ามากถ้าสมาชิกมีจำนวนมากเนื่องจากต้องกลับค่าของลิสต์ 2 ครั้งเพื่อให้การทำงานของคำสั่ง pop() ของคลาสลิต์ทำงานถูกต้อง ทั้งนี้เนื่องจากการ pop() ของคลาสลิสต์เป็นการนำข้อมูลตัวสุดท้ายออก ซึ่งเป็นหลักการทำงานของโครงสร้างข้อมูลแบบสแด็ก (Stack)

    def pop(self):
        if self.idx == 0:
            print("Queue empty!")
            return None
        self.idx -= 1
        self.items.reverse()
        x = self.items.pop()
        self.items.reverse()
        return x

ตัวอย่างโปรแกรมที่ทดสอบการทำงานทั้งการ push() และ pop() เป็นดังนี้ โดยตัวอย่างของการทำงานเป็นดังภาพที่ 5

class Queue:
    def __init__(self,maxN=10):
        self.items = []
        self.idx = 0
        self.topOfQ = maxN
    def push(self,x):
        if self.idx == self.topOfQ:
            print("Queue Overflow!")
            return
        self.items.append(x)
        self.idx += 1
    def pop(self):
        if self.idx == 0:
            print("Queue empty!")
            return None
        self.idx -= 1
        self.items.reverse()
        x = self.items.pop()
        self.items.reverse()
        return x
myQueue = Queue(5)

for i in range(7):
    myQueue.push(i)
for i in range(6):
    print(myQueue.pop())
    print(myQueue.items)

ตัวอย่างการนำไปใช้

ตัวอย่างโปรแกรมต่อไปนี้เป็นการอ่านค่าอุณหภูมิของ esp32 มาเก็บลงในคิวของข้อมูลและนำข้อมูลจากคิวมาแสดงเป็นกราฟแท่งดังตัวอย่างในภาพที่ 1 โดยวิธีการติดต่อกับ st7735 สามารถอ่านได้จากบทความก่อนหน้านี้

# demo-jQueue.py
from jQueue import Queue
from st7735 import TFT
from sysfont import sysfont
from machine import SPI,Pin
import machine as mc
import time
import math
import esp32

mc.freq(240000000)
spi = SPI(2, baudrate=27000000,
          sck=Pin(14), mosi=Pin(12),
          polarity=0, phase=0)
# dc, rst, cs
tft=TFT(spi,15,13,2)
tft.init_7735(tft.GREENTAB80x160)
tft.fill(TFT.BLACK)
dataQ = Queue(160)
for i in range(160):
    dataQ.push(0)
while True:
    tft.fill(TFT.BLACK)
    # input
    tf = esp32.raw_temperature()
    tc = int((tf-32.0)/1.8)
    # process
    dataQ.pop()
    dataQ.push(tc)
    # show
    for i in range(160):
        value = dataQ.items[i]
        if value >= 49:
            tft.vline((i,80-value), value, TFT.RED)
        else:
            tft.vline((i,80-value), value, TFT.GREEN)
    time.sleep_ms(1000)

นอกจากนี้ได้แยกคลาสของโครงสร้างคิวออกเป็นอีกไฟล์ดังนี้

class Queue:
    def __init__(self,maxN=10):
        self.items = []
        self.idx = 0
        self.topOfQ = maxN
    def push(self,x):
        if self.idx == self.topOfQ:
            print("Queue Overflow!")
            return False
        self.items.append(x)
        self.idx += 1
        return True
    def pop(self):
        if self.idx == 0:
            print("Queue empty!")
            return None
        self.idx -= 1
        self.items.reverse()
        x = self.items.pop()
        self.items.reverse()
        return x

จากตัวอย่างด้านบนจะพบว่าการแบ่งโซนของกราฟเขียวและแดงเกิดจากการกำหนดค่า 49 เป็นเกณฑ์ในการตัดสินใจ ถ้าต้องการเปลี่ยนให้ทุกอย่างปรับค่าเองตามลักษณะของข้อมูลเช่น ใช้เกณฑ์ด้วยค่าเฉลี่ยของค่าที่มีอยู่ในคิวจะเปลี่ยนโค้ดได้ดังนี้

    minVal = 100
    maxVal = 0
    avgVal = int(math.fabs(maxVal+minVal)/2)
    tft.fill(TFT.BLACK)
    for i in range(1,160):
        value = dataQ.items[i]
        if minVal > value:
            minVal = value
            avgVal = int(math.fabs(maxVal+minVal)/2)
        if maxVal < value:
            maxVal = value
            avgVal = int(math.fabs(maxVal+minVal)/2)
        if value > avgVal:
            tft.vline((i,80-value), value, TFT.RED)
        else:
            tft.vline((i,80-value), value, TFT.GREEN)

สรุป

จากบทความนี้ผู้อ่านได้รู้จักกับโครงสร้างข้อมูลประเภทคิว วิธีการเขียนโปรแกรมเพื่อทำงานตามหลักการของโครงสร้างข้อมูลแบบคิว และตัวอย่างการเขียนโปรแกรมเพื่อประยุกต์ใช้งานกับการแสดงกราฟอุณหภูมิของ CPU นอกจากนี้จะพบว่าเมื่อมีข้อมูลมาก ๆ เราสามารถนำข้อมูลการแบ่งหรือดำเนินการใด ๆ กับข้อมูลจะทำให้การแสดงผลนั้นเปลี่ยนไป เช่น ในตัวอย่างนี้เมื่อเปลี่ยนการกำหนดค่าตัดสินใจจากค่าคงที่เรามโนขึ้นมาเองไปเป็นค่าเฉลี่ยที่เกิดขึ้นจริงจะทำให้เห็นผลลัพธ์ของกราฟได้ว่าเป็นสีแดงหรือเขียวมากกว่ากันหรือเท่า ๆ กัน

สุดท้ายนี้ขอให้สนุกกับการเขียนโปรแกรมครับ

ท่านใดต้องการพูดคุยสามารถคอมเมนท์ไว้ได้เลยครับ

(C) 2020-2021, โดย อ.ดนัย เจษฎาฐิติกุล/อ.จารุต บุศราทิจ
ปรับปรุงเมื่อ 2021-08-17, 2021-11-23