บทที่ 4 สแตก (stack)

                                                               บทที่ 4 สแตก (stack)

โครงสร้างสแตก (Stack structure)

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

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

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

ลักษณะ ที่สำคัญของสแตก

·         การ นำข้อมูลเข้าสู่สแตก (Insertion บางครั้งเรียกว่า Pushing)

·         การ นำข้อมูลออกจากสแตก (Deletion บางครั้งเรียกว่า Poping)

·         สามารถ กระทำได้เพียงปลายด้านเดียวของโครงสร้างเท่านั้น

·         ข้อมูล ที่เข้าไปเก็บทีหลังสุดจะถูกนำออกมาใช้ก่อน จะเรียกลักษณะแบบนี้ว่า เข้าหลักออกก่อน (Last in First out)

·         การ เข้าถึงข้อมูลในโครงสร้างจะต้องอาศัยพอยเตอร์ ซึ่งทำหน้าที่ชี้ตำแหน่งของข้อมูลตัวสุดท้ายของสแตก

 ลักษณะสำคัญของสแตก

·         โครง สร้างข้อมูลเป็นแบบเชิงเส้น (Linear structure)

·         มี โครงสร้างที่ไม่ตายตัว (dynamic sturcture)

·         นำ ข้อมูลเข้าและดึงข้อมูลออกได้ (push and pop)

·         นำ ข้อมูลเข้าและดึงข้อมูลออกแบบลำดับ

·         มี การจัดการนำเข้าและดึงข้อมูลในตำแหน่ง บนสุด

พื้น ฐานการดำเนินการกับสแตก

1. Push หรือการนำเข้าข้อมูล เป็นการดำเนินการในลักษณะของการเพิ่มข้อมูลในสแตกและต้องระวังปัญหา stack over flow คือไม่มีพื้นที่ว่างสำหรับการเพิ่มข้อมูลเข้าไปในสแตก หรือ สแตกเต็ม

2. Pop หรือการดึงข้อมูลออก  คือ การนำเอาข้อมูลออกจากสแตก ซึ่งการดำเนินการก็จะต้องดำเนินการในตำแหน่ง top หากไม่มีข้อมูลภายในสแตกแล้วยังมีการ pop จะทำให้เกิดข้อผิดพลาด stack under fow

การ ดำเนินการที่สำคัญ 6 ประการ

1.               การดำเนินการสร้างสแตก (create)

2.               การดำเนินการ push

3.               การดำเนินการ pop

4.               การดำเนินการตรวจสอบสแตกว่าง (Empty stack)

5.               การดำเนินการตรวจสอบสแตกเต็ม (Full stack)

6.               การดำเนินการกำหนดล้างสแตก (Clear stack)

การ ประยุกต์ใช้งานสแตกในการแปลงรูป นิพจน์ทางคณิตศาสตร์

รูปแบบนิพจน์ ทางคณิตศาสตร์ แบ่งเป็น 3 ประเภท คือ

1.               นิพจน์ Infix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่กึ่งกลางตัวถูกดำเนินการ      

2.               นิพจน์ Postfix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่ด้านหลังตัวถูกดำเนินการ

3.               นิพจน์ Prefix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่ด้านหน้าตัวถูกดำเนินการ

การ แปลงนิพจน์ Infix เป็น Postfix

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

ลำดับ ความสำคัญของตัวนิพจน์

1.               ^  ยกกำลัง ความสำคัญอันดับแรก

2.               *,/  คูณ,หาร รองจากยกกำลัง

3.               +,-  บวก,ลบ รองจาก ยกกำลัง คูณ หาร

4.               ( )  เครื่องหมายวงเล็บไม่ใช่ตัวดำเนินการแต่ใช้ในการกำหนดลำดับการคำนวณ

หมาย เหตุ  กรณีที่มีลำดับบอกความสำคัญเท่ากันหาไม่มีการกำหนดวงเล็บให้เทียบลำดับความ สำคัญจากซ้ายไปขวายกเว้นเลขยกกำลังความสำคัญจากขวาไปซ้าย

 

การ หาค่าผลลัพธ์จากนิพจน์ Postfix

·         ถ้าเป็นตัวถูกดำเนินการให้ push ลงสแตก

·         ถ้าเป็นตัวดำเนินการให้ pop ตัวดำเนินการออกจากสแตก 2 ตัว แล้วหาค่าผลรวมที่ดำเนินการด้วยตัวดำเนินการนั้น แล้วเก็บผลรวมลงสแตกดำเนินการกับตัวดำเนินการต่อไปจนกว่าจะหมดตัวดำเนินการ