สรุปบทเรียน
เรื่อง Stack (ต่อ)
การแทนที่ข้อมูลของสแตก มี 2 วิธี คือ
1. การแทนที่ข้อมูลของสแตกด้วยอาร์เรย์ คือ การแทนสแตกด้วยโครงสร้างอาร์เรย์นั้นเนื่องจากอาร์เรย์เป็นโครงสร้างที่ต้องมีการกำหนดขนาดพื้นที่เท่ากับขนาดที่ใหญ่ที่สุด(Static) จึงจำเป็นต้องมีการกำหนดขนาดพื้นที่จัดเก็บข้อมูลสูงสุดให้เหมาะสมเมื่อมีการนำเอาข้อมูลเข้ามาก็จะนำเข้ามาจัดไว้ในอาร์เรย์แรกสุด จากนั้นจึงเรียงลำดับกันไปตามพื้นที่ที่กำหนด
2. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์ คือ การแทนสแตกด้วยโครงสร้างแบบลิงค์ลิสต์นั้น ไม่มีข้อจำกัดของขนาดของสแตกและหน่วยความจำจะถูกใช้ก็ต่อเมื่อมีข้อมูลจริงๆแล้วเท่านั้น ซึ่งทำให้ประหยัดเนื้อที่ในหน่วยความจำมากกว่า แต่การเขียนโค้ดสำหรับการแทนที่ข้อมูลสแตกด้วยอาร์เรย์ง่ายกว่าการแทนที่ข้อมูลด้วยลิงค์ลิสต์
การดำเนินงานเกี่ยวกับสแตก ได้แก่
1. Creste Stack คือ การสร้าง stack head node
2. Push Stack คือ การเพิ่มรายการใน stack
3. Pop Stack คือ การลบรายการใน stack
4. Stack Top คือ การเรียกใช้งานรายการข้อมูลที่อยู่บนสุดของ stack
5. Empty Stack คือ การตรวจสอบว่า Stack ว่างป่าวหรือไม่
6. Full Stack คือ การตรวจสอบว่า Stack เต็มหรือไม่
7. Stack Count คือ การส่งค่าจำนวนรายการในสแตก
8. Destroy Stack คือ การคืนหน่วยความจำของทุกโหนดในสแตกให้ระบบ
การคำนวณนิพจน์ทางคณิตศาสตร์-นิพจน์ทางคณิตศาสตร์ที่เขียนในโปรแกรมคอมพิวเตอร์ ประกอบด้วยตัวดำเนินการ(operator) และตัวถูกดำเนินการ(operand) โดยทั่วไปนิพจน์ทางคณิตศาสตร์สามารถเขียนได้ 3 รูปแบบ คือ1. แบบอินฟิกซ์ (Infix) เป็นรูปแบบที่ตัวดำเนินการอยู่ระหว่างตัวถูกดำเนินการ2. แบบพรีฟิกซ์ (Prefix) เป็นรูปแบบที่ตัวดำเนินการอยู่หน้าตัวถูกดำเนินการ3. แบบโพสต์ฟิกซ์ (Postfix) เป็นรูปแบบที่ตัวดำเนินการอยู่หลังตัวถูกดำเนินการ
***A B C D คือ operand
***+ - * / คือ operator
ขั้นตอนการแปลงนิพจน์ Infix เป็น Postfix
1. อ่านอักขระใน infix ทีละตัว
2. ถ้าเป็น operand จะถูกย้ายไปที่ postfix
3. ถ้าเป็น operator จะต้องดูค่าความสำคัญและนำมาเปรียบเทียบกับ operator ที่อยู่บนสุดของสแตก-ถ้ามีความสำคัญมากกว่า จะถูก Push ลงในสแตก-ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง Pop ตัวดำเนินการที่อยู่ในสแตกไปเรียงต่อที่ Postfix
4. Operator ที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตก แต่จะให้ operator ตัวอื่น pop ออกไปเรียงต่อที่ Postfix จนกว่าจะเจอ “(“
5. เมื่ออ่านตัวอักษรใน Infix หมดแล้ว ให้ทำการ popตัวดำเนินการทั้งหมดในสแตกออกไปเรียงต่อที่ Postfix
ไม่มีความคิดเห็น:
แสดงความคิดเห็น