บทนำ: ห้องพักคอยอัจฉริยะแห่งระบบฝังตัว

สวัสดีครับน้องๆ วิศวกรและเพื่อนนักพัฒนาชาว www.123microcontroller.com ทุกคน! กลับมาพบกับวิศวกรขอบตาดำๆ กันอีกครั้ง วันนี้เราจะมาคุยกันถึงโครงสร้างข้อมูล (Data Structures) ที่เปรียบเสมือน “ห้องพักคอย” สำหรับจัดการข้อมูลในระบบฝังตัว นั่นก็คือ Queues หรือ คิว ครับ

ในงานเขียนโปรแกรมระดับฮาร์ดแวร์ เรามักเจอสถานการณ์ที่ข้อมูลเข้ามาอย่างไม่เป็นจังหวะ เช่น การรับข้อมูลจากเซ็นเซอร์ การสื่อสารผ่านพอร์ตอนุกรม (UART) หรือแม้แต่การจัดการคิวงานในระบบปฏิบัติการ RTOS หากเราประมวลผลไม่ทัน ข้อมูลเหล่านั้นอาจจะสูญหายได้ โครงสร้างข้อมูลแบบคิวจึงเข้ามาเป็นพระเอกในการแก้ปัญหานี้ วันนี้เราจะมาเจาะลึกกันว่า แหล่งข้อมูลชั้นครูพูดถึง Queues ในบริบทที่กว้างขึ้นของ Data Structures ไว้อย่างไร และมันมีความสำคัญกับสายฮาร์ดแวร์อย่างไรครับ!

ปรัชญาการทำงานของ Queues และประยุกต์ใช้

ในบริบทของโครงสร้างข้อมูล Queue (คิว) จัดเป็นโครงสร้างข้อมูลแบบเชิงเส้น (Linear Data Structure) ที่จำกัดการเพิ่มและลบข้อมูลคนละฝั่งกัน หลักการทำงานของมันคือ First-In, First-Out (FIFO) หรือ “มาก่อนได้ก่อน” ซึ่งตรงข้ามกับ Stack ที่เป็นแบบ LIFO

เปรียบเทียบง่ายๆ คิวก็เหมือนกับ “การเข้าแถวซื้อตั๋วหนัง” หรือ “รถที่ต่อแถวเข้าด่านเก็บค่าผ่านทาง” ครับ คนที่มาต่อแถวคนแรกจะได้รับบริการก่อน และคนที่มาใหม่จะต้องไปต่อท้ายแถวเสมอ

ปฏิบัติการหลัก (Operations) ของ Queue:

คิวมีปฏิบัติการที่สำคัญอยู่ 2 อย่างหลักๆ คือ:

  1. Enqueue: การแทรกหรือเพิ่มข้อมูลใหม่เข้าไปที่ “ด้านท้าย (Rear หรือ Tail)” ของคิว
  2. Dequeue: การดึงและลบข้อมูลออกจาก “ด้านหน้า (Front หรือ Head)” ของคิว

รูปแบบการสร้างคิว (Implementations):

แหล่งข้อมูลระบุว่าเราสามารถสร้างคิวได้หลายวิธี ซึ่งแต่ละวิธีก็มีข้อดีข้อเสียต่างกัน:

  • Linear Queue ด้วย Array: เป็นวิธีที่ง่ายที่สุด แต่มีปัญหาใหญ่คือ เมื่อเราดึงข้อมูลออกจากด้านหน้าคิว (Dequeue) พื้นที่ด้านหน้าจะกลายเป็น “พื้นที่ตาย (Dead space)” ที่สูญเปล่า หากต้องการใช้พื้นที่นั้นใหม่ เราต้องเสียเวลาประมวลผลเพื่อเลื่อน (Shift) ข้อมูลที่เหลือทั้งหมดมาด้านหน้า ซึ่งไม่เหมาะกับงานที่ต้องการความเร็ว
  • Circular Queue (คิวแบบวงแหวน): นี่คือ “ท่ามาตรฐาน” ในงาน Embedded Systems ครับ! เพื่อแก้ปัญหาพื้นที่ตายของ Array เราจะจับปลาย Array มาชนกับจุดเริ่มต้น ทำให้มันทำงานเป็นวงกลม (Wrap-around) เมื่อตัวชี้ (Pointer) วิ่งไปถึงตำแหน่งสุดท้ายของ Array มันจะวนกลับมาที่ช่องแรก (Index 0) อัตโนมัติ ซึ่งมักจะคำนวณตำแหน่งด้วยตัวดำเนินการ Modulo (%)
  • Linked List Queue (คิวแบบไดนามิก): ใช้ Linked List ในการสร้าง โดยจองหน่วยความจำ (Memory Allocation) เป็นโหนดๆ ไป ทำให้คิวสามารถขยายขนาดได้เรื่อยๆ ตราบใดที่ยังมี RAM เหลือ วิธีนี้จะต้องใช้ Pointer 2 ตัว คือ front ชี้ไปที่โหนดแรก และ rear ชี้ไปที่โหนดสุดท้ายเสมอเพื่อความรวดเร็วในการ Enqueue/Dequeue

บทบาทของคิวในงานระบบและฮาร์ดแวร์:

  • Hardware FIFOs: การสื่อสารกับเซ็นเซอร์ดิจิทัลหรือพอร์ตสื่อสารอย่าง SPI และ UART หากเราใช้ซอฟต์แวร์อ่านทีละบิต (Bit-bang) จะช้ามาก ไมโครคอนโทรลเลอร์ส่วนใหญ่จึงมีวงจร FIFO (First-In, First-Out) เล็กๆ ฝังมาในฮาร์ดแวร์เพื่อรับข้อมูลมาพักไว้ก่อน แล้วค่อยแจ้งเตือน (Interrupt) ให้โปรเซสเซอร์มารับข้อมูลไปทีเดียวเมื่อคิวเต็มในระดับหนึ่ง (เช่น ครึ่งคิว)
  • Message Queues: ในระดับระบบปฏิบัติการ (OS) หรือการสื่อสารระหว่างโปรเซส (IPC) คิวถูกใช้เป็นตัวกลางในการส่งผ่านข้อมูลระหว่าง Task ต่างๆ ที่ทำงานไม่พร้อมกัน (Asynchronous) โดยข้อมูลจะถูกจัดเก็บและเข้าคิวไว้ในฝั่งของ Kernel
  • Priority Queues (คิวลำดับความสำคัญ): ในบางระบบ คิวจะถูกดัดแปลงให้ข้อมูลที่มี “ความสำคัญสูงสุด” ถูก Dequeue ออกมาประมวลผลก่อนเสมอ ไม่ว่าจะเข้ามาในคิวตอนไหนก็ตาม คล้ายกับการคัดกรองผู้ป่วยฉุกเฉินในโรงพยาบาล

Queue Data Structure Diagram

ตัวอย่างการสร้าง Circular Queue ด้วย Array สำหรับ Embedded

มาดูการสร้าง Circular Queue (วงแหวน) ด้วย Array ซึ่งเป็นโครงสร้างที่สายฮาร์ดแวร์นิยมใช้ทำ Data Buffer มากที่สุด เพราะจองหน่วยความจำแบบคงที่ล่วงหน้า (Static) ป้องกันปัญหา Memory Leak ครับ

#include <stdio.h>
#include <stdbool.h>

#define QUEUE_SIZE 8

/* โครงสร้าง Circular Queue */
typedef struct {
    int data[QUEUE_SIZE];
    int front;
    int rear;
    int count; // ใช้เก็บจำนวนข้อมูลปัจจุบันในคิว เพื่อให้เช็ค Full/Empty ง่ายขึ้น
} CircularQueue;

/* ฟังก์ชันกำหนดค่าเริ่มต้นให้คิว */
void initQueue(CircularQueue *q) {
    q->front = 0;
    q->rear = 0;
    q->count = 0;
}

/* ตรวจสอบว่าคิวเต็มหรือไม่ */
bool isFull(CircularQueue *q) {
    return (q->count == QUEUE_SIZE);
}

/* ตรวจสอบว่าคิวว่างหรือไม่ */
bool isEmpty(CircularQueue *q) {
    return (q->count == 0);
}

/* 1. Enqueue: นำข้อมูลเข้าสู่คิวที่ด้านท้าย (Rear) */
bool enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        printf("Queue Overflow! Cannot enqueue %d\n", value);
        return false;
    }
    
    // ใส่ข้อมูลและคำนวณตำแหน่ง rear ใหม่โดยใช้ Modulo เพื่อให้วนเป็นวงกลม
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % QUEUE_SIZE; 
    q->count++;
    return true;
}

/* 2. Dequeue: นำข้อมูลออกจากคิวที่ด้านหน้า (Front) */
int dequeue(CircularQueue *q, bool *success) {
    if (isEmpty(q)) {
        printf("Queue Underflow! No data to dequeue.\n");
        *success = false;
        return -1;
    }
    
    // อ่านค่า ดึงข้อมูลออก และเลื่อน front เป็นวงกลม
    int value = q->data[q->front];
    q->front = (q->front + 1) % QUEUE_SIZE;
    q->count--;
    *success = true;
    return value;
}

int main(void) {
    CircularQueue q;
    initQueue(&q);
    
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    
    bool ok;
    printf("Dequeued: %d\n", dequeue(&q, &ok)); // จะได้ 10 (FIFO)
    printf("Dequeued: %d\n", dequeue(&q, &ok)); // จะได้ 20
    
    return 0;
}

สกัดกั้นภัยคุกคามจากการจัดการ Queue ผิดพลาด

การจัดการคิวในภาษา C มีหลุมพรางที่ต้องระวังเพื่อป้องกันไม่ให้โปรแกรมหรือฮาร์ดแวร์แครช ดังนี้ครับ:

  1. ระวัง Buffer Overflow และ Underflow เสมอ: ก่อนทำ Enqueue คุณ ต้อง ตรวจสอบว่าคิวเต็มหรือไม่ (Queue Full / Overflow) เพื่อป้องกันการเขียนข้อมูลทับข้อมูลเก่าที่ยังไม่ได้อ่าน และก่อน Dequeue ต้องตรวจสอบว่าคิวว่างหรือไม่ (Queue Empty / Underflow) เพื่อป้องกันการดึงค่าขยะ (Garbage Value) ไปใช้งาน
  2. การทำ Modulo Arithmetic ให้เร็วปรี๊ด: การคำนวณคิววงแหวนด้วยคำสั่ง index % QUEUE_SIZE อาจใช้ไซเคิลของ CPU เยอะในชิปที่ไม่มีวงจรหารฮาร์ดแวร์ ทริคของสาย Embedded คือการกำหนดขนาด QUEUE_SIZE ให้เป็นเลขยกกำลัง 2 (เช่น 8, 16, 256) แล้วใช้ Bitwise AND (&) แทนคำสั่ง % เช่น index = (index + 1) & (QUEUE_SIZE - 1); วิธีนี้จะเร็วกว่ามากครับ
  3. ปัญหา Memory Leak ใน Linked List Queue: หากคุณอิมพลีเมนต์คิวด้วย Linked List ร่วมกับ malloc() เวลาที่คุณทำ Dequeue สิ่งที่สำคัญที่สุดคือการใช้ฟังก์ชัน free() คืนพื้นที่ของโหนดที่ถูกดึงออกให้กับระบบเสมอ การละเลยจุดนี้จะทำให้ RAM ของบอร์ดคุณหมดเกลี้ยง (Memory Leak)
  4. จัดการ Pointer ผีดิบ (Dangling Pointers): เมื่อคุณ Dequeue จนคิวกลายเป็นคิวว่าง (Empty) ต้องแน่ใจว่าตัวชี้ front และ rear (หรือ tail) ถูกเซ็ตกลับเป็น NULL เสมอ เพื่อป้องกันการอ้างอิงตำแหน่งที่ไม่มีอยู่จริง

สรุป (Conclusion)

Queue (FIFO) เป็นโครงสร้างข้อมูลที่เรียบง่ายแต่ทรงพลังมากครับ มันเป็นหัวใจสำคัญในการสร้างระบบบัฟเฟอร์ (Buffer) เพื่อรองรับข้อมูลที่หลั่งไหลเข้ามาอย่างไม่เป็นระเบียบ ทั้งในระดับฮาร์ดแวร์ (Hardware FIFOs), การส่งผ่านข้อมูลด้วย DMA, หรือคิวข้อความในระบบปฏิบัติการ (Message Queues) การเลือกใช้คิวแบบ Circular Buffer ถือเป็นไม้ตายที่นักพัฒนาสมองกลฝังตัวต้องเขียนให้เป็นและใช้ให้คล่องครับ

หากเพื่อนๆ สนใจอยากเรียนรู้วิธีการส่งข้อมูลจากเซ็นเซอร์เข้า Circular Queue ผ่านระบบ Interrupt แบบลึกซึ้ง หรืออยากนำคิวไปใช้จัดการงานใน RTOS อย่าลืมแวะเข้ามาติดตามและตั้งกระทู้พูดคุยกันต่อที่เว็บ www.123microcontroller.com ของพวกเรานะครับ แล้วพบกันใหม่ในบทความประลองโครงสร้างข้อมูลหน้า Happy Coding ครับทุกคน!