สแตค (Stack) ต่อ
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
การแทนสแตกด้วยโครงสร้างแบบลิงค์ลิสต์นั้น ไม่มีข้อจำกัดของขนาดของสแตกและหน่วยความจำจะถูกใช้ก็ต่อเมื่อมีข้อมูลจริงๆ แล้วเท่านั้น ซึ่งทำให้ประหยัดเนื้อที่ในหน่วยความจำมากกว่า แต่การเขียนโค้ดสำหรับการแทนที่ข้อมูลสแตกด้วยอะเรย์ง่ายกว่าการแทนที่ข้อมูลด้วยลิงค์ลิสต์
การแทนที่ข้อมูลของสแตกด้วยอาร์เรย์
การแทนสแตกด้วยโครงสร้างอาร์เรย์นั้น เนื่องจากอาร์เรย์เป็นโครงสร้างที่ต้องมีการกำหนดจองพื้นที่เท่ากับขนาดที่ใหญ่ที่สุด(static) จึงจำเป็นต้องมีการกำหนดขนาดพื้นที่จัดเก็บข้อมูลสูงสุดให้เหมาะสมเมื่อมีการนำเอาข้อมูลเข้ามาก็จะนำเข้ามาจัดไว้ในอาร์เรย์แรกสุดจากนั้นจึงเรียงลำดับกันไปตามพื้นที่ที่กำหนด
การดำเนินการเกี่ยวกับสแตกการดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack จัดสรรหน่วยความจำให้แก่ Head Nodeและส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
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 เป็นการลบข้อมูลทั้งหมดที่อยู่ใน สแตก8.Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ใน สแตก
การใช้ สแตค เพื่อแปลรูปนิพจน์ทางคณิตศาสตร์
รูปแบบนิพจน์ทางคณิตศาสตร์
• นิพจน์ Infix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่ระหว่างตัวดำเนินการ (Operands) เช่น A+B-C
• นิพจน์ Prefix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หน้าตัวดำเนินการ (Operands) เช่น +-AB
• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หลังตัวดำเนินการ (Operands) เช่น AC*+
ลำดับการทำงานของตัวดำเนินการทางคณิตศาสตร์ (Operator Priority)
มีการลำดับความสำคัญของตัวดำเนินการจากลำดับสำคัญมากสุดไปน้อยสุด คือ ลำดับที่มีความสำคัญมากที่ต้องทำก่อน ไปจนถึงลำดับที่มีความสำคัญน้อยสุดที่ไว้ทำทีหลัง ดังนี้
1.ทำในเครื่องหมายวงเล็บ
2.เครื่องหมายยกกำลัง ( ^ )
3.เครื่องหมายคูณ ( * ) , หาร ( / )
4.เครื่องหมายบวก ( + ) , ลบ ( - )
แปลงนิพจน์ Infix ให้เป็น Postfix ได้ดังนี้
1. ถ้าข้อมูลเข้า (input) เป็นตัวถูกดำเนินการ (operand) ให้นำออกไปเป็นผลลัพธ์ (output)
2. ถ้าข้อมูลเข้าเป็นตัวดำเนินการ (operator) ให้ดำเนินการดังนี้
2.1 ถ้าสแตคว่าง ให้ push operator ลงในสแตค2.2 ถ้าสแตคไม่ว่าง ให้เปรียบเทียบ operator ที่เข้ามากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค
2.2.1 ถ้า operator ที่เข้ามามีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตคให้ push ลงสแตค2.2.2 ถ้า operator ที่เข้ามามีความสำคัญน้อยกว่าหรือเท่ากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค ให้ pop สแตคออกไปเป็นผลลัพธ์ แล้วทำการเปรียบเทียบ operator ที่เข้ามากับ operator ที่ตำแหน่ง TOP ต่อไป จะหยุดจนกว่า operator ที่เข้ามาจะมีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตค แล้วจึง push operator ที่เข้ามานั้นลงสแตค
3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตค
4. ถ้าข้อมูลเข้าเป็นวงเล็บปิด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าจะถึงวงเล็บ เปิด จากนั้นทิ้งวงเล็บเปิดและปิดทิ้งไป
5. ถ้าข้อมูลเข้าหมด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าสแตคจะว่าง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น