Stack (ต่อ)
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 2 ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูล
การดำเนินการเกี่ยวกับสแตก
1.Create Stack จัดสรรหน่วยความจำให้แก่ Head Nodeและส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push Stack การเพิ่มข้อมูลลงไปในสแตก
3. Pop Stack การนำข้อมูลบนสุดออกจากสแตก
4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการลบข้อมูลออจาก
สแตก
5. Empty Stack เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาดในการนข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow6.
6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
7. Stack Count เป็นการนับจำนวนสมาชิกในสแตก
8. Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การแทนที่ข้อมูลของสแตกแบบอะเรย์ เช่นเดียวกับ 8 ขั้นตอนที่กล่าวมาข้างต้น
การประยุกต์ใช้สแตก การประยุกต์ใช้สแตก จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้หลังสุด เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทางคณิตศาสตร์ และรีเคอร์ชั่น (Recursion)
การประยุกต์ใช้สแตก
จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้หลังสุด เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทางคณิตศาสตร์ และรีเคอร์ชั่น (Recursion)
การทำงานของโปรแกรมที่มีโปรแกรมย่อย
ในแต่ละโปรแกรมย่อยก็มีการเรียกใช้โปรแกรมย่อยต่อไปอีก สแตกจะสามารถเข้ามาช่วยในการทำงาน คือ แต่ละจุดของโปรแกรมที่เรียกใช้โปรแกรมย่อยจะเก็บเลขที่ของคำสั่งถัดไปที่เครื่องต้องกลับมาทำงานไว้ในสแตก หลังจากเสร็จสิ้นการทำงานในโปรแกรมย่อยแล้วจะทำการ pop ค่าเลขที่คำสั่งออกมาจากสแตก เพื่อกลับไปทำงานที่คำสั่งต่อจากคำสั่งที่เรียกใช้โปรแกรมย่อย
การคำนวณนิพจน์ทางคณิตศาสตร์
ในการเขียนนิพจน์ทางคณิตศาสตร์เพื่อการคำนวณ จะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วยโดยทั่วไปนิพจน์ทางคณิตศาสตร์สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์Postfix
1. อ่านอักขระในนิพจน์ Infix เข้าทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตก
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่จะดำเนินการตัวอื่น ๆ ถูก pop ออกจากสแตกนำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ popวงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infixหมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุกตัวใน
สแตกนำมาเรียงต่อในนิพจน์Postfix
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์จะประกอบไปด้วย2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 2 ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data) และพอยเตอร์ ที่ชี้ไปยังข้อมูล
การดำเนินการเกี่ยวกับสแตก
1.Create Stack จัดสรรหน่วยความจำให้แก่ Head Nodeและส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push Stack การเพิ่มข้อมูลลงไปในสแตก
3. Pop Stack การนำข้อมูลบนสุดออกจากสแตก
4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก โดยไม่มีการลบข้อมูลออจาก
สแตก
5. Empty Stack เป็นการตรวจสอบการว่างของสแตก เพื่อไม่ให้เกิดความผิดพลาดในการนข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow6.
6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
7. Stack Count เป็นการนับจำนวนสมาชิกในสแตก
8. Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การแทนที่ข้อมูลของสแตกแบบอะเรย์ เช่นเดียวกับ 8 ขั้นตอนที่กล่าวมาข้างต้น
การประยุกต์ใช้สแตก การประยุกต์ใช้สแตก จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้หลังสุด เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทางคณิตศาสตร์ และรีเคอร์ชั่น (Recursion)
การประยุกต์ใช้สแตก
จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้หลังสุด เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทางคณิตศาสตร์ และรีเคอร์ชั่น (Recursion)
การทำงานของโปรแกรมที่มีโปรแกรมย่อย
ในแต่ละโปรแกรมย่อยก็มีการเรียกใช้โปรแกรมย่อยต่อไปอีก สแตกจะสามารถเข้ามาช่วยในการทำงาน คือ แต่ละจุดของโปรแกรมที่เรียกใช้โปรแกรมย่อยจะเก็บเลขที่ของคำสั่งถัดไปที่เครื่องต้องกลับมาทำงานไว้ในสแตก หลังจากเสร็จสิ้นการทำงานในโปรแกรมย่อยแล้วจะทำการ pop ค่าเลขที่คำสั่งออกมาจากสแตก เพื่อกลับไปทำงานที่คำสั่งต่อจากคำสั่งที่เรียกใช้โปรแกรมย่อย
การคำนวณนิพจน์ทางคณิตศาสตร์
ในการเขียนนิพจน์ทางคณิตศาสตร์เพื่อการคำนวณ จะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วยโดยทั่วไปนิพจน์ทางคณิตศาสตร์สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์Postfix
1. อ่านอักขระในนิพจน์ Infix เข้าทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตก
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่จะดำเนินการตัวอื่น ๆ ถูก pop ออกจากสแตกนำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ popวงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infixหมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุกตัวใน
สแตกนำมาเรียงต่อในนิพจน์Postfix
