ทบทวนบทเรียนครั้งที่ 5
เรื่อง Stack
Stack เป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์(เป็นลำดับ)ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก หรือส่วนบนสุดก็ได้ เเละการนำเข้านำออกจะเป็นลำดับความสำคัญจะอยู่ที่ ตัวเเรก(Top) ของสเเตก คุณสมบัตินี้คือLIFO(last In First Out)คือเข้าก่อนออกก่อน
การดำเนินงานของสเเตกมี3เเบบ(โดยพื้นฐาน)
1. การpush เป็นการใส่ข้อมูลลงสเเตกโดยถ้าสเเตกยังไม่เต็มก็ใส่ลงไปได้
2. การ pop เป็นการนำข้อมูลออกมาจากสเเตกโดยจะpopข้อมูลที่อยู่บนสุดเป็นเงื่อนไขที่ สำคัญมากแต่ถ้าไม่มีสมาชิกในสแตก แล้วทำการ pop สแตก จะทำให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflow
3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก.
การดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack -เป็นการดำเนินการสร้างสแตก
2. Push Stack -เป็นการใส่ข้อมูลลงสเเตกโดยถ้าสเเตกยังไม่เต็มก็ใส่ลงไปได้
3. Pop Stack -เป็นการนำข้อมูลออกมาจากสเเตกโดยจะpopข้อมูลที่อยู่บนสุดเป็นเงื่อนไขที่สำคัญมากแต่ถ้าไม่มีสมาชิกในสแตก แล้วทำการ pop สแตก จะทำให้ เกิดความผิดพลาดที่เรียกว่า Stack Underflow
4. Stack Top -เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก
5. Empty Stack -เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้มีความผิดพลาดในการนำข้อมูลออกจาก สแตกที่เรียกว่า Stack Underflow
6. Full Stack -เป็นการตรวจสอบว่าสแตกเต็มหรือไม่จะได้ไม่ผิดพลาดที่เรียกว่าStack Overflow
7. Stack Count -การนับจำนวนสมาชิก(ข้อมูล)ในสเเตก
8. Destroy Stack -การลบข้อมูลทั้งหมดในสเเตกจนกลายเป็นสเเตกว่าง
รวมทั้งมีการคำนวณนิพจน์ทางคณิตศาสตร์
--การคำนวณนี้จะเป็นการที่เราต้องเเปลงค่า Infix เป็น Postfixมีหลักการทำอยู่โดยเราต้องเปรียบเทียบตัวดำเนินการก่อนที่จะรับเข้าเป็นPostfixส่วนตัวถูกดำเนินการสามารถเข้าPostfix ได้ทันที
--การเเปลงกับจาก Postfix เป็น Infix เป็นการ
1. อ่านตัวอักษรในนิพจน์ Postfix จากซ้ายไปขวาทีละตัวอักษร
2. ถ้าเป็นตัวถูกดำเนินการให้ทำการpushตัวถูกดำเนินการนั้นลงในสแตกแล้วกลับไปอ่านอักษรตัวใหม่เข้ามา3. ถ้าเป็นตัวดำเนินการ ให้ทำการ pop ค่าจากสแตก 2 ค่าโดยตัวแรกเป็นตัวถูกดำเนินการตัวที่ 2 และตัวที่1
4. ทำการคำนวณ ตัวถูกดำเนินการตัวที่ 1ด้วยตัวถูก ดำเนินการตัวที่ 2 โดยใช้ตัวดำเนินการในข้อ 3
5. ทำการ push ผลลัพธ์ที่ได้จากการคำนวณในข้อ 4 ลงสแตก
6. ถ้าตัวอักษรในนิพจน์ Postfix ยังอ่านไม่หมดให้กลับไปทำข้อ 1 ใหม่
ไม่มีความคิดเห็น:
แสดงความคิดเห็น