ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การ
เพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ ปลาย
ข้างเดียวกัน ซึ่งเรียกว่า 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) คือ ไม่มีสมาชิกอยู่ในสแตกเลย
การแทนที่ข้อมูลของสแตก
สามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของสแตกแบบ
ลิงค์ลิสต์
2. การแทนที่ข้อมูลของสแตก
แบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
จะประกอบไปด้วย
2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 2
ส่วนคือ top pointer และจำนวนสมาชิกในส
แตก
2. Data Node จะประกอบไปด้วย
ข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูล
ตัวถัดไป
การประยุกต์ใช้สแตก
การประยุกต์ใช้สแตก จะใช้ในงานด้าน
ปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการ
ทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้
หลังสุด เช่น การทำงานของโปรแกรม
แปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่
เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทาง
คณิตศาสตร์ และรีเคอร์ชั่น (Recursion
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์
Postfix
1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็น
ตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับ
ความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบ
กับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่
บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัว
ดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรใน
นิพจน์ Postfix
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตก
แต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตก
นำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(”pop
วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix
หมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุก
ตัวในสแตกนำมาเรียงต่อในนิพจน์
Postfix
ไม่มีความคิดเห็น:
แสดงความคิดเห็น