สรุปเรื่อง Stack สแตก (Stack) เป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์ มีคุณสมบัติ คือ
การเพิ่มหรือลบข้อมูลในสแตก ลักษณะสำคัญของสแตก คือ
ข้อมูลที่ใส่หลังสุดจะถูกนำออกมาจากสแตกเป็นลำดับแรกสุด เช่น การหยิบ CD, การหยิบจาน เป็นต้น กระบวนการที่สำคัญ 3 กระบวนการ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก ต้องดูด้วยว่าสามารถใส่ข้อมูลลงไปได้หรือไม่
ถ้าสแตกเต็มก็ไม่สามารถเพิ่มข้อมูลได้
2.Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก การ Pop ถ้าไม่มีสมาชิกในสแตก
จะทำให้เกิดความผิดพลาดที่เรียกว่า Stack Underflow
3.Stack Top การคัดลอกข้อมูลบนสุดของสแตก แต่ไม่ได้เอาข้อมูลออกการแทนที่ข้อมูลของสแตก
การดำเนินการเกี่ยวกับสแตก ของทั้งแบบลิงค์ลิสต์และแบบอะเรย์ ได้แก่
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 คือ การลบข้อมูลทั้งหมดที่อยู่ในสแตก
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์ Postfix
1.อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2.ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3.ถ้าเป็นตัวดำเนินการจะนำค่าลำดับความสำคัญของตัวดำเนินการที่อ่านเข้ามาเปรียบเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้องกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตก
ขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4.ตัวดำเนินการที่เป็นวงเล็บปิด ")" จะไม่ push ลงในสแตก แต่มีผลให้ตัวดำเนิน
การอื่นๆ ถูก pop ออกจากสแตกนำไปเรียงต่อกันใน
นิพจน์ Postfix จนกว่าจะเจอ "(" จะ pop วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5.เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix หมดแล้ว ให้ทำการ pop
ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์ Postfixการคำนวณ
ค่า Postfix ที่แปลงมา ตัวแปลภาษาจะทำการคำนวณโดยใช้โครงสร้างสแตกช่วย
ขั้นตอนในการคำนวณ
1.อ่านตัวอักษรในนิพจน์ Postfix จากซ้ายไปขวาทีละตัวอักษร
2.ถ้าเป็นตัวถูกดำเนินการให้ทำการ push ตัวถูกดำเนินการนั้นลงในสแตก แล้วกลับไปอ่านอักษรตัวใหม่เข้ามา
3.ถ้าเป็นตัวดำเนินการ ให้ทำการ pop ค่าจากสแตก 2 ค่า โดยตัวแรกเป็นตัวถูกดำเนินการตัวที่ 2 และตัวที่ 1 ตามลำดับ
4.ทำการคำนวณตัวถูกดำเนินการตัวที่ 1 ด้วยตัวถูกดำเนินการตัวที่ 2 โดยใช้ตัวดำเนินการในข้อ 3
5.ทำการ push ผลลัพธ์ที่ได้จากการคำนวณในข้อ 4 ลงสแตก
6.ถ้าตัวอักษรในนิพจน์ Postfix ยังอ่านไม่หมดให้กลับไปทำข้อ 1 ใหม่
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น