ใบงานที่ 6 โครงสร้างข้อมูลแบบ Stack

เรื่อง Stack

- โครงสร้างข้อมูลแบบสแตก
- การดำเนินงานพื้นฐานของสแตก

- การแทนที่ข้อมูลของสแตก
- การประยุกต์ใช้สแตก

จุดประสงค์การเรียนรู้

1. เพื่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบสแตกและการทำงาน
2. เพื่อให้นักศึกษาทราบการดำเนินงานพื้นฐานของสแตก
3. เพื่อให้นักศึกษาทราบการแทนที่ของข้อมูลแบบสแตก

4. เพื่อให้นักศึกษาทราบวิธีการประยุกต์ใช้สแตก

สแตก(Stack)เป็นโครงสร้างข้อมูลที่ ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่าการเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ปลายข้างเดียวกัน ซึ่งเรียกว่า Topของสแตก (Top Of Stack)และ ลักษณะที่สำคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)การดำเนินงานพื้นฐานของสแตกการทำงานต่าง ๆของสแตกจะกระทาที่ปลายข้างหนึ่งของสแตกเท่านั้นดั้งนั้นจะต้องมีตัวชี้ตำแหน่งข้อมูลบนสุดของสแตกด้วยการทำงานของสแตกจะประกอบด้วยกระบวนการ 3กระบวนการที่สำคัญ คือ

1.Push คือ การนำข้อมูลใส่ลงไปในสแตกเช่น สแตก s ต้องการใส่ข้อมูล iในสแตกจะได้ push(s,i)คือ ใส่ข้อมูล i ลงไปที่ท็อปของสแตก sในการเพิ่มข้อมูลลงในสแตก จะต้องทำการ ตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม้เต็มก็ สามารถเพิ่มข้อมูลลงไปในสแตกได้แล้วปรับตัวชี้ตำแหน่งให้ไปชี้ที่ตำแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow)ก็จะไม่สามารถเพิ่มข้อมูลเขาไปในสแตกได้อีก

2.Pop คือการนำข้อมูลออกจากส่วนบนสุดของสแตกเช่น ต้องการนำข้อมูลออกจากสแตกsไปไว้ที่ตัวแปร iจะได้ i = pop (s)การนำข้อมูลออกจากสแตกถ้าสแตกมีสมาชิกเพียง 1ตัวแล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง(Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลยแต่ถ้าไม่มีสมาชิกในสแตกแล้วทำการ popสแตกจะทำให้เกิดความผิดพลาดที่เรียกว่าStack Underflow เพราะฉะนั้นก่อนนำข้อมูลออกจากสแตกจะต้องตรวจสอบก่อนว่าสแตกว่างหรือเปล่าจึงจะนำข้อมูลออกจากสแตกได้ และ ปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนำออกไป