- สแตก เป็นโครงสร้างข้อมูล มีการเก็บข้อมูลได้ทั้งเรคอร์ด อาร์เรย์ หรือ เก็บในลักษณะลิงค์ลิสต์
- รูปแบบของการทำงาน เป็นการจัดเก็บ หรือ บันทึกสมาชิกในลักษณะของการพักไว้
- เป็นโครงสร้างที่มีลักษณะเป็นเชิงเส้น สามารถลบ หรือ เพิ่มจำนวนสมาชิกเข้ามาในโครงสร้างได้
- LIFO ข้อมูลที่เข้ามาในลิสต์เป็นลำดับสุดท้าย จะถูกนำออกจากลิสต์เป็นอันดับแรก
- Push หรือ การนำเข้าข้อมูล เป็นการเพิ่มข้อมูลในสแตก กรณีที่ไม่มีข้อมูลจะ push เข้าในตำแหน่งแรก ซึ่งเป็นตำแหน่ง top แต่หากนำข้อมูล push เข้ามาอีก จะดำเนินการจัดลงในตำแหน่งต่อจาก top และปรับค่า top มาอยู่ที่ตำแหน่งข้อมูลที่ push เข้ามาใหม่ ปัญหา stack over flow คือไม่มีพื้นที่ว่างสำหรับการเพิ่มข้อมูลเข้าไปใน สแตก หรือ สแตก เต็ม
- Pop หรือการดึงข้อมูลออก คือ การนำเอาข้อมูลออกจากสแตก จะดำเนินการในตำแหน่ง top ต้องตวรจสอบด้วยว่า หากไม่มีข้อมูลภายในสแตกแล้วยังมีการเรียก pop ข้อมูลอีกจะทำให้เกิดข้อผิพลาดที่เรียกว่า stack under flow
- Top หรือตำแหน่งบนสุด บอกให้ทราบว่าหากต้องการ pop หรือ push ข้อมูลก็สามารถทำได้ ณ ตำแหน่งนี้ โดยลักษณะการดำเนินการของ top เป็นเพียงสิ่งที่บอกตำแหน่งของข้อมูลท่อยู่บนสุดเท่านั้น หากมีการ push ข้อมูลตำแหน่งของ top ก็จะชี้ไปค่าตำแหน่งสูงสุดใหม่ หรือ หากมีการ pop ข้อมูลออกไป top ก็ไม่ใช่ตัวลบค่า แต่จะเป็นการคืนค่าและลดตำแหน่งลงมา
#พื้นฐานของ Stack ที่สร้างด้วย Linked list#
- Create stack: สร้าง stack head node
- Push stack: เพิ่มรายการใน stack
- Pop stack: การนำข้อมูลบนสุดออกจาก stack (ไม่บอกตำแหน่งเพราะเอาตัวบนสุดออกมาเท่านั้น)
- Stack top: เป็นการคัดลอกข้อมูลที่อยู่บนสุดของ stack
- Empty stack: ตรวจสอบว่า stack ว่างเปล่าหรือไม่
- Full stack: ตรวจสอบว่า stack เต็มหรือไม่
- Stack count: ส่งค่าจำนวนรายการใน stack
- Destroy stack: คืนหน่วยความจำของทุก node ใน stack ให้ระบบ
#การประยุกต์ใช้งานสแตกในการแปลงรูปนิพจน์ทางคณิตศาสตร์#
1.รูปแบบนิพจน์ทางคณิตศาสตร์ แบ่งเป็น 3 ประเภทคือ
- Infix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่กึ่งกลางตัวถูกดำเนินการ (operand)
- Postfix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่ด้านหลังตัวถูกดำเนินการ (operand)
- Prefix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่ด้านหน้าตัวถูกดำเนินการ (operand)
- เครื่องหมายดำเนินการ (operand) ได้แก่ + - * ^
- ตัวถูกดำเนินการ ได้แก่ สัญลักษณ์แทนค่าตัวเลข หรือ ตัวแปรอื่น
#นิพจน์ infix#
- จะเป็นลักษณะของนิพจน์ที่ใช้งานกันทั่วไป มีการนำเครื่องหมายการดำเนินการไว้ตรงกลาง
#นิพจน์ posfix#
- เป็นนิพจน์ที่มีการจัดรูปแบบของการคำนวณโดยเอาเครื่องหมายดำเนินการไว้หลังตัวถูกดำเนินการเพื่อให้ระบบอ่านตัวถูกดำเนินการก่อนแล้วจึงทราบวิธีการคำนวณ
2.การแปลงนิพจน์ infix เป็น posfix ในระบบคอมพิวเตอร์ไม่สามารถที่จะจัดลำดับของการคำนวณในรูปแบบของ infix ได้ แต่จะแปลงเป็นนิพจน์ของ infix หรือ prefix เสียก่อน
- ลักษณะของการแปลงนิพจน์จะใช้การเปรียบเทียบความสำคัญของตัวดำเนินการ เครื่องหมายในการคำนวณทั้ง 5 ตัว และหลักการอัลกอริทึมของการแปลงนิพจน์
#วิธีการเปลี่ยน Infix เป็น Postfix#
1. ใส่ “(“ เข้าไปใน Stack•
2. อ่าน EXP จากซ้ายไปขวา
- 2.1 ถ้าพบตัวถูกดำเนินการ(ตัวเลข) ให้ใส่เข้าไปใน NEXP
- 2.2 ถ้าพบ “(“ ให้ push ใส่ stack
- 2.3 ถ้าพบตัวดำเนินการ(เครื่องหมาย) ให้ทำดังนี้ - ให้ pop ตัวดำเนินการ ทุกตัวที่มีลำดับความสำคัญกว่าตัวดำเนินการที่พบใน 2.3 ออกมาใส่ใน NEXP ให้หมด - นำตัวดำเนินการที่พบใน2.3 push เข้าใน stack แทนที่
- 2.4 ถ้าพบ “)” ให้ทำดังนี้ • - ให้ push ตัวดำเนินการ ทุกตัวมาใส่ไว้ใน NEXP ให้หมดจนพบ “(“ • - push “(“ ทิ้ง
3. จบการทำงาน
ไม่มีความคิดเห็น:
แสดงความคิดเห็น