(Stack)
โครงสร้างสแตก (stack structure)สแตก เป็นโครงสร้างข้อมูลอีกรูปแบบหนึ่งที่มีลักษณะของการจัดเก็บข้อมูลที่สามารถจัดเก็บได้แบบทั้งเรคอร์ด อาร์เรย์ หรือการจัดเก็บในลักษณะลิงค์ลิสต์ แต่โดยรูปแบบของการทำงานนั้นจะเป็นเหมือนการจัดเก็บหรือบันทึกสมาชิกในลักษณะของการพักไว้ สแตก เป็นโครงสร้างที่ถูกออกแบบมาให้มีลักษณะเป็นเชิงเส้น (linear list) สามารถที่จะทำการลบหรือเพิ่มจำนวนสมาชิกเข้ามาในโครงสร้างได้Last In First Out : LIFO หมายถึงข้อมูลที่เข้ามาในลิสต์เป็นลำดับสุดท้าย จะถูกนำออกจากลิสต์เป็นอันดับแรก ตัวอย่างได้แก่การนำชั้นของปิ่นโตเข้าและออกจากเถาปิ่นโต
พื้นฐานการดำเนินการกับสแตก
1.Push หรือการนำเข้าข้อมูล เป็นการดำเนินการในลักษณะของการเพิ่มข้อมูลในสแตกกรณีที่ไม่มีข้อมูลใดอยู่ก็จะ push เข้าไปตำแหน่งแรก ซึ่งถือว่าเป็นตำแหน่ง top แต่ถ้าหากนำข้อมูล push เข้ามาอีกก็จะดำเนินการจัดลงในตำแหน่งต่อจาก top และปรับค่า top มาอยู่ที่ตำแหน่งข้อมูลที่ push เข้ามาใหม่ จะต้องระวังปัญหา stack over flow คือไม่มีพื้นที่ว่างสำหรับการเพิ่มข้อมูลเข้าไปใน สแตก หรือ สแตก เต็ม
2.Pop หรือการดึงข้อมูลออก การดึงออกข้อมูล คือการนำเอาข้อมูลออกจากสแตก ซึ่งการดำเนินการก็จะต้องดำเนินการในตำแหน่ง top กรณีของการ pop ก็จะต้องตวรจสอบด้วยว่า หากไม่มีข้อมูลภายในสแตกแล้วยังมีการเรียก pop ข้อมูลอีกจะทำให้เกิดข้อผิพลาดที่เรียกว่า stack under flow
3. Top หรือตำแหน่งบนสุด ตำแหน่งบนสุดนั้นใช้ top เป็นตัวกำกับ ซึ่งบอกให้ทราบว่าหากต้องการ pop หรือ push ข้อมูลก็สามารถทำได้ ณ ตำแหน่งนี้ โดยลักษณะการดำเนินการของ top เป็นเพียงสิ่งที่บอกตำแหน่งของข้อมูลท่อยู่บนสุดเท่านั้น หากมีการ push ข้อมูลตำแหน่งของ top ก็จะชี้ไปค่าตำแหน่งสูงสุดใหม่ หรือ หากมีการ pop ข้อมูลออกไป top ก็ไม่ใช่ตัวลบค่า แต่จะเป็นการคืนค่าและลดตำแหน่งลงมา ซึ่งtop จะเกิดความผิดพลาดกรณีเดียวกันกับ pop คือ Underflow เมื่อ สแตกนั้นเกิดการว่าง
เครื่องหมายดำเนินการ (operand) ได้แก่เครื่องหมาย + - * ^
ตัวถูกดำเนินการ ได้แก่ สัญลักษณ์แทนค่าตัวเลข เช่น A B C D ….. หรือตัวแปรอื่นรูปแบบนิพจน์ของ infix จะเป็นลักษณะของนิพจน์ที่ใช้งานกันทั่วไป เช่น a + b, A*B ซึ่งมีการนำเครื่องหมายการดำเนินการไว้ตรงกลาง นิพจน์ posfix เป็นนิพจน์ที่มีการจัดรูปแบบของการคำนวณโดยเอาเครื่องหมายดำเนินการไว้หลังตัวถูกดำเนินการเพื่อให้ระบบอ่านตัวถูกดำเนินการก่อนแล้วจึงทราบวิธีการคำนวณ เช่น AB + และนิพจน์ prefix เป็นนิพจน์ที่นำเครื่องหมายสำหรับการดำเนินการ วางไว้ด้านหน้าก่อนตัวถูกดำเนินการ เช่น + ABPrefix : +ABInfix : A+BPosfix : AB+
วิธีการเปลี่ยน Infix เป็น Postfix•Algorithm
การเปลี่ยน Infix เป็น Postfix• ให้ EXP เป็นสมการคณิตศาสตร์ที่เป็น Infix และ Stack เป็น stack ใด ๆ NEXP เป็นสมการที่เป็น Postfix•
1. ใส่ “(“ เข้าไปใน Stack•
2. อ่าน EXP จากซ้ายไปขวา
2.1 ถ้าพบตัวถูกดำเนินการ(ตัวเลข) ให้ใส่เข้าไปใน NEXP2.2 ถ้าพบ “(“ ให้ push ใส่ stack2.3 ถ้าพบตัวดำเนินการ(เครื่องหมาย) ให้ทำดังนี้ - ให้ pop ตัวดำเนินการ ทุกตัวที่มีลำดับความสำคัญกว่าตัวดำเนินการที่พบใน 2.3 ออกมาใส่ใน NEXP ให้หมด - นำตัวดำเนินการที่พบใน2.3 push เข้าใน stack แทนที่2.4 ถ้าพบ “)” ให้ทำดังนี้ • - ให้ push ตัวดำเนินการ ทุกตัวมาใส่ไว้ใน NEXP ให้หมดจนพบ “(“ • - push “(“ ทิ้ง
3. จบการทำงาน
ไม่มีความคิดเห็น:
แสดงความคิดเห็น