สแต็กเป็นโครงสร้างข้อมูลแบบลิเนียร์ลิสต์(linear list) ที่สามารถนำข้อมูลเข้าหรือออกได้ทางเดียวคือส่วนบนของสแต็กหรือ หรือเรียกว่า ท๊อปของสแต็ก (Top Of Stack) ซึ่งคุณสมบัติดังกล่าวเรียกว่า ไลโฟลิสต์ (LIFO list: Last-In-First-Out list)
1. การดำเนินการพื้นฐานของสแต็ก
1.1 ฟังก์ชัน Push การเพิ่มข้อมูลในสแต็ก ในการเพิ่มข้อมูลในสแต็ก (pushing) สามารถทำได้โดยให้ทับบนข้อมูลสุดท้ายในสแต็ก และจะสามารถเพิ่มเข้าได้เรื่อย ๆ จนกว่าสแต็กจะเต็ม (Overflow State)
1.2 ฟังก์ชัน Pop การเอาข้อมูลที่อยู่บนสุดในสแต็ก หรือที่ชี้ด้วย Top ออกจากสแต็ก
1.3 ฟังก์ชัน Stack Top จะคืนค่าไปยังผู้ใช้งานเท่านั้น โดยไม่มีการลบข้อมูลออกจากสแต็กแต่อย่างใด
2. การสร้างสแต็ก
2.1 การสร้างสแต็กด้วยอาร์เรย์ การสร้างสแต็กด้วยอาร์เรย์ต้องมีการจัดสรรพื้นที่หน่วยความจำที่แน่นอนไว้ล่วงหน้า
2.2 การสร้างสแต็กด้วยลิงก์ลิสต์ จะเป็นการจัดสรรหน่วยความจำแบบไดนามิก (Dynamic) ไม่จำเป็นต้องกำหนดขนาดของหน่วยความเหมือนกับอาร์เรย์ หน่วยความจำจะถูกจัดสรรเมื่อมีการใช้งานจริงเท่านั้น
3. อัลกอริทึมการสร้างสแต็กด้วยลิงก์ลิสต์
3.1 Create stack สร้าง stack head node
3.2 Push stack เพิ่มรายการใน stack
3.3 Pop stack ลบรายการใน stack
3.4 Stack top เรียกใช้รายการข้อมูลที่อยู่บนสุดของ stack
3.5 Empty stack ตรวจสอบว่า stack ว่างเปล่าหรือไม่
3.6 Full stack ตรวจสอบว่า stack เต็มหรือไม่
3.7 Stack count ส่งค่าจำนวนรายการใน stack
3.8 Destroy stack คืนหน่วยความจำของทุก node ใน stack ให้ระบบ
4. การประยุกต์ใช้งานสแต็ก
4.1 การเรียงลำดับข้อมูลแบบย้อนกลับ (Reversing data) คือการจัดเรียงลำดับข้อมูลใหม่
4.2 การแตกข้อมูลออกเป็นส่วนๆ (Parsing) เป็นการแตกข้อมูลออกเป็นส่วนๆ ให้เป็นอิสระต่อกัน เพื่อส่งไปประมวลผล
4.3 การหน่วงเวลา (Postponement) เป็นการหน่วงเวลาของข้อมูลไว้ชั่วขณะหนึ่งเพื่อรอการประมวลผลในช่วงจังหวะเวลาที่เหมาะสม ซึ่งกรณีดังกล่าว จะนำไปใช้กับการแปลงนิพจน์ Infix มาเป็น Postfix
4.4 การย้อนรอย (Backtracking Steps) คือวิธีการหาคำตอบโดยเดินหน้าไปยังเป้าหมาย เมื่อถึงทางแยกก็จะต้องตัดสินใจเลือกเส้นทางใดเส้นทางหนึ่งเดินหน้าต่อไปเพื่อหาเป้าหมาย หากเดินไปจนสุดเส้นทางแล้วยังไม่พบเป้า ก็จะเดินย้อนกลับมายังจุดแยกครั้งสุดท้ายแล้วเลือกเส้นทางใหม่ที่ยังไม่เคยไป ทำเช่นนี้ไปเรื่อยๆจนกว่าจะพบเป้าหมาย หรือจนครบทุกเส้นทาง
5.รูปแบบนิพจน์ทางคณิตศาสตร์ แบ่งเป็น 3 ประเภทคือ
5.1 นิพจน์ Infix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่กึ่งกลางตัวถูกดำเนินการ (operand)
5.2 นิพจน์ Postfix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่ด้านหลังตัวถูกดำเนินการ (operand)
5.3 นิพจน์ Prefix คือ นิพจน์ที่มีเครื่องหมายดำเนินการอยู่ด้านหน้าตัวถูกดำเนินการ (operand)
Infix : A+B Postfix : AB+ Prefix : +AB |
6. การแปลงนิพจน์ Infix เป็น Postfix มีขั้นตอนดังนี้
6.1 ให้ทำการใส่เครื่องหมายวงเล็บให้กับทุกๆ นิพจน์ด้วยการคำนึงถึงลำดับการคำนวณ เช่น เครื่องหมายคูณและหารต้องมาก่อนเครื่องหมายบวกและลบ
6.2 ทำการเปลี่ยนสัญลักษณ์ Infix ในแต่ล่ะลงเล็บให้มาเป็นสัญลักษณ์แบบ Postfix โดยให้เริ่มต้นจากนิพจน์ที่อยู่วงเล็บในสุดก่อน จากนั้นก็ดำเนินการแปลงให้เป็นนิพจน์ Postfix ด้วยการย้ายโอเปอเรเตอร์ตรงตำแหน่งวงเล็บนั้นไปยังตำแหน่งวงเล็บปิดของคู่นั้นๆ
6.3 ถอดเครื่องหมายวงเล็บทิ้งออกไปให้หมด
7. รีเคอร์ชัน (Recursion)
7.1 การวนรอบ
7.2 การเรียกตัวเอง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น