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

Posted by: loyart on: กรกฎาคม 2, 2009

• In: Uncategorized
• ให้ความเห็น

หน้าแรก สารบัญ เกี่ยวกับบล็อกนี้ เกี่ยวกับผู้เขียน   คิวน่ารักเพราะสร้างจากลิงค์ลิสต์ [ตอน 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 เพื่อเป็นเครื่องแสดงว่าไม่มีโหนดก่อนหน้าและหลัง