Stack
สแตคเป็นโครงสร้างข้อมูลที่มีลักษณะแบบลำดับ (sequential) คือการกระทำกับข้อมูลจะกระทำที่ปลายข้างเดียวกันที่ส่วนปลายสุดของสแตค การกระทำกับข้อมูลของสแตคประกอบไปด้วยการนำเข้าข้อมูลเข้า (PUSH) ที่ส่วนบนสุดของสแตค และการนำข้อมูลออก (POP) ที่ส่วนบนสุดของสแตคเช่นกัน ในการจะ Push ข้อมูลเข้าก็ต้องตรวจสอบด้วยว่าข้อมูลในสแตคเต็มหรือไม่ หากสแตคเต็มก็จะไม่สามารถ Push หรือนำข้อมูลเข้าได้ เช่นเดียวกับการ Pop ข้อมูลออกก็ต้องตรวจสอบด้วยว่ามีข้อมูลอยู่ในสแตคหรือไม่ หากไม่มีข้อมูลอยู่ในสแตคหรือสแตคว่าง (empty stack) ก็ไม่สามารถ pop ได้การนำข้อมูลเข้า-ออก จากสแตค (push , pop) จะมีลักษณะแบบเข้าหลัง ออกก่อน (LIFO : Last In , First Out) คือ ข้อมูลที่เข้าไปในสแตคลำดับหลังสุด จะถูกนำข้อมูลออกจากสแตคเป็นลำดับแรก
ตัวดำเนินงานพื้นฐานของสแตก ประกอบไปด้วย กระบวนการ 3 กระบวนการคือ
1. Push เป็นฟังก์ชั่นมี 2 พารามิเตอร์คือ s กับ i คือการนำเข้าข้อมูลใส่ลงไปในสแตกเช่น สแตก s ต้องการใส่ข้อมูล i ในสแตก จะได้ push (s,i) คือใส่ข้อมูลi ลงไปในทอปของสแตก s ในการเพิ่มข้อมูลลงในสแตก จะต้องตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม่เต็มก็สามารถเพิ่มข้อมูลลงไปในสแตกได้ แล้วปรับตัวชี้ที่ตำแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow) ก็จะไม่ลสามารถเพิ่มข้อมูลเข้าไปในสแตกได้อีก
2.Pop หรือการดึงข้อมูลออก การดึงออกข้อมูล คือการนำเอาข้อมูลออกจากสแตก ซึ่งการดำเนินการก็จะต้องดำเนินการในตำแหน่ง top กรณีของการ pop ก็จะต้องตวรจสอบด้วยว่า หากไม่มีข้อมูลภายในสแตกแล้วยังมีการเรียก pop ข้อมูลอีกจะทำให้เกิดข้อผิพลาดที่เรียกว่า stack under flow
3. Top หรือตำแหน่งบนสุด ตำแหน่งบนสุดนั้นใช้ top เป็นตัวกำกับ ซึ่งบอกให้ทราบว่าหากต้องการ pop หรือ push ข้อมูลก็สามารถทำได้ ณ ตำแหน่งนี้ โดยลักษณะการดำเนินการของ top เป็นเพียงสิ่งที่บอกตำแหน่งของข้อมูลท่อยู่บนสุดเท่านั้น หากมีการ push ข้อมูลตำแหน่งของ top ก็จะชี้ไปค่าตำแหน่งสูงสุดใหม่ หรือ หากมีการ pop ข้อมูลออกไป top ก็ไม่ใช่ตัวลบค่า แต่จะเป็นการคืนค่าและลดตำแหน่งลงมา ซึ่งtop จะเกิดความผิดพลาดกรณีเดียวกันกับ pop คือ Underflow เมื่อ สแตกนั้นเกิดการว่าง
การแทนที่ข้อมูลของสแตก สามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย 2 ส่วนคือ
1. Head Node จะประกอบไปด้วย 2 ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูลตัวถัดไป
Operations พื้นฐานของ Stack ที่สร้างด้วย Linked list
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 : เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การประยุคต์ใช่สแตก
การประยุคต์ใช่สแตก จะใช่ในงานด้านปฎิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้หลังสุด เช่น การทำงานของโปรแกรม แปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรมย่อย กาคำนวนนิพจน์ทางคณิตศาสตร์ และรีเคอร์ชั่น (Recursion) เป็นต้น
การคำนวนนิพจน์ทางคณิตศาสตร์
สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ lnfix นิพจน์รูปแบบนี้ opeaor จะต้องอยู่ตรงกลางระหว่างตัวถูกดำเนินการ2 ตัว
2.นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเยนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3.นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operator ก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2
ขั้นตอนการแปลงนิพจน์ lnfix เป็นนิพจน์ Postfix
1. อ่านอัขระในนิพจน์ lnfix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัวดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4. ตัวดำเนินการที่เป็นวงเล็บปิด ")" จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่นๆ ถูก pop ออกจากสแตกนำไปเรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ "(" จะ pop วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ lnfix หมดแล้ว ให้ทำการ pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์ Postfix
ในการคำนวนค่า Postfix ที่แปลงมาแล้ว ตัวแปลภาษาจะทำการคำนวนโดยใช้โครงสร้างสแตกช่วยอีกเช่นกัน
ขั้นตอนในการคำนวน
1. อ่านตัวอักษรในนิพจน์ Postfix จากซ้ายไปขวาทีละตัวอักษร
2. ถ้าเป็นตัวถูกดำเนินการ ให้เป็นการ push ตัวดำเนินการนั้นลงในสแตก แล้วกลับไปอ่านอักษรตัวใหม่เข้ามา
3. ถ้าเป็นตัวดำเนินการ ให้ทำการ pop ค่าจากสแตก 2 ค่าโดย ตัวแรกเป็นตัวดำเนินการตัวที่ 2 และตัวที่ 1 ตามลำดับ
4. การทำการคำนวน ตัวถูกดำเนินการตัวที่ 1 ด้วยตัวถูก ดำเนินการตัวที่ 2 โดยใช้ตัวดำเนินการในข้อ 3
5. ทำการ push ผลลัพธ์ที่ได้จากการคำนวนในข้อ 4 ลงสแตก
6. ถ้าตัวอักษรในนิพจน์ Postfix ยังอ่านไม่หมดให้กลับไปทำข้อ 1 ใหม่
ไม่มีความคิดเห็น:
แสดงความคิดเห็น