บทที่ 4 สแต็ก (Stacks)
สแตก(stack)
สแตก เป็นโครงสร้างข้อมูลที่เก็บข้อมูลต่อเนื่องกัน ซึ่งมีลักษณะคล้ายกันกับการวางจานข้าวหรือหนังสือซ้อนกันเป็นชั้นๆ โดยมีตัวดำเนินการคอยจัดการกับข้อมูล ได้แก่ การนำข้อมูลเข้า(Push) และการนำข้อมูลออก (Pop) โดยจะกระทำกับข้อมูลที่อยู่ตำแหน่งบนสุดในสแตกเท่านั้น จึงทำให้หลักการของโครงสร้างข้อมูลดังกล่าวมีลักษณะเป็น "เข้าก่อนออกทีหลัง Last In First Out /LIFO) ซึ่งหมายถึง ข้อมูลที่นำเข้าเป็นลำดับสุดท้ายจะถูกนำออกจากสแตกเป็๋นลำดับแรก
1. ฟังก์ชัน Push ทำหน้าที่เพิ่มข้อมูลเข้าไปในชั้นบนสุดของแสต็กปัญหาของการ
Push ก็คือต้องมีความมั่นใจว่าภายในสแต้กนั้นมีพื้นที่ว่างพอที่จะบรรจุข้อมูลใหม่ลงไปได้ถ้าหาก
สแต็กหรือมีพื้นที่ว่างไม่เพียงพอ จะทำให้เกิดสถานะโอเวอร์โฟลว์ (Overflow State) ส่งผลให้
ไม่สามารถใส่ข้อมูลใหม่เข้าไปในสแต็กได้อีก ซึ่งโดยทั่วไปเราจะใช้ฟังก์ชัน fullStack ในการ
ตรวจสอบว่าสแต็กเต็มหรือไม่ โดยพิจารณาจากรูปที่ 1 ที่แสดงถึงฟังก์ชัน Push ด้วยการใส่
ข้อมูลลงในสแต็ก
รูปที่ 1 การPush ข้อมูลลงในสแต็ก
2. ฟังก์ชัน Pop เป็นฟังก์ชันคืนค่าข้อมูลที่อยู่บนสุดของสแต็กส่งคืนให้กับผู้ใช้ พร้อม
ทั้งลบข้อมูลรายการนั้นออกไปด้วย ส่งผลให้ข้อมูลรายการถัดไปกลีบมาอยู่ในสถานะบนสุดอีกครั้ง
และเมื่อรายการสุดท้ายในสแต็กได้ถูกนำออกไปทั้งหมด สแต็กดังกล่าวก็จะถูกกำหนดให้อยู่ใน
สถานะว่าง (EmptyState) แต่หากในขณะนั้นมีการเรียกใช้ฟังก์ชัน Pop บนสแต็กว่างเปล่าจะ
ทำให้เกิดสถานะอันเดอร์โฟลว์(Underflow State) ดังนั้นเมื่อต้องการ Pop ข้อมูลออกจาก
สแต็ก จึงจำเป็นต้องตรวจสอบก่อนว่าสแต็กนั้นว่างหรือไม่ ซึ่งโดยทั่วไปเราจะใช้ฟังก์ชัน empty
Stack ในการตรวจสอบว่าสแต็กว่างหรือไม่ โดยพิจารณาจากรูปที่ 2 ที่แสดงถึงฟังก์ชัน Pop
ด้วยการนำข้อมูลออกจากสแต็กรูปที่ 2 การ Pop ข้อมูลออกจากสแต็ก3. ฟังก์ชัน Stack Top ฟังก์ชันนี้จะมีความคล้ายคลึงกับฟังก์ชัน Pop ที่คืนค่าข้อมูล
ด้วยการคัดลอกข้อมูลบนสุดของสแต็กส่งคืนให้กับผู้ใช้ แต่จะแตกต่างตรงที่ฟังก์ชัน Stack Top
นั้น จะคืนค่าข้อมูลไปยังผู้ใช้งานเท่านั้น โดยไม่มีการลบข้อมูลออกจากสแต็กแต่อย่างใด กล่าวคือ
หน้าที่ของฟังก์ชัน StackTop นั้นก็คือการอ่านข้อมูลบนสแต็กที่อยู่ลำดับบนสุดของสแต็กนั่นเอง
โดยพิจารณาจากรูปที่ 3 ที่แสดงถึงฟังก์ชันStack Topด้วยการอ่านข้อมูลจากสแต็กที่อยู่ใน
ลำดับสุดส่งคืนกลับไปยังผู้ใช้เพื่อนำไปใช้งานต่อไป
รูปที่ 3 การอ่านข้อมูลด้วย Stack Top
การสร้างสแต็กด้วยอาร์เรย์
การสร้างสแต็กด้วยโครงสร้างข้อมูลแบบอาร์เรย์นั้น เป็นการจัดสรรพื้นที่หน่วยความ
การสร้างสแต็กด้วยโครงสร้างข้อมูลแบบอาร์เรย์นั้น เป็นการจัดสรรพื้นที่หน่วยความ
จำแบบสแตติก (Static) ซึ่งต้องมีการกำหนดขนาดของสแต็กเพื่อใช้งานล่วงหน้าว่าต้องการขนาด
เท่าไรจากนั้นก็ทำการจัดสรรเนื้อที่ภายในหน่วยความจำแบบคงที่ตายตัวและด้วยโครงสร้างแบบ
อาร์เรย์ที่นำมาแทนที่ข้อมูลของสแต็ก จึงต้องจัดเก็บข้อมูลที่เป็นชนิดเดียวกัน จากรูปที่ 4
แสดงถึงการสร้างสแต็กด้วยอาร์เรย์
รูปที่ 4 การสร้างสแต็กด้วยอาร์เรย์
อย่างไรก็ตาม การเลือกโครงสร้างข้อมูลแบบอาร์เรย์มาสร้างสแต็กนั้น จะมีข้อเสียอยู่หลายประการ
ด้วยกัน คือ
- การสร้างสแต็กด้วยอาร์เรย์ต้องมีการจัดสรรพื้นที่หน่วยความจำที่แน่นอนไว้ล่วงหน้า
- กรณีการเพิ่มข้อมูลลงในสแต็กมากเกินกว่าที่กำหนดไว้จะส่งผลให้สแต็กเต็มได้
- แต่ก็สามารถแก้ไขปัญหาได้ด้วยการจัดสรรเนื้อที่ภายในหน่วยความจำจำนวนมากๆ เข้าไว้
ซึ่งก็จะทวีความสิ้นเปลืองยิ่งขึ้น - สำหรับกรณีมีข้อมูลจำนวนน้อยหรือไม่มีข้อมูลในสแต็กเลย นั่นหมายความว่าต้องเสียพื้นที่
หน่วยความจำไปโดยปริยาย
การสร้างสแต็กด้วยลิงก์ลิสต์
การสร้างสแต็กด้วยโครงสร้างข้อมูลแบบลิงก์ลิสต์จัดเป็นอีกวิธีหนึ่งที่มีประสิทธิภาพสูงซึ่ง
ลิงก์ลิสต์จะจัดสรรหน่วยความจำแบบไดนามิก (Dynamic) ดังนั้นจึงไม่ต้องกำหนดขนาดคงที่อย่าง
เช่นอาร์เรย์ กล่าวคือหน่วยความจำจะถูกจัดสรรเมื่อมีการใช้งานจริงเท่านั้น อีกทั้งยังสามารถจัดเก็บ
ข้อมูลต่างชนิดกันได้ นอกจากนี้แล้ว การสร้างสแต็กด้วยลิงก์ลิสต์ สแต็กจะไม่มีวันเต็มต่อเมื่อยังมี
เนื้อที่เพียงพอต่อการจัดสรรได้อยู่
ส่วนประกอบสำคัญของลิงก์ลิสต์ก็คือ โครงสร้างสองส่วนที่มีความแตกต่างกันคือ ส่วนหัว
(Head) และส่วนข้อมูล (Data Node) โดยโครงสร้างส่วนหัวจะประกอบไปด้วย Metadataที่เป็น
ข้อมูลเพื่อใช้อธิบายข้อมูลอีกทีหนึ่ง และพอยน์เตอร์ที่อยู่ส่วนบนสุดของสแต็ก สำหรับส่วนข้อมูลจะ
ประกอบด้วยข้อมูลพอยน์เตอร์ที่ใช้เชื่อมโยงไปยังโหนดถัดไปในสแต็ก พิจารณาจากรูปที่ 6 ที่
แสดงถึงการสร้างสแต็กด้วยด้วยลิงก์ลิสต์ โดยรูปที่ 5 นั้นคือแนวความคิดของสแต็ก และเป็นรูป
แบบของการสร้างสแต็กด้วยลิงก์ลิสต์ในเชิงกายภาพ
รูปที่ 5 การสร้างสแต็กด้วยลิงก์ลิสต์
ไม่มีความคิดเห็น:
แสดงความคิดเห็น