[TH] Queue data structure with array and Singly Linked List.

บทความนี้เป็นการอธิบายเกี่ยวกับโครงสร้างข้อมูลแบบคิว (Queue) ซึ่งได้เคยเขียนถึงไปในบทความ Queue Data Structure ที่เป็นภาษาไพธอนและถูกนำไปใช้บ่อยกับตัวอย่างของ MicroPython แต่บทความนี้เป็นภาษา C ที่เขียนผ่าน Arduino IDE เพื่อใช้งานกับบอร์ดไมโครคอนโทรลเลอร์ LGT8F328P, SAM-D21, ESP8266, ESP32 และ ESP32-S2 ดังภาพที่ 1 โดยยกตัวอย่างการนำโครงสร้างแถวลำดับ และลิงค์ลิสต์เดี่ยวมาเป็นโครงสร้างข้อมูลแบบคิว และคงเป็นบทความสุดท้ายบน JarutEx แล้วครับ

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

คิวเป็นโครงสร้างข้อมูลที่มีจำนวนสมาชิกจำกัดที่ทำงานตามหลักของ FIFO (First-in-First-out) สามารถนำไปประยุกต์ใช้ได้หลากหลาย เช่น ใช้เป็นที่เก็บข้อมูลและเมื่อข้อมูลมีเต็มแล้วแต่ต้องการนำข้อมูลใหม่ใส่เข้าไป ดังนั้น จึงต้องนำข้อมูลเก่าอันดับที่ 1 ที่ใส่เข้ามาออกไป ซึ่งตรงกับหลักการของ FIFO หรือ หลักการใครมาก่อนเก็บก่อนและใครมาก่อนได้ออกไปก่อน  เป็นต้น 

องค์ประกอบของโครงสร้างข้อมูลคิวประกอบด้วย 2 ส่วน คือ

1. โหนดเก็บข้อมูล ซึ่งสามารถเลือกใช้โครงสร้างข้อมูลแบบแถวลำดับเป็นที่เก็บข้อมูล หรือโครงสร้างข้อมูลแบบลิงค์ลิสต์
2. ชุดคำสั่งสำหรับใช้งานโครงสร้างข้อมูลภายใต้การทำงานแบบคิว

คำสั่งสำหรับใช้งานแบบคิวประกอบด้วย 2 คำสั่ง คือ

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

การนำเข้ามีขั้นตอนวิธีในการทำงาน 2 กรณี คือ

1. นำเข้าข้อมูลเข้าคิวที่ยังสามารถเก็บข้อมูลได้
2. นำเข้าข้อมูลให้กับคิวที่มีจำนวนสมาชิกเต็มตามที่กำหนดไว้แล้ว อันส่งผลให้เกิด Queue Overflow

กรณีของการนำออกมี 2 ลักษณะเช่นเดียวกัน คือ

1. กรณีของการนำออกจากคิวที่มีข้อมูลอยู่
2. กรณีที่นำออกข้อมูลโดยที่คิวว่างอันส่งผลให้เกิดปัญหาที่เรียกว่า Queue Underflow

ขั้นตอนวิธีของการ push(x)

การนำเข้าข้อมูลลงในโครงสร้างข้อมูลคิวมีขั้นตอนดังนี้

1. ตรวจสอบจำนวนสมาชิก
2. ถ้ามีสมาชิกเต็มอยู่แล้ว ให้รายงาน Queue Overflow แล้วออกจากการทำงาน
3. นำข้อมูลไปไว้ท้ายสุดของคิว
4. เพิ่มค่าตัวนับจำนวนสมาชิกในคิวขึ้น 1 ค่า

ขั้นตอนวิธีของการ pop()

การนำข้อมูลออกจากคิวมีลำดับขั้นดังนี้

1. ตรวจสอบจำนวนสมาชิกในคิว
2. ถ้าจำนวนสมาชิกเป็น 0 ให้รายงาน Queue Underflow แล้วออกจากการทำงาน
3. จำค่าสมาชิกตัวแรกสุด
4. ลดค่าตัวนับจำนวนสมาชิกในคิวลง 1 ค่า
5. เลื่อนสมาชิกตัวถัดไปมาแทนตัวที่ถูกดึงออก
6. คืนค่าสมาชิกที่จำไว้จากข้อ 3

คิวแบบใช้แถวลำดับ

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

ข้อมูล

ตัวแปรสำหรับเก็บข้อมูลและจำนวนสมาชิกเขียนดังนี้

const uint8_t queMaxElm = 5;
uint8_t queData[5];
uint8_t queElmCounter = 0;

bool queInit() {
  queElmCounter = 0;
  return true;
}

การ push

ฟังก์ชันการ push() มีโค้ดดังต่อไปนี้

bool quePush( uint8_t x ) {
  if (queElmCounter == queMaxElm) {
    return false;
  }
  queData[queElmCounter] = x;
  queElmCounter += 1;
  return true;
}

การ pop

ฟังก์ชันสำหรับ pop() เพื่อดึงข้อมูลออกจากคิวเป็นดังนี้

bool quePop( uint8_t& x ) {
  if (queElmCounter == 0) {
    return false;
  }
  x = queData[0];
  queElmCounter -= 1;
  if (queElmCounter > 0) {
    for (int i = 0; i < queElmCounter; i++) {
      queData[i] = queData[i + 1];
    }
  }
  return true;
}

ตัวอย่างโปรแกรม

ตัวอย่างโปรแกรมสำหรับทดสอบการทำงานของคิวเป็นดังนี้ โดยตัวอย่างผลลัพธ์เป็นดังภาพที่ 4

const uint8_t queMaxElm = 5;
uint8_t queData[5];
uint8_t queElmCounter = 0;

bool queInit() {
  queElmCounter = 0;
  return true;
}

bool quePush( uint8_t x ) {
  if (queElmCounter == queMaxElm) {
    return false;
  }
  queData[queElmCounter] = x;
  queElmCounter += 1;
  return true;
}

bool quePop( uint8_t& x ) {
  if (queElmCounter == 0) {
    return false;
  }
  x = queData[0];
  queElmCounter -= 1;
  if (queElmCounter > 0) {
    for (int i = 0; i < queElmCounter; i++) {
      queData[i] = queData[i + 1];
    }
  }
  return true;
}

void queShow() {
  Serial.print("Queue data=[ ");
  for (int i = 0; i < queElmCounter; i++) {
    Serial.print(queData[i]);
    Serial.print(" ");
  }
  Serial.println("]");
}

void queDemo() {
  queInit();
  queShow();
  for (int i = 0; i < 6; i++) {
    Serial.print("push(");
    Serial.print(i);
    Serial.print(") ... ");
    if (quePush(i)) {
      Serial.println("done.");
      queShow();
    } else {
      Serial.println(" Queue overflow!");
    }
  }
  uint8_t data;
  for (int i = 0; i < 6; i++) {
    Serial.print("pop() ... ");
    if (quePop(data)) {
      Serial.println(data);
      queShow();
    } else {
      Serial.println(" Queue underflow!");
    }
  }
}

void setup() {
  Serial.begin( 9600 );

}

void loop() {
  queDemo();
  delay(30000);
}

คิวแบบใช้ลิงค์ลิสเดี่ยว

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

ข้อมูล

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

const uint8_t queMaxElm = 5;
struct queNode {
  uint8_t data;
  queNode * next;
};

queNode * queRoot;
queNode * queCurrentNode;
queNode * queNewNode;
uint8_t queElmCounter = 0;

bool queInit() {
  queElmCounter = 0;
  queRoot = NULL;
  queCurrentNode = NULL;
  queNewNode = NULL;
  return true;
}

การ push

การ push() หรือการเพิ่มโหนดมีขั้นตอนที่มากกว่าใช้แถวลำดับดังนี้

1. ถ้าจำนวนสมาชิกครบแล้วให้ออกจากฟังก์ชัน
2. จองหน่วยความจำ ถ้ามีไม่เพียงพอให้ออกจากฟังก์ชัน
3. นำค่า x ไปเก็บใน  data
4. ถ้าเป็นโหนดแรกให้กำหนด queRoot และ queCurrentNode ชี้ไปที่โหนดที่สร้างขึ้นจากข้อ 2
5. เพิ่มค่าตัวนับจำนวนสมาชิก

bool quePush( uint8_t x ) {
  if (queElmCounter == queMaxElm) {
    return false;
  }
  queNewNode = (queNode*)malloc( sizeof( queNode ) );
  if (queNewNode == NULL) {
    return false;
  }
  queNewNode->next = NULL;
  queNewNode->data = x;
  if (queElmCounter == 0) {
    queRoot = queNewNode;
  } else {
    queCurrentNode->next = queNewNode;
  }
  queCurrentNode = queNewNode;
  queElmCounter += 1;
  return true;
}

การ pop

การ pop() มีขั้นตอนการทำงานดังนี้

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

bool quePop( uint8_t& x ) {
  if (queElmCounter == 0) {
    return false;
  }

  if (queRoot == queCurrentNode) {
    x = queRoot->data;
    free(queRoot);
    queRoot = NULL;
    queCurrentNode = NULL;
  } else {
    queNode * p = queRoot;
    x = p->data;
    queRoot = p->next;
    free(p);
  }
  queElmCounter -= 1;
  return true;
}

ตัวอย่างโปรแกรม

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

const uint8_t queMaxElm = 5;
struct queNode {
  uint8_t data;
  queNode * next;
};

queNode * queRoot;
queNode * queCurrentNode;
queNode * queNewNode;
uint8_t queElmCounter = 0;

bool queInit() {
  queElmCounter = 0;
  queRoot = NULL;
  queCurrentNode = NULL;
  queNewNode = NULL;
  return true;
}

bool quePush( uint8_t x ) {
  if (queElmCounter == queMaxElm) {
    return false;
  }
  queNewNode = (queNode*)malloc( sizeof( queNode ) );
  if (queNewNode == NULL) {
    return false;
  }
  queNewNode->next = NULL;
  queNewNode->data = x;
  if (queElmCounter == 0) {
    queRoot = queNewNode;
  } else {
    queCurrentNode->next = queNewNode;
  }
  queCurrentNode = queNewNode;
  queElmCounter += 1;
  return true;
}

bool quePop( uint8_t& x ) {
  if (queElmCounter == 0) {
    return false;
  }

  if (queRoot == queCurrentNode) {
    x = queRoot->data;
    free(queRoot);
    queRoot = NULL;
    queCurrentNode = NULL;
  } else {
    queNode * p = queRoot;
    x = p->data;
    queRoot = p->next;
    free(p);
  }
  queElmCounter -= 1;
  return true;
}

void queShow() {
  Serial.print("Queue data=[ ");
  queNode * currentNode = queRoot;
  while (currentNode) {
    Serial.print(currentNode->data);
    Serial.print(" ");
    currentNode = currentNode->next;
  }
  Serial.println("]");
}

void queDemo() {
  queInit();
  queShow();
  for (int i = 0; i < 6; i++) {
    Serial.print("push(");
    Serial.print(i);
    Serial.print(") ... ");
    if (quePush(i)) {
      Serial.println("done.");
      queShow();
    } else {
      Serial.println(" Queue overflow! or not enough memory!");
    }
  }
  uint8_t data;
  for (int i = 0; i < 6; i++) {
    Serial.print("pop() ... ");
    if (quePop(data)) {
      Serial.println(data);
      queShow();
    } else {
      Serial.println(" Queue underflow!");
    }
  }
}

void setup() {
  Serial.begin( 9600 );

}

void loop() {
  queDemo();
  delay(30000);
}

สรุป

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

(C) 2022, โดย อ.ดนัย เจษฎาฐิติกุล/อ.จารุต บุศราทิจ
ปรับปรุงเมื่อ 2022-01-06, 2022-02-21