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