สแตก (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
เพราะฉะนั้นก่อนนำข้อมูลออกจากส
แตกจะต้องตรวจสอบ ก่อนว่าสแตกว่าง
หรือเปล่า จึงจะนำข้อมูลออกจากสแตกได้
และ ปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งของ
ข้อมูลที่ต่อจากข้อมูลที่ถูกนำ ออกไป
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
จะประกอบไปด้วย2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 2
ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วย
ข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูลตัวถัดไป
การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack 5. Empty Stack
2. Push Stack 6. Full Stack
3. Pop Stack 7. Stack Count
4. Stack Top 8. Destroy Stack
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
เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การคำนวณนิพจน์ทางคณิตศาสตร์
ในการเขียนนิพจน์ทางคณิตศาสตร์เพื่อการคำนวณ จะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วยโดยทั่วไปนิพจน์ทางคณิตศาสตร์สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์Postfix
1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบ
กับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัว
ดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรใน
นิพจน์ Postfix
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตก
แต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตก
นำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ pop
วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infixหมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุก
ตัวในสแตกนำมาเรียงต่อในนิพจน์Postfix
