[TH] Stack data structure with Singly Linked List.

บทความนี้เป็นการอธิบายเกี่ยวกับโครงสร้างข้อมูลแบบสแต็ก (Stack) เพื่อเขียนโปรแกรมด้วยภาษา C บนแพล็ตฟอร์มต่าง ๆ โดยใช้โครงสร้างข้อมูลแบบลิงค์ลิสต์เดี่ยวเป็นที่เก็บข้อมูลของสแต็กพร้อมตัวอย่างการแถวลำดับเป็นที่เก็บข้อมูล และทดสอบการทำงานกับบอร์ดไมโครคอนโทรลเลอร์ LGT8F328P, SAM-D21, ESP8266, ESP32 และ ESP32-S2 ดังภาพที่ 1 และ 2 ส่วนกรณีที่ต้องการไปใช้กับแพล็ตฟอร์มอื่น ๆ ยังคงสามารถดัดแปลงโค้ดเพื่อนำไปใช้ได้เช่นเดียวกัน

ภาพที่ 1 บอร์ดไมโครคอนโทรลเลอร์ ESP32, LGY8P326P และ SAM-D21

ภาพที่ 2 บอร์ด ESP32-S2 (Ai Tinker ESP-12K)

โครงสร้างข้อมูลแบบสแต็ก

สแต็กเป็นโครงสร้างข้อมูลที่มีจำนวนสมาชิกจำกัดที่ทำงานตามหลักของ LIFO (Last-in-First-out) หรือ ข้อมูลที่นำเข้ามาก่อนจะถูกนำออกทีหลังหรือข้อมูลที่ถูกนำเข้าทีหลังจะถูกนำออกก่อน ดังภาพที่ 3 ซึ่งสามารถนำไปใช้เกี่ยวกับการเรียกใช้โปรแกรมย่อย/การทำซ้ำด้วยการจำตำแหน่งของหน่วยความจำที่ถูกเรียกใช้หรือจะถูกเรียกใช้เป็นตำแหน่งถัดไปเพื่อให้หน่วยประมวลผลไปทำคำสั่งในตำแหน่งอื่นก่อน หรือประยุกต์ใช้กับการคำนวณนิพจน์ทางคณิตศาสตร์ตามหลัก prefix เพื่อแปลงนิพจน์แบบ infix ให้เป็นเป็น prefix เพื่อนำผลลัพธ์จาก prefix ไปประมวลผลด้วยการใช้โครงสร้างแบบคิว (จะกล่าวถึงโครงสร้างข้อมูลแบบคิวแบบภาษา C ในบทความหน้า ส่วนภาษา Python สามารถอ่านได้จากบทความ Queue Data Structure) ในการประมวลผล

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

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

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

push(X) สำหรับนำเข้าข้อมูล x ไปเก็บในสแต็ก ดังภาพที่ 4
ค่าที่นำออก = pop() สำหรับนำออกข้อมูลจากสแต็กซึ่งข้อมูลนั้นเป็นข้อมูลบำดับสุดท้ายที่นำเข้าไปหลังสุด ดังภาพที่ 5

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

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

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

กรณีของการนำออกจากสแต็กที่มีข้อมูลอยู่
กรณีที่นำออกข้อมูลโดยที่สแตกว่างอันส่งผลให้เกิดปัญหาที่เรียกว่า Stack Underflow

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

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

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

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

กานำข้อมูลออกจากสแตกมีลำดับขั้นดังนี้

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

สแต็กแบบใช้แถวลำดับ

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

ข้อมูล

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

const uint8_t stkMaxElm = 5;
uint8_t stkData[5];
uint8_t stkElmCounter = 0;

bool stkInit() {
  stkElmCounter = 0;
  return true;
}

การ push

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

bool stkPush( uint8_t x ) {
  if (stkElmCounter == stkMaxElm) {
    return false;
  }
  stkData[stkElmCounter] = x;
  stkElmCounter += 1;
  return true;
}

การ pop

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

bool stkPop( uint8_t& x ) {
  if (stkElmCounter == 0) {
    return false;
  }
  x = stkData[stkElmCounter - 1];
  stkElmCounter -= 1;
  return true;
}

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

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

const uint8_t stkMaxElm = 5;
uint8_t stkData[5];
uint8_t stkElmCounter = 0;

bool stkInit() {
  stkElmCounter = 0;
  return true;
}

bool stkPush( uint8_t x ) {
  if (stkElmCounter == stkMaxElm) {
    return false;
  }
  stkData[stkElmCounter] = x;
  stkElmCounter += 1;
  return true;
}

bool stkPop( uint8_t& x ) {
  if (stkElmCounter == 0) {
    return false;
  }
  x = stkData[stkElmCounter - 1];
  stkElmCounter -= 1;
  return true;
}

void stkShow() {
  Serial.print("Stack data=[ ");
  for (int i = 0; i < stkElmCounter; i++) {
    Serial.print(stkData[i]);
    Serial.print(" ");
  }
  Serial.println("]");
}

void setup() {
  Serial.begin( 9600 );
  stkInit();
  stkShow();
  for (int i = 0; i < 6; i++) {
    Serial.print("push(");
    Serial.print(i);
    Serial.print(") ... ");
    if (stkPush(i)) {
      Serial.println("done.");
      stkShow();
    } else {
      Serial.println(" Stack overflow!");
    }
  }
  uint8_t data;
  for (int i = 0; i < 6; i++) {
    Serial.print("pop() ... ");
    if (stkPop(data)) {
      Serial.println(data);
      stkShow();
    } else {
      Serial.println(" Stack underflow!");
    }
  }
}

void loop() {
}

ภาพที่ 6 ตัวอย่างผลลัพธ์ของโปรแกรมสแต็กแบบใช้แถวลำดับ

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

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

ข้อมูล

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

const uint8_t stkMaxElm = 5;
struct stkNode {
  uint8_t data;
  stkNode * next;
};

stkNode * stkRoot;
stkNode * stkCurrentNode;
stkNode * stkNewNode;
uint8_t stkElmCounter = 0;

bool stkInit() {
  stkElmCounter = 0;
  stkRoot = NULL;
  stkCurrentNode = NULL;
  stkNewNode = NULL;
  return true;
}

การ push

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

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


bool stkPush( uint8_t x ) {
  if (stkElmCounter == stkMaxElm) {
    return false;
  }
  stkNewNode = (stkNode*)malloc( sizeof( stkNode ) );
  if (stkNewNode == NULL) {
    return false;
  }
  stkNewNode->next = NULL;
  stkNewNode->data = x;
  if (stkElmCounter == 0) {
    stkRoot = stkNewNode;
  } else {
    stkCurrentNode->next = stkNewNode;
  }
  stkCurrentNode = stkNewNode;
  stkElmCounter += 1;
  return true;
}

การ pop

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

ถ้าจำนวนสมาชิกเป็น 0 ให้ออกจากฟังก์ชัน
ถ้ามีเพียงโหนดเดียวให้ลบโหนดแรกและกำหนดให้ stkRoot และ stkCurrentNode มีค่าเป็น NULL
กรณีอื่นให้ลบโหนดสุดท้ายออก
ลดค่าจำนวนสมาชิกของโหนดลง 1

bool stkPop( uint8_t& x ) {
  if (stkElmCounter == 0) {
    return false;
  }

  if (stkRoot == stkCurrentNode) {
    x = stkCurrentNode->data;
    free(stkCurrentNode);
    stkRoot = NULL;
    stkCurrentNode = NULL;
  } else {
    x = stkCurrentNode->data;

    stkNode * currentNode = stkRoot;
    while (currentNode->next != stkCurrentNode) {
      currentNode = currentNode->next;
    }
    currentNode->next = NULL;
    free(stkCurrentNode);
    stkCurrentNode = currentNode;
  }
  stkElmCounter -= 1;
  return true;
}

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

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

const uint8_t stkMaxElm = 5;
struct stkNode {
  uint8_t data;
  stkNode * next;
};

stkNode * stkRoot;
stkNode * stkCurrentNode;
stkNode * stkNewNode;
uint8_t stkElmCounter = 0;

bool stkInit() {
  stkElmCounter = 0;
  stkRoot = NULL;
  stkCurrentNode = NULL;
  stkNewNode = NULL;
  return true;
}

bool stkPush( uint8_t x ) {
  if (stkElmCounter == stkMaxElm) {
    return false;
  }
  stkNewNode = (stkNode*)malloc( sizeof( stkNode ) );
  if (stkNewNode == NULL) {
    return false;
  }
  stkNewNode->next = NULL;
  stkNewNode->data = x;
  if (stkElmCounter == 0) {
    stkRoot = stkNewNode;
  } else {
    stkCurrentNode->next = stkNewNode;
  }
  stkCurrentNode = stkNewNode;
  stkElmCounter += 1;
  return true;
}

bool stkPop( uint8_t& x ) {
  if (stkElmCounter == 0) {
    return false;
  }

  if (stkRoot == stkCurrentNode) {
    x = stkCurrentNode->data;
    free(stkCurrentNode);
    stkRoot = NULL;
    stkCurrentNode = NULL;
  } else {
    x = stkCurrentNode->data;

    stkNode * currentNode = stkRoot;
    while (currentNode->next != stkCurrentNode) {
      currentNode = currentNode->next;
    }
    currentNode->next = NULL;
    free(stkCurrentNode);
    stkCurrentNode = currentNode;
  }
  stkElmCounter -= 1;
  return true;
}

void stkShow() {
  Serial.print("Stack data=[ ");
  stkNode * currentNode = stkRoot;
  while (currentNode) {
    Serial.print(currentNode->data);
    Serial.print(" ");
    currentNode = currentNode->next;
  }
  Serial.println("]");
}

void setup() {
  Serial.begin( 9600 );
  stkInit();
  stkShow();
  for (int i = 0; i < 6; i++) {
    Serial.print("push(");
    Serial.print(i);
    Serial.print(") ... ");
    if (stkPush(i)) {
      Serial.println("done.");
      stkShow();
    } else {
      Serial.println(" Stack overflow! or not enough memory!");
    }
  }
  uint8_t data;
  for (int i = 0; i < 6; i++) {
    Serial.print("pop() ... ");
    if (stkPop(data)) {
      Serial.println(data);
      stkShow();
    } else {
      Serial.println(" Stack underflow!");
    }
  }
}

void loop() {
}

สรุป

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

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