เรื่อง Stack
สแตก (Stack) เป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์ที่มีคุณสมบัติที่ว่าการเพิ่มหรือลบข้อมูลในสแตก จะทำที่ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (Top Of Stack)
ลักษณะที่สำคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมาจากสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)
การดำเนินงานของสแตก
การทำงานของสแตกจะประกอบด้วย 3 กระบวนการที่สำคัญ คือ
- Push คือ การนำข้อมูลไปใส่ในสแตก เช่น สแตก s ต้อใส่ข้อมูล i ในสแตก จะได้ push (s,i) คือ ใส่ข้อมูล i ลงไปที่ทอปของสแตก s
- Pop คือ การนำข้อมูลออกมาจากส่วนบนสุดของสแตก เช่น ต้องการนำข้อมูลออกจากสแตก s ไปไว้ที่ตัวแปร i จะได้ i = pop(s)
- Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก
การแทนที่ข้อมูลของสแตก
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
- การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
- การแทนที่ข้อมูลของสแตกแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย 2 ส่วน คือ
- Head Node จะประกอบไปด้วย 2 ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
- Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูลตัวถัดไป
การดำเนินงานเกี่ยวกับสแตก
การดำเนินงานเกี่ยวกับสแตกได้แก่
- Create Stack เป็นการจัดสรรหน่วยความจำ ได้แก่ Head Node และส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
- Push Stack เป็นการเพิ่มข้อมูลลงในสแตก กรณีที่ไม่มีข้อมูลอยู่ในสแตก
- Pop Stack เป็นการนำข้อมูลบนสุดออกจากสแตก
- Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการลบข้อมูลออกจากสแตก
- Empty Stack เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow
- Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดควมผิดพลดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
- Stack Count เป็นการนับจำนวนสมาชิกในสแตก
- Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การเข้าทีหลังออกก่อน
ตัวอย่างเช่น กระดาษรายงานที่เรียงกันทีละแผ่นเป็นปึ้งๆ เราจะต้องใช้แผ่นบนสุดก่อนเสมอ
*********************************************************************************
ไม่มีความคิดเห็น:
แสดงความคิดเห็น