สรุปบทเรียนครั้งที่ 6
เรื่อง Stack
เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ปลายข้างเดียวกันซึ่งเรียกว่า Top ของสแตก ลักษณะสำคัญของสแตกคือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมาจากสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)
การทำงานของสแตกจะประกอบด้วยกระบวนการ 3 กรบวนการที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก เช่น สแตก s ต้องการใส่ข้อมูล i ในสแตกจะได้ push (s,i) คือใส่ข้อมูล i ลงไปที่topของสแตก s
2.Pop คือการนำข้อมูลออกจากส่วนบนสุดของสแตก เช่น ต้องกานำข้อมูลออกจากแสตก s ไปว้ที่ตัวแปร i จะได้ i = pop(s)
3.Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1.การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์ จะประกอบไปด้วย 2 ส่วนคือ
1.1.Head Node จะประกอบด้วย 2 สาวนคือ Top Pointer และจำนวนสมาชิกในสแตก
1.2.Data Node จะประกอบด้วยข้อมูล(Data) และพอยเตอร์ที่ชี้ไปยังตัวถัดไป
2.การแทนที่ข้อมูลของสแตกแบบอะเรย์
การดำเนินการเกี่ยวกับสแตก ได้แก่
1.Create Stack จัดสรรหน่วยความจำให้แก่ Head Node และส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2.Push Stack การเพิ่มข้อมูลลงไปในสแตก
3.Pop Stack การนำข้อมูลบนสุดออกจากสแตก
4.Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการลบข้อมูลออกจากสแตก
5.Empty Stack เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow
6.Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
7.Stack Count เป็นการนับจำนวนสมาชิกในสแตก
8.Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
ขั้นตอนการเก็บข้อมูลในสแตกเมื่อเรียกใช้โปรแกรมย่อย
1.เริ่มต้นทำงานใน Main
2.ขณะที่กำลังทำงานใน Sub1
3.กลับมาทำงานใน Main
4.ขณะที่กำลังทำงานใน Sub2
5.ขณะที่กำลังทำงานใน Sub3
6.ขณะที่กำลังทำงานใน Sub4
ไม่มีความคิดเห็น:
แสดงความคิดเห็น