บทที่ 5 “Stacks” (สแต็ก)

บทที่ 5 “Stacks” (สแต็ก)       สแต็ก (Stacks) เป็นลิสต์แบบเชิงเส้น (Linear Lists)  มีโครงสร้างข้อมูลที่จัดเก็บข้อมูลแบบเรียงลำดับต่อเนื่อง การเพิ่มข้อมูลลงในสแต็ก หรือการนำข้อมูลออกจากสแต็ก จะกระทำที่จุดปลายด้านใดด้านหนึ่งซึ่งมีลักษณะเข้าออกได้ทางเดียว โดยเรียกบริเวณนั้นว่า Top ของสแต็ก การดำเนินงานพื้นฐานของสแต็ก 1.       ฟังก์ชัน Push การเพิ่มข้อมูลลงในสแต็ก จะใช้ฟังก์ชัน Push ซึ่งฟังก์ชันดังกล่าวจะทำหน้าที่เพิ่มรายการที่ตำแหน่งบนสุดของสแต็ก ปัญหาของ Push คือ ต้องมั่นใจว่าภายในสแต็กนั้นมีพื้นที่ว่างพอที่จะบรรจุข้อมูลใหม่ลงไปได้ ถ้าหากสแต็กเต็มหรือมีพื้นที่ว่างไม่เพียงพอ จะทำให้เกิดสถานะ Overflow State ส่งผลให้ไม่สามารถใส่ข้อมูลใหม่เข้าไปในสแต็กได้อีก 2.       ฟังก์ชัน Pop เป็นฟังก์ชันคืนค่าข้อมูลที่อยู่บนสุดของสแต็กส่งคืนให้กับผู้ใช้ พร้อมทั้งลบข้อมูลรายการนั้นออกไปด้วย ส่งผลให้ข้อมูลรายการถัดไปกลับมาอยู่ในสถานะบนสุดอีกครั้ง และเมื่อรายการสุดท้ายในสแต็กได้ถูกนำออกไปทั้งหมด สแต็กดังกล่าวก็จะถูกกำหนดให้อยู่ในสถานะว่าง (Empty State) แต่หากในขณะนั้นมีการเรียกฟังก์ชัน Pop บนสแต็กที่ว่างเปล่า จะทำให้เกิดสถานะ Underflow State จึงจำเป็นต้องตรวจสอบก่อนว่าสแต็กนั้นว่างหรือไม่ 3.       ฟังก์ชัน Stack Top ฟังก์ชันนี้จะมีความคล้ายคลึงกับฟังก์ชัน Pop ที่คืนค่าข้อมูลโดยการคัดลอกข้อมูลบนสุดของสแต็กส่งคืนให้กับผู้ใช้ แตกต่างกันตรงที่ฟังก์ชัน Stack Top นั้น จะคืนค่าข้อมูลไปยังผู้ใช้งานเท่านั้น โดยไม่มีการลบข้อมูลออกจากสแต็กแต่อย่างใด การสร้างสแต็ก       เนื่องจากสแต็กเป็นโครงสร้างข้อมูลที่เป็นภาษาคอมพิวเตอร์ไม่ได้มีมาให้เหมือนกับอาร์เรย์ ดั้งนั้นจึงจำเป็นต้องสร้างขึ้นเอง โดยสามารถสร้างด้วยการแทนที่ข้อมูลสแต็กได้ 2 วิธี คือ       การสร้างสแต็กด้วยอาร์เรย์ เป็นการจัดสรรพื้นที่หน่วยความจำแบบ Static ซึ่งต้องมีการกำหนดของสแต็กเพื่อใช้งานล่วงหน้าว่าต้องการขนาดเท่าไร จากนั้นก็ทำการจัดสรรเนื้อที่ภายในหน่วยความจำแบบคงที่ตายตัว และด้วยโครงสร้างอาร์เรย์ที่นำมาแทนที่ข้อมูลของสแต็ก จึงต้องจัดเก็บข้อมูลชนิดเดียวกัน       ข้อเสีย 1.       ต้องมีการจัดสรรพื้นที่หน่วยความจำที่แน่นอนไว้ล่วงหน้า 2.       กรณีมีการเพิ่มข้อมูลลงในสแต็กมากเกินกว่าที่กำหนดไว้ก็จะส่งผลให้สแต็กเต็มได้ จะต้องแก้ไขโดยการจัดสรรพื้นที่ภายในหน่วยความจำจำนวนมากๆ เข้าไว้ ซึ่งก็จะทวีความสิ้นเปลืองยิ่งขึ้น 3.       กรณีที่มีข้อมูลน้อยหรือไม่มีข้อมูลในสแต็กเลย นั่นหมายความว่าจะต้องเสียพื้นที่หน่วยความจำไปโดยปริยาย       การสร้างสแต็กด้วยลิงก์ลิสต์ เป็นวิธีหนึ่งที่มีประสิทธิภาพสูง ซึ่งลิงก์ลิสต์จะจัดหน่วยความจำแบบไดนามิก ดังนั้นจึงไม่ต้องกำหนดขนาดคงที่อย่างอาร์เรย์ คือหน่วยความจำจะถูกจัดสรรเมื่อมีการใช้งานจริงเท่านั้น อีกทั้งยังสามารถจัดเก็บข้อมูลต่างชนิดกันได้ ส่วนประกอบสำคัญของลิงก์ลิสต์         ส่วนหัว ตามปกติ ส่วนหัวจะประกอบด้วย 2 แอตทิบิวต์ด้วยกัน คือ พอยต์เตอร์ ที่ชี้ไปยังโหนดบนสุด และตัวนับ ที่แสดงจำนวนสมาชิกในสแต็ก ทั้งสองส่วนนี้จะบรรจุอยู่ในโครงสร้าง       ส่วนข้อมูล จะดูเหมือนกับโหนดลิงก์ลิสต์ที่มีการต่อเติมข้อมูลเพิ่มเข้าไป กล่าวคือส่วนนี้จะประกอบไปด้วยข้อมูล และพอยต์เตอร์ที่ใช้สำหรับเชื่อมโยงไปยังส่วนข้อมูลตัวถัดไป อัลกอริทึมการสร้างสแต็กด้วยลิงก์ลิสต์       ประกอบด้วย 1.       Create Stack 2.       Push Stack 3.       Pop Stack 4.       Stack Top 5.       Empty Stack 6.       Full Stack 7.       Stack Count 8.       Destroy Stack       โครงสร้างข้อมูลแบบสแต็กนั้นจะเป็นลิสต์ที่มีข้อจำกัดหลายประการ ดังนี้ 1.    การเพิ่มสมาชิกหรือข้อมูลจะสามารถจัดเก็บเรียงตามลำดับจากปลายด้านใดด้านหนึ่งเท่านั้น 2.    รายการข้อมูลที่เพิ่มเข้าไปจะอยู่บนสุด 3.     เราสามารถเข้าถึงรายการข้อมูลในสแต็กได้ ณ ส่วนบนสุดเท่านั้น 4.     การดำเนินงานใดๆ บนสแต็กจะเป็นไปตามประสิทธิภาพของฟังก์ชัน การประยุกต์ใช้งานสแต็ก       การเรียงลำดับข้อมูลแบบย้อนกลับ คือการจัดเรียงลำดับข้อมูลใหม่       การแตกข้อมูลออกเป็นส่วนๆ เป็นการแตกข้อมูลให้เป็นอิสระต่อกัน เพื่อส่งไปประมวลผล       การหน่วงเวลา เป็นการหน่วงเวลาข้อมูลไว้ชั่วขณะหนึ่ง เพื่อรอการประมวลผลในช่วงจังหวะเวลาที่เหมาะสม นำไปใช้กับการแปลงนิพจน์ Infix มาเป็นนิพจน์ Postfix       การย้อนรอย เป็นการย้อนรอยไปยังสถานะก่อนหน้า รวมถึงการค้นหาเส้นทางการเดินทางเพื่อไปยังเป้าหมายปลายทาง การแปลงนิพจน์ Infix มาเป็น Postfix ด้วยมือ 1.       ให้ใส่วงเล็บให้กับทุกๆ นิพจน์ ด้วยการคำนึงถึงลำดับการคำนวณ 2.       ทำการเปลี่ยนสัญลักษณ์ Infix มาเป็นแบบ Postfix โดยเริ่มจากลงเล็บในสุดก่อน จากนั้นย้ายโอเปอเรเตอร์ตรงตำแหน่งวงเล็บนั้นไปยังตำแหน่งวงเล็บปิดของคู่นั้นๆ 3.       ถอดเครื่องหมายวงเล็บทิ้งออกให้หมด รีเคอร์ชัน       รีเคอร์ชัน เป็นหลักการที่จะนำมาใช้กับการเขียนโปรแกรมแบบ Recursive ซึ่งโดยปกติทั่วไป อัลกอริทึมการทำงานซ้ำๆ สามารถเขียนได้ 2 แบบ คือ 1.       การวนรอบ เป็นเทคนิคที่ใช้หลักการวนรอบหรือลูป เพื่อทำกระบวนการนั้นซ้ำๆ จนกระทั่งตรงตามเงื่อนไข การควบคุมลูปก็จะหลุดออกจากลูป 2.       การเรียงตัวเอง เป็นเทคนิคการวนซ้ำเพื่อกระบวนการหรือชุดคำสั่งนั้นซ้ำๆ ด้วยวิธีการเรียกตัวเองเพื่อทำซ้ำ มีความซับซ้อนมากกว่าแบบแรก และได้มาซึ่งโปรแกรมขนาดเล็กกระชับมากกว่า **********จบแล้วจ่ะ**********