สรุปเนื้อหาบทเรียน "Data Structure"
เรื่อง Stack (ต่อ)
การแทนที่ข้อมูลของสแตก มี 2 วิธี คือ
การแทนที่ข้อมูลของสแตกด้วยอาร์เรย์
การแทนสแตกด้วยโครงสร้างอาร์เรย์นั้น เนื่องจากอาร์เรย์เป็นโครงสร้างที่ต้องมีการกำหนดจองพื้นที่เท่ากับขนาดที่ใหญ่ที่สุด(static) จึงจำเป็นต้องมีการกำหนดขนาดพื้นที่จัดเก็บข้อมูลสูงสุดให้เหมาะสมเมื่อมีการนำเอาข้อมูลเข้ามาก็จะนำเข้ามาจัดไว้ในอาร์เรย์แรกสุดจากนั้นจึงเรียงลำดับกันไปตามพื้นที่ที่กำหนด
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
การแทนสแตกด้วยโครงสร้างแบบลิงค์ลิสต์นั้น ไม่มีข้อจำกัดของขนาดของสแตกและหน่วยความจำจะถูกใช้ก็ต่อเมื่อมีข้อมูลจริงๆ แล้วเท่านั้น ซึ่งทำให้ประหยัดเนื้อที่ในหน่วยความจำมากกว่า แต่การเขียนโค้ดสำหรับการแทนที่ข้อมูลสแตกด้วยอะเรย์ง่ายกว่าการแทนที่ข้อมูลด้วยลิงค์ลิสต์
การดำเนินงานเกี่ยวกับสแตก
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 เป็นการลบข้อมูลในสแตกออกทั้งหมด
การคำนวณนิพจน์ทางคณิตศาสตร์ แบ่งเป็น 3 ประเภทคือ
1. นิพจน์ Infix คือ นิพจน์ที่มีเครื่องหมายดำเนินการ(operator)อยู่กึ่งกลางตัวถูกดำเนินการ (operand) เช่น A + B
2. นิพจน์ Postfix คือ นิพจน์ที่มีเครื่องหมายดำเนิน(operator)การอยู่ด้านหลังตัวถูกดำเนินการ (operand) เช่น AB+
3. นิพจน์ Prefix คือ นิพจน์ที่มีเครื่องหมายดำเนินการ(operator)อยู่ด้านหน้าตัวถูกดำเนินการ (operand) เช่น -AB
*** เครื่องหมายดำเนินการ (operand) ได้แก่เครื่องหมาย + - * ^ ตัวถูกดำเนินการ ได้แก่ สัญลักษณ์แทนค่าตัวเลข เช่น A B C D
หรือตัวแปรอื่น
สำหรับการดำเนินการด้านการคำนวณนั้น ในระบบคอมพิวเตอร์ไม่สามารถที่จะจัดลำดับของการคำนวณในรูปแบบของ infix ได้ แต่จะแปลงเป็นนิพจน์ของ infix หรือ prefix เสียก่อน โดยลักษณะของการแปลงนิพจน์จะใช้การเปรียบเทียบความสำคัญของตัวดำเนินการ
ลำดับความสำคัญของตัวดำเนินการ
1.เครื่องหมาย (
2.เครื่องหมาย ^
3.เครื่องหมาย * /
4.เครื่องหมาย + -
5.เครื่องหมาย )
ขั้นตอนการแปลง infix เป็น postfix
1.อ่านอักขระใน infix
2.ถ้าเป็น operand ย้ายไปใส่ใน postfix
3.ถ้าเป็น operator จะต้องดูลำดับความสำคัญของตัวดำเนินการด้วยแล้วใส่ลงในสแตกที่เก็บตัวดำเนินการ ถ้ามีค่ามากกว่าให้ push ถ้ามีค่าน้อยกว่าหรือเท่ากันให้ pop ออกแล้วไปเรียงต่อตัวอักษรใน postfix
4.ตัวดำเนินการที่เป็น ) จะไม่ถูก push แต่จะทำให้ตัวดำเนินการตัวอื่นถูก pop ออกมาแล้วไปเรียงต่อใน postfix
5.เมื่ออ่านอักขระใน infix หมด ให้ pop ตัวดำเนินการทุกตัวมาเรียงต่อใน postfix
การคำนวณค่า postfix
1.อ่านตัวอักษรจาก postfix ที่ละตัว
2.ถ้าเป็น operand ให้ push ไปเรื่อยๆ
3.ถ้าเป็น operator ให้ pop ตัวอักษรออก 2 ตัว แล้วทำการคำนวณตัวที่ถูก pop ที่หลังจะเป็นตัวตั้งแล้วนำ push ผลลัพธ์ลงไป
ไม่มีความคิดเห็น:
แสดงความคิดเห็น