หน้าแรก สารบัญ เกี่ยวกับบล็อกนี้ เกี่ยวกับผู้เขียน

คิวน่ารักเพราะสร้างจากลิงค์ลิสต์ [ตอน 4]

สร้างคิวที่เพิ่ม-ลดขนาดได้อย่างมีพลวัต

และเป็นเจนเนอริกสไตล์ OOP

บทความโดย : ลาภลอย วานิชอังกูร (laploy.com)

โปรแกรมทดสอบ

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

รูป 010 : คลาส Program

Main คือเมธอดที่จะทำงานโดยอัตโนมัติเมื่อโปรแกรมเริ่มต้น ภายใน Main ไม่มีโค้ดใดๆ นอกจากโค้ดรียกใช้งานเมธอดสองตัว คือ TestLinkedList ซึ่งทำหน้าที่ทดสอบลิงค์ลิสต์ และ TestQueueLinkedList ทำหน้าที่ทดสอบคิวที่สร้างจากลิงค์ลิสต์

รูป 011 : เมธอด TestLinkedList และ TestQueueLinkedList

บรรทัดที่ 17 ทำหน้าที่สร้างออพเจ็กต์ชื่อ myList จากคลาส LinkedList ที่เรานิยามไว้ บรรทัดที่ 18 ถึง 19 นำข้อมูลมาเข้าคิวสามจำนวน คือ 5,6 และ 7 บรรทัด 22 เรียกเมธอด DisplayNode ซึ่งจะแสดงข้อมูลในคิวทั้งหมด บรรทัด 22 เรียกเมธอด DisplayNodeReverse แสดงข้อมูลในคิวทั้งหมดแบบเรียงย้อนจากหลังไปหน้า บรรทัด 24 ลบโหนดทุกโหนดในคิว บรรทัด 25 เรียกเมธอด DisplayNode ซึ่งจะแสดงข้อมูลในคิวทั้งหมดอีกครั้ง

ต่อไปเราจะตรวจสอบว่า QueueLinkedList ทำงานถูกต้องหรือไม่ บรรทัดที่ 30 ทำหน้าที่สร้างออพเจ็กต์ชื่อ myQ จากคลาส QueueLinkedList ที่เรานิยามไว้ บรรทัดที่ 31 ถึง 33 นำข้อมูลมาเข้าคิวสามตัว บรรทัดที่ 34 กำหนดค่าเริ่มต้นให้ตัวแปร x บรรทัดที่ 35 ถึง 39 คือการทำงานวนซ้ำด้วยคำสั่ง while ระหว่างวนซ้ำเราจะออกคิวด้วยคำสั่งในบรรทัดที่ 37 และแสดงผลบนจอภาพด้วยคำสั่งบรรทัดที่ 38 หากออกคิวจนข้อมูลหมดคิวแล้ว ค่า x จะกลายเป็น -1 การวนซ้ำจะหยุดลง ผลลัพธ์จากการทำงานของโปรแกรมทดสอบจะเป็นดังนี้

รูป 012 : ผลลัพธ์จากการทำงานของคลาส Program

สร้างคิวด้วยลิงค์ลิสต์แบบเจนเนอริก

คลาสลิงค์ลิสต์ที่เรานิยามไว้มีข้อเสียคือ ใช้งานกับข้อมูลได้เพียงชนิดเดียว (เลขจำนวนเต็ม) หากต้องการให้ใช้ได้กับข้อมูลทุกชนิดเราต้องเปลี่ยนชนิดข้อมูลให้เป็นเจนเนอริก แต่ไม่จำเป็นต้องนิยามขึ้นเอง ผู้สร้างดอนเน็ตไลบรารีได้เตรียมคลาสลิงค์ลิสต์แบบเจนเนอริกมาให้เรียบร้อยแล้ว อยู่ในเนมสเปส Collection และ Collection.Generic

เราจึงนิยามคลาส QueueLinkedList แบบเจนเนอริกได้โดยการเขียนโค้ดเพียงไม่กี่บรรทัด

รูป 015 : คลาส QueueLinkedList แบบเจนเนอริก

บรรทัด 13 คำว่า <GenericType> เป็นคำที่ผู้เขียนตั้งขึ้นเอง ทำหน้าที่ประกาศว่าคลาสนี้เป็นเจนเนอริก (จะเปลี่ยนไปใช้ชื่ออื่นแทนก็ได้ เช่น <T>) บรรทัด 15 สร้างออพเจ็กต์ลิงค์ลิสต์แบบเจนเนอริก ในเมธอด Enqueue จะเห็นว่ามีเพียงบรรทัดเดียว อาศัยการเรียกใช้เมธอด AddLast ซึ่งทำหน้าที่นำโหนดใหม่ไปใส่ท้ายลิสต์ ส่วนการออกคิว บรรทัด 22 ตรวจสอบว่าคิวว่างเปล่าหรือไม่โดยใช้เมธอด Count ที่ให้ผลลัพธ์เป็นจำนวนโหนดในลิงค์ลิสต์ หากว่างเปล่า จะทำคำสั่ง return default แล้วจบการทำงานไป หากมีโหนด โปรแกรมจะไปทำงานบรรทัดที่ 23 เพื่ออ่านค่าจากด้านหน้าสุดของคิว แล้วลบโหนดนั้นในบรรทัดที่ 24

โปรแกรมทดสอบ

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

รูป 017 : คลาส Program

ภายใน Main ไม่มีโค้ดใดๆ นอกจากโค้ดที่เรียกเมธอดสองตัวคือ TestWithInt ทำหน้าที่ทดสอบคิวโดยใช้เลขจำนวนเต็ม และ TestWithString ซึ่งจะทดสอบคิวด้วยตัวอักษร

รูป 023 : เมธอด TestWithInt และ TestWithString

ในเมธอด TestWithInt บรรทัดที่ 18 ถึง 20 นำข้อมูลมาเข้าคิวสามจำนวน คือ 12,13 และ 14 บรรทัด 24 เรียกเมธอด Dequeue ซึ่งจะนำข้อมูลหน้าคิวออกมา แล้วแสดงผลดัวยคำสั่งในบรรทัดที่ 25 ส่วนเมธอด TestWithString บรรทัดที่ 32 ถึง 34 นำข้อมูลมาเข้าคิวสามจำนวน คือ “hello”, “this is” และ “Queue!” บรรทัด 38 เรียกเมธอด Dequeue ซึ่งจะนำข้อมูลหน้าคิวออกมา แล้วแสดงผลดัวยคำสั่งในบรรทัดที่ 39

ผลลัพธ์ที่ได้จะเป็นดังนี้

รูป 022 : ผลลัพธ์จากการทำงานของ Program

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

สรุปเรื่องการสร้างคิวจากลิงค์ลิสต์

ในการพัฒนาซอฟต์แวร์ไม่ว่าจะทำเกม ระบบปฏิบัติการ หรือโปรแกรมใช้งานทางธุรกิจ โครงสร้างข้อมูลแบบคิว เป็นโครงสร้างข้อมูลพื้นฐานที่เราต้องใช้อยู่เสมอ บทความนี้นำเสนออัลกอริทึมของคิว พร้อมโค้ดและคำอธิบายโดยละเอียด ท่านสามารถนำคลาสที่นิยามในบทความนี้ไปบูรณาการกับระบบงานของท่านได้ทันที ท่านสามารถดาวน์โหลดซอร์สโค้ดของบทความนี้ได้จากเว็บไซต์ laploy.com (เลือกหัวข้อดาวน์โหลด ไฟล์ชื่อ QueueLinkedList.zip )หากท่านมีข้อสงสัยใดๆ โปรดใส่คำถามไว้ที่กระดานถาม-ตอบซึ่งอยู่ในเว็บไซต์เดียวกัน

หน้าแรก สารบัญ เกี่ยวกับบล็อกนี้ เกี่ยวกับผู้เขียน

คิวน่ารักเพราะสร้างจากลิงค์ลิสต์ [ตอน 3]

สร้างคิวที่เพิ่ม-ลดขนาดได้อย่างมีพลวัต

และเป็นเจนเนอริกสไตล์ OOP

บทความโดย : ลาภลอย วานิชอังกูร (laploy.com)

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

บทความนี้มีจุดมุ่งหมายเพื่อเสนอวิธีเขียนโปรแกรมแบบ OOP แสดงการทำงานของโครงสร้างข้อมูล แสดงตัวอย่างอัลกอริทึม แสดงวิธีเขียนโค้ดด้วยภาษา C# แสดงการเขียนโปรแกรมแบบเมนเนจโค้ด และแสดงวิธีสร้างคิวด้วยลิงค์ลิสต์แบบเจนเนอริค

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

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

การออกคิว

การออกคิวหรือ dequeue คือการลบโหนดหน้าสุดออกจากคิว แย่หน่อยที่ในคลาส LinkedList ไม่มีโค้ดอะไรใกล้เคียงการออกคิวเลย เราจึงต้องเขียนโค้ดขึ้นใหม่ทั้งหมด

รูป 009 : เมธอด Dequeue และ IsEmpty

เมธอด Dequeue เริ่มทำงานโดยตรวจสอบว่าคิวว่างเปล่าหรือไม่ (บรรทัดที่ 19) เราเขียนเมธอดตรวจสอบชื่อ IsEmpty (บรรทัดที่ 35-41) เตรียมไว้แล้ว เมธอดนี้มีหน้าที่ตรวจสอบว่า front เป็น null หรือไม่ หากใช่ แสดงว่าในคิวไม่มีโหนดเหลืออยู่เลย

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

รูป 020 : สภาพของคิวเมื่อมีข้อมูลสามโหนด โปรดสังเกตว่าตัวชี้ front ตอนนี้ชี้โหนด 1 และ back ชี้โหนด 3

เนื่องจากขณะนี้ในคิวมีโหนดอยู่ ตัวชี้ front จึงไม่เป็น null แต่จะมีค่าเท่ากับโหนด 1 ผลลัพธ์คือเมธอด IsEmpty จะคืนค่ากลับมาเป็น false โปรแกรมจะไปทำงานบรรทัดที่ 21

แต่ถ้าสมมุติว่าตอนนี้ในลิสต์ไม่มีโหนดเหลืออยู่เลย คือเราดึงข้อมูลออกคิวไปหมดแล้ว เมื่อโปรแกรมทำงานบรรทัดที่ 19 เมธอด IsEmpty พบว่าไม่มีโหนดแล้ว ค่า front จะกลายเป็น null มันจะคืนค่ากลับมาเป็น true ทำให้โค้ดบรรทัดที่ 20 ทำงานเพื่อส่งค่า -1 ไปให้โค้ดที่เรียกใช้มัน (ค่า -1 เป็นเครื่องหมายบอกว่าไม่มีข้อมูลในคิว) และจบการทำงานของเมธอด Dequeue เพียงเท่านั้น

ในกรณีที่ยังมีข้อมูลบรรทัดที่ 21 จะสร้างตัวแปรชื่อ retVal เพื่อเก็บค่าส่งกลับ (return value) ค่าที่เราจะส่งกลับไปคือข้อมูลในโหนดหน้าสุดของคิว (เพราะการออกคิวต้องออกทางด้านหน้าเสมอ) ซึ่งก็คือข้อมูลโหนดที่เก็บอยู่ใน front.Data นั่นเอง ดังนั้นคำสั่งบรรทัดที่ 21 จึงนำค่านี้มาไว้ใช้ส่งกลับ

คำสั่งบรรทัดที่ 22 ผู้เขียนใส่ไว้ทดสอบการทำงานตอนไล่หาความผิดพลาด (ดีบัก) ไม่ได้ใช้ประโยชน์ในเมธอดนี้ จะลบทิ้งไปเสียก็ได้

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

คำสั่ง if บรรทัดที่ 23 ตรวจสอบว่าภายในคิว มีโหนดเหลือโหนดอยู่เพียงเดียวหรือไม่ ซึ่งทำได้โดยดูที่ตัวชี้ Next ของ front หาก Next มีค่าเป็น null แสดงว่าไม่มีโหนดถัดไปอีกแล้ว โปรแกรมจะไปทำงานบรรทัดที่ 25-26 เพื่อเซตให้ทั่ง back และ front ให้มีค่าเป็น null เพื่อเป็นเครื่องแสดงว่าขณะนี้ลิงค์ลิสต์ว่างเปล่า นั่นคือไม่มีข้อมูลเหลืออยู่ในคิวแล้ว

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

บรรทัด 31 เซต front.Previous เป็น null ซึ่งมีผลให้โหนด 2 กลายเป็นโหนดแรกของคิว เมื่อเมธอด Dequeue ทำงานจบคิวจะมีสภาพดังนี้

รูป 021 : สภาพของคิวเมื่อนำข้อมูลออกไปหนึ่งโหนด

โปรดสังเกตว่าในภาษา C# การออกคิวไม่จำเป็นต้องเขียนโค้ดเพื่อลบโหนดไปจริงๆ เพราะเมื่อเราเลื่อนตัวชี้ previous และ next แล้ว โหนดที่ไม่ได้รับการอ้างถึงจะถูกมองว่าเป็นขยะ และกาเบจคอลเลคเตอร์จะลบโหนดนั้นให้โดยอัตโนมัติ ไม่เหมือนภาษา C++ (ในโหมด unmanaged) ที่เราต้องคอยดูให้แน่ใจด้วยตนเองว่าได้ทำลายออพเจ็กต์ที่ไม่ต้องการแล้ว

หน้าแรก สารบัญ เกี่ยวกับบล็อกนี้ เกี่ยวกับผู้เขียน

คิวน่ารักเพราะสร้างจากลิงค์ลิสต์ [ตอน 2]

สร้างคิวที่เพิ่ม-ลดขนาดได้อย่างมีพลวัต

และเป็นเจนเนอริกสไตล์ OOP

บทความโดย : ลาภลอย วานิชอังกูร (laploy.com)

คลาส LinkedList

รูป 004 : โครงสร้างของคลาส LinkedList

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

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

รูป 006 : เมธอด DisplayNode ใช้แสดงข้อมูลในทุกๆ โหนด โค้ดเหมือนเดิม แต่เพิ่มเมธอด

DisplayNodeReverse เพื่อใช้แสดงข้อมูลทุกโหนดโดยไล่จากหลังมาหน้า

รูป 007 : เมธอด DestroyList ใช้เพื่อทำให้ลิสต์ว่างเปล่าโดยลบโหนดทั้งหมด ก็เป็นเมธอดที่ถูกเพิ่มขึ้นใหม่

คลาส QueueLinkedList

หัวใจของบทความตอนนี้คือคลาส QueueLinkedList เมื่อดูจากโครงสร้างจะเห็นว่ามีสมาชิกเพียงสามตัว คือเมธอ Enqueue ใช้ทำหน้าที่นำข้อมูลใหม่มาบรรจุลงในคิว Dequeue ทำหน้าที่ดึงข้อมูลออกจากคิว และ IsEmpty ใช้เพื่อตรวจสอบว่าภายในคิวมีข้อมูลหรือไม่

รูป 008 : โครงสร้างของคลาส QueueLinkedList

การเข้าคิว

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

รูป 014 : เมธอด Enqueue

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

รูป 005 : เมธอด AppendNode

ต่อไปเราจะมาดูการทำงานของโปรแกรมเมื่อเข้าคิว ดูในโค้ดเมธอด AppendNode สมมุติว่าโปรแกรมเพิ่งเริ่มทำงาน และคิวยังว่างเปล่า บรรทัดที่ 22 เราสร้างออพเจ็กต์ myNode เป็นโหนดใหม่ที่จะนำไปใส่ในคิว บรรทัด 23 ตรวจสอบว่าคิวว่างเปล่าหรือไม่ หากว่างเปล่า โปรแกรมบรรทัดที่ 25-26 จะทำงาน เซตค่า back และ front เป็น myNode ทั้งคู่เพราะในลิสต์มีโหนดใหม่นี้เพียงโหนดเดียว แล้วเมธอดจะจบการทำงาน ผลลัพธ์จะเป็นดังนี้

รูป 016 : ผลลัพธ์เมื่อนำข้อมูลอันแรกเข้าคิว

ต่อไปเราจะนำข้อมูลเข้าคิวอีกตัว คราวนี้ใส่เลข 6 ตอนนี้มีโหนดอยู่ในคิวแล้ว โปรแกรมจะทำงานบรรทัดที่ 30 เซตค่า next ของ back ให้กลายเป็น myNode ผลลัพธ์จะเป็นดังนี้

รูป 017 : ผลลัพธ์เมื่อทำคำสั่ง back.Next = myNode;

บรรทัดที่ 31 กำหนดค่า previous ของโหนดใหม่ให้ชี้ไปยังโหนดก่อนหน้า ผลลัพธ์จะเป็นดังนี้

รูป 018 : ผลลัพธ์เมื่อทำคำสั่ง myNode.Previous = back;

บรรทัด 32 ปรับเลื่อนตัวชี้ back ให้ชี้ไปยังข้อมูลตัวล่าสุดที่ถูกนำมาเข้าคิว

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

หน้าแรก สารบัญ เกี่ยวกับบล็อกนี้ เกี่ยวกับผู้เขียน

คิวน่ารักเพราะสร้างจากลิงค์ลิสต์ [ตอน 1]

สร้างคิวที่เพิ่ม-ลดขนาดได้อย่างมีพลวัต

และเป็นเจนเนอริกสไตล์ OOP

บทความโดย : ลาภลอย วานิชอังกูร (laploy.com)

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

บทความนี้มีจุดมุ่งหมายเพื่อเสนอวิธีเขียนโปรแกรมแบบ OOP แสดงการทำงานของโครงสร้างข้อมูล แสดงตัวอย่างอัลกอริทึม แสดงวิธีเขียนโค้ดด้วยภาษา C# แสดงการเขียนโปรแกรมแบบเมนเนจโค้ด และแสดงวิธีสร้างคิวด้วยลิงค์ลิสต์แบบเจนเนอริค

ทวนความจำเรื่องคิว

เพื่อทบทวนความจำของท่าน และเพื่อปูพื้นแก่ผู้อ่านที่ไม่ได้อ่านฉบับสิงหาคม ผู้เขียนจะขอทบทวนเรื่องคิวสักเล็กน้อย คิวคือโครงสร้างข้อมูลแบบเข้าก่อนได้ออกก่อน (First In First Out หรือ FIFO) เหมือนการเข้าคิวซื้อบัตรชมภาพยนตร์ ที่ผู้เข้าไปในคิวก่อนจะได้ออกจากคิวก่อนเสมอ ปรกติเราจะสร้างคิวจากอาร์เรย์ ซึ่งคิวจะไม่เป็นแถวตรงๆ เหมือนคิวซื้อบัตรชมภาพยนตร์ แต่เป็นจะมีลักษณะเป็นวงแหวน

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

สร้างคิวจากลิงค์ลิสต์

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

รูป 013 : แสดงตัวอย่างลิงค์ลิสต์ที่มีสี่โหนด โปรดสังเกตว่า Previous จะชี้ไปยังโหนดก่อนหน้า และ Next ชี้ไปยังโหนดถัดไป ที่โหนดแรกค่าของ Previous จะเป็น null และโหนดสุดท้าย Next ก็จะเป็น null เช่นกัน

โซลูชัน

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

รูป 001 : โซลูชัน QueueLinkedList เมื่อดูใน project explorer ของวิสชวลสตูดิโอ

รูป 002 : แผนภูมิคลาสในโปรเจค QueueLinkedList

ในแผนภูมิคลาสจะเห็นคลาสและสมาชิกของคลาสทั้งสี่ คลาส Node จะเหมือนที่อธิบายไปแล้วในบทความฉบับเดือนสิงหาคม คลาส LinkedList ก็คล้ายของเดิม แต่นำมาดัดแปลงใหม่ โดยแก้ไขเอ็กเซสโมดิฟายเออร์ของฟิลด์ เพื่อให้เรียกจากคลาสลูกได้ และเพิ่มเมธอด DisplayNodeReverse และ DestroyList

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

คลาส Node

รูป 003 : คลาส Node

ผู้เขียนอธิบายคลาส Node โดยละเอียดไปแล้วในฉบับเดือนสิงหาคม ดังนั้นในฉบับนี้จะพูดถึงเพียงคร่าวๆ ในนิยามคลาส Node บรรทัด 13-15 ประกาศฟิลด์ชื่อ data ตัวชี้ previous และ next เมื่อคลาส LinkedList ต้องการอ่านเขียนฟิลด์เหล่านี้ จะทำผ่าน พร็อพเพอร์ตี Data, Previous และ Next เมื่อสร้างออพเจ็กต์โหนด เมธอดคอนสทรักเตอร์ (บรรทัดที่ 33 ถึง 37) จะทำงานโดยนำข้อมูลไปใส่ใน data แล้วเซตค่าของ previous และ next ให้เป็น null เพื่อเป็นเครื่องแสดงว่าไม่มีโหนดก่อนหน้าและหลัง

หน้าแรก สารบัญ เกี่ยวกับบล็อกนี้ เกี่ยวกับผู้เขียน

สร้าง Mouse Air Pad [ตอน2]

จะทนรำคาญผ่ามือที่ชุ่มเหงื่อไปทำไม

มาประดิษฐ์แผ่นรองเมาส์ที่มีระบบระบายอากาศกันดีกว่า

บทความโดย : ลาภลอย วานิชอังกูร (laploy.com)

ถอดแผ่นอะลูมิเนียม

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

รูป 008 : แผ่นรองโน้ตบุ๊กที่ถอดแผ่นอะลูมิเนียมออกแล้ว

ตัดแผ่นลวดตาข่าย

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

รูป 009 : ตัดตาข่ายตามแบบ

แต่งขอบตาข่าย

เมื่อตัดแผ่นลวดตาข่ายตามแบบเสร็จแล้ว ให้ใช้กระดาษทรายขัดขอบให้เรียบ หากมีเส้นตาข่ายเกินออกมาให้ใช้คีมตัดเล็ก เล็มแต่งอีกครั้งจนขอบทุกด้านเรียบเนียน

รูป 010 : แต่งขอบตาข่าย

ใส่ผ้าให้ตาข่าย

ขั้นตอนนี้ควรหาผู้ช่วยสักหนึ่งคน ขั้นแรกให้นำกาวมาฉีดพ่นให้ทั่วพื้นผิวลวดตาข่าย (พ่นเพียงด้านเดียว) จากนั้นดึงผ้าให้เรียบ (แต่ไม่ดึงมากไปจนผ้ายืด) แล้วนำไปทาบลงบนแผ่นลวดตาข่ายด้านที่พ่นกาวแล้ว ใช้มือรีดให้เรียบไม่ให้มีรอยย่น สุดท้ายให้นำหนังสือหนักๆ วางทับไว้ข้ามคืนเพื่อให้ผ้าอยู่ตัว

ข้อควรระวังในขั้นตอนนี้คือ ปรกติกาวสเปรย์จะแห้งภายในสองนาที เมื่อพ่นกาวเสร็จแล้วจึงต้องติดผ้าให้เสร็จภายในสองนาที เพราะหากทิ้งไว้นานกว่านั้นผ้าจะยึดกับผิวงานได้ไม่ดี

รูป 011 : ก่อนใส่ผ้าบนแผ่นลวดตาข่าย

เก็บขอบผ้า

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

รูป 012 : แผ่นลวดตาข่ายเมื่อตัดผ้าแล้วแต่ยังไม่ได้เก็บขอบผ้า

ติดแผ่นกาวสองหน้า

ขั้นตอนต่อไปให้ติดแผ่นกาวสองหน้า การติดให้ติดในตำแหน่งที่แสดงในภาพ แผ่นกาวสองหน้าให้ใช้แบบหนาประมาณหนึ่งส่วนแปดของนิ้ว เพราะเราต้องการให้มีช่องว่างระหว่างแผ่นลวดตาข่ายและแผ่นรองโน้ตบุ๊ก ช่องว่านี้จะทำให้อากาศไหลผ่านได้ดี

รูป 013 : แผ่นลวดตาข่ายเมื่อติดแผ่นกาวสองหน้าแล้ว

ประกบแผ่นลวดตาข่าย

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

รูป 014 : ลวดตาข่ายเมื่อประกบเข้ากับแผ่นรองโน้ตบุ๊กแล้ว

ทิ้งไว้อีกหนึ่งคืน

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

รูป 015 : ขั้นตอนสุดท้ายคือทิ้งไว้อีกหนึ่งคืน

ได้เวลาหฤหรรษ์

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