P. PISHCHAYATIDA: DTS06-29-07-2552

สรุปสิ่งที่ได้จากการเรียน เรื่อง Stack (ต่อ)

การแทนที่ข้อมูลของแสตก ทำได้ 2 วิธี คือ

1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์ ซึ่งเป็นการจัดสรรเนื้อที่หน่วยความจำแบบไดนามิก นั้นคือ หน่วยความจำจะถูกจัดสรรเมื่อมีการขอใช้จริง ๆ ระหว่างการประมวลผลโปรแกรมผ่านตัวแปรชนิด pointer

2. การแทนที่ของมูลของสแตกแบบอะเรย์ ซึ่งเป็นการจัดสรรเนื้อที่หน่วยความจำแบบสแตติก นั้นคือ จะมีการกำหนดขนาดของสแตกล่วงหน้าว่าจะมีขนาดเท่าใดและจะมีการจัดสรรเนื้อที่หน่วยความจำให้เลย

การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์ ประกอบด้วย 2 ส่วน คือ
1. Head Node ประกอบด้วย top pointer และจำนวนสมาชิกมนสแตก(Count)

2. Data Node ประกอบด้วย Data และ Pointer ที่ชี้ไปยังข้อมูลตัวต่อไป

การดำเนินการเกี่ยวกับสแตก

1. Create stack จัดสรรหน่วยความจำให้แก่ head node และส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2. Push stack โดยทั่วไปจะกระทำที่ต้นลิสต์ซึ่งถือว่าเป็นตำแหน่งโหนดบนสุดของสแตกหรือเป็นตำแหน่งที่พุชโหนดเข้าไปในสแตกหลังสุด เมื่อมีการพุชโหนดใหม่ลงในสแตกก็จะต้องปรับค่าพอยน์เตอร์ของโหนดใหม่ชี้ไปที่โหนดบนสุดในขณะนั้น และถ้า top เป็นพอยน์เตอร์ชี้ที่ตำแหน่งโหนดบนสุดในสแตก ให้ทำการปรับพอยน์เตอร์ top ชี้ไปที่โหนดใหม่ที่ทำการพุชลงไปแทน

3. Pop stack โหนดแรกที่จะถูกพ็อปออกมาคือโหนดที่อยู่บนสุดหรือโหนดแรกของลิงค์ลิสต์นั่นเอง ก่อนที่จะทำการพ็อปโหนดต้องตรวจสอบก่อนว่าสแตกว่างหรือไม่ โดยตรวจสอบจากค่าพอยน์เตอร์ที่ชี้ตำแหน่งโหนดบนสุดของสแตก ถ้ามีค่าเป็นนัลแสดงว่า สแตกว่าง และถ้าสแตกไม่ว่างก็สามารถทำการพ็อปโหนดออกจากสแตกได้

4. Stack top เรียกใช้รายการข้อมูลที่อยู่บนสุดของ stack (เป็นการคัดลอกโดยไม่มีการลบข้อมูลออกจากสแตก)
5. Empty stack ตรวจสอบว่า stack ว่างเปล่าหรือไม่ ถ้าไม่มีข้อมูลสแตกเหลืออยู่ เราก็ไม่สามารถทำการ Pop สแตกได้ ในกรณีเช่นนี้เรียกว่า "สแตกว่าง" (Stack Underflow) โดยการตรวจสอบว่าสแตกว่างหรือไม่ เราจะตรวจสอบตัวชี้สแตกว่าเท่ากับ 0 หรือ null หรือไม่ ถ้าเท่ากับ 0 แสดงว่าสแตกว่าง จึงไม่สามารถดึงข้อมูลออกจากสแตกได้
6. Full stack ตรวจสอบว่า stack เต็มหรือไม่ ถ้าไม่มีที่ว่างเหลืออยู่ เราก็จะไม่สามารถทำการ Push สแตกได้ ในกรณีเช่นนี้เราเรียกว่า "สแตกเต็ม" (Stack Overflow) โดยการตรวจสอบว่าสแตกเต็มหรือไม่ เราจะใช้ตัวชี้สแตก (Stack pointer) มาเปรียบเทียบกับค่าสูงสุดของสแตก (Max stack) หากตัวชี้สแตกมีค่าเท่ากับค่าสูงสุดของสแตกแล้ว แสดงว่าไม่มีที่ว่างให้ข้อเก็บข้อมูลอีก
7. Stack count ส่งค่าจำนวนรายการในสแตก หรือเป็นการนับจำนวนสมาชิกในสแตก
8. Destroy stack คืนหน่วยความจำของทุก node ในสแตกให้ระบบ หรือเป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก

การแทนที่ข้อมูลของสแตกแบบอะเรย์ เนื่องจากอาร์เรย์เป็นโครงสร้างที่ต้องมีการกำหนดจองพื้นที่แน่นอน (static) จึงจำเป็นต้องมีการกำหนดขนาดพื้นที่จัดเก็บข้อมูลสูงสุดให้เหมาะสมเมื่อมีการ นำเอาข้อมูลเข้ามาก็จะนำเข้ามาจัดไว้ในอาร์เรย์แรกสุดจากนั้นจึงเรียงลำดับกัน ไปตามพื้นที่ที่กำหนด

การดำเนินการเกี่ยวกับสแตก

1. Create stack สร้าง stack head node
2. Push stack เพิ่มรายการใน stack
3. Pop stack ลบรายการใน stack
4. Stack top เรียกใช้รายการข้อมูลที่อยู่บนสุดของ stack
5. Empty stack ตรวจสอบว่า stack ว่างเปล่าหรือไม่
6. Full stack ตรวจสอบว่า stack เต็มหรือไม่
7. Stack count ส่งค่าจำนวนรายการใน stack
8. Destroy stack คืนหน่วยความจำของทุก node ใน stack ให้ระบบ

การประยุกต์ใช้สแตก

สแตกเป็นโครงสร้างข้อมูลที่มีประโยชน์มาก ใช้มากในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้หลังสุด และข่าวสารที่เก็บเป็นอันดับล่าสุดและรอง ๆ ลงมาใช้ก่อน เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการทำงานของโปรแกรมที่เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์คณิตศาสตร์ และรีเคอร์ชัน (recursion) เป็นต้น

1. การทำงานของโปรแกรมที่มีโปรแกรมย่อย

การทำงานของโปแกรมหลักที่เรียกใช้โปรแกรมย่อย และในแต่ละโปรแกรมย่อยมีการเรียกใช้โปรแกรมย่อยต่อไปอีก ลักษณะของปฏิบัติการแบบนี้ โครงสร้างข้อมูลแบบสแตกสามารถช่วยทำงานได้ โดยที่แต่ละจุดของโปรแกรมที่เรียกใช้โปรแกรมย่อยจะเก็บเลขที่ของคำสั่งถัดไปที่เครื่องต้องกลับมาทำงานไว้ในสแตก หลังจากเสร็จสิ้นการทำงานในโปรแกรมย่อยนั้นแล้ว จะทำการ popค่าเลขที่คำสั่งออกมาจากสแตก เพื่อกลับไปทำงานที่คำสั่งต่อจากคำสั่งที่เรียกใช้โปรแกรมย่อยนั้น จนกระทั่งโหนดในสแตกว่าง

จากภาพ อธิบายได้ว่าในสแตกเก็บเลขที่คำสั่งที่ต้องกลับมาทำหลังจากทำคำสั่งในโปรแกรมย่อยนั้น ๆ เสร็จเรียบร้อยแล้ว เริ่มต้นทำงานในโปรแกรมหลัก Main สแตกจะว่าง เมื่อถึงคำสั่งที่โปรแกรม Main เรียกใช้โปรแกรมย่อย Sub1 จะทำการ push เลขที่คำสั่งของคำสั่ง St1 ลงในสแตก แล้วย้ายการทำงานไปที่โปรแกรมย่อย Sub1 จนจบ

เมื่อต้องกลับมาทำงานในโปรแกรมหลัก Main จะทำการ pop เลขที่คำสั่งในสแตกออกมาเพื่อไปทำงานในโปรแกรมหลักที่เลขที่คำสั่งนั้นต่อไป ทำคำสั่งเรียงลำดับไปเรื่อย ๆ จนถึงคำสั่งที่เรียกใช้โปรแกรมย่อย Sub2 จะทำการ push เลขที่คำสั่งของคำสั่ง St2 ลงในสแตกซึ่งขณะนี้ว่างอยู่ แล้วไปทำงานที่โปรแกรมย่อย Sub2 ซึ่งมีการเรียกใช้โปรแกรมย่อย Sub3 จะทำการ push เลขที่คำสั่งของคำสั่ง St3 ลงในสแตกอีก แล้วจึงย้ายการทำงานไปที่โปรแกรมย่อย Sub3 ซึ่งเรียกใช้โปรแกรมย่อย Sub4 จะทำการ push เลขที่คำสั่งของคำสั่ง St4 ลงในสแตก แล้วไปทำงานที่โปรแกรมย่อย Sub4

เมื่อทำงานในโปรแกรมย่อย Sub4 เสร็จเรียบร้อยแล้วจะทำการ pop เลขที่คำสั่งในสแตกเพื่อกลับมาทำงานต่อในโปรแกรมย่อย Sub3 นั่นคือทำคำสั่ง St4 ไปจนกระทั่งเสร็จสิ้นในโปรแกรมย่อยนี้ แล้วทำการ pop เลขที่คำสั่งที่ต้องกลับไปทำงานในโปรแกรมย่อย Sub2 โดยทำคำสั่ง St3 จนกระทั่งเสร็จสิ้นคำสั่งทั้งหมดในโปรแกรมย่อยนี้ และทำการ pop เลขที่คำสั่งที่ต้องกลับไปทำงานในโปรแกรมหลัก Main ทำคำสั่ง St2 และคำสั่งอื่น ๆ ที่เหลือตามลำดับจนกระทั่งจบโปรแกรม ซึ่งขณะนั้นสแตกจะว่าง

2. การคำนวณนิพจน์ทางคณิตศาสตร์
การเขียนนิพจน์คณิตศาสตร์เพื่อการคำนวณจะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วย โดยทั่วไปนิพจน์คณิตศาสตร์สามารถเขียนได้ 3 รูปแบบดังนี้
1.) นิพจน์อินฟิกซ์ (infix expression) การเขียนนิพจน์ด้วยรูปแบบนี้ ตัวดำเนินการ (operator) อยู่ตรงกลางระหว่างตัวถูกดำเนินการ (operand) 2 ตัว
2.) นิพจน์โพสฟิกซ์ (postfix expression) เป็นการเขียนนิพจน์ที่จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และตัวถูกดำเนินการตัวที่ 2 ก่อน ตามด้วยตัวดำเนินการ
3.) นิพจน์พรีฟิกซ์ (prefix expression) เป็นการเขียนนิพจน์ที่จะต้องเขียนตัวดำเนินการก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และตัวถูกดำเนินการตัวที่ 2 ตามลำดับ

ตัวอย่างนิพจน์คณิตศาสตร์ในรูปแบบต่าง ๆ

ในการเขียนโปรแกรมคอมพิวเตอร์ด้วยภาษาระดับสูงคำสั่งที่เป็นนิพจน์คณิตศาสตร์จะเขียนอยู่ในรูปแบบของนิพจน์ Infix นั่นคือเครื่องหมายคำนวณจะอยู่ตรงกลางระหว่างตัวแปรหรือค่าที่จะถูกนำมาคำนวณด้วย การคำนวณค่าในนิพจน์รูปแบบนี้ ตัวแปลภาษาต้องทำการตรวจสอบนิพจน์จากซ้ายไปขวา เพื่อหาเครื่องหมายหรือตัวดำเนินการที่ต้องคำนวณก่อนจึงจะเริ่มคำนวณให้ แล้วทำแบบนี้ซ้ำ ๆ กันจนกว่าจะคำนวณเครื่องหมายครบทุกตัว ซึ่งการทำงานค่อนข้างช้าและไม่สะดวกในการคำนวณ

ดังนั้นเพื่อแก้ปัญหานี้ การแปลคำสั่งที่เป็นการคำนวณนิพจน์คณิตศาสตร์ ตัวแปลภาษาจะทำการแปลงนิพจน์ Infix ให้อยู่ในรูปแบบที่ช่วยให้การคำนวณนิพจน์สะดวกและรวดเร็วขึ้น โดยแปลงให้อยู่ในรูปแบบของนิพจน์ Postfix ซึ่งตัวดำเนินการอยู่ข้างหลังตัวถูกดำเนินการทั้งสองเสมอ

สำหรับแนวคิดในการเขียนโปรแกรมเพื่อเปลี่ยนนิพจน์ Infix ไปเป็นนิพจน์ Postfix ของตัวแปลภาษา ใช้เทคนิคของการจัดเก็บข้อมูลในโครงสร้างสแตกเข้ามาช่วย โดยการพิจารณานิพจน์ Infix ทีละตัวอักษรจากซ้ายไปขวา และย้ายตัวอักษรเหล่านั้นไปเป็นตัวอักษรในนิพจน์ Postfix ทีละตัว ส่วนตัวดำเนินการจะถูกนำไปเก็บไว้ในสแตก โดยกำหนดค่าของตัวดำเนินการวงเล็บเปิด และวงเล็บปิด

ค่าลำดับความสำคัญของตัวดำเนินการ

ขั้นตอนวิธีในการเขียนโปรแกรมแปลงนิพจน์ Infix ไปเป็นนิพจน์ Postfix

(1) อ่านตัวอักขระในนิพจน์อินฟิกซ์เข้ามาทีละตัว
(2) ถ้าเป็นตัวถูกดำเนินการ จะถูกย้ายไปเป็นตัวอักษรในนิพจน์โพสฟิกซ์
(3) ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัวดำเนินการที่อ่านเข้ามาในขณะนั้นไปเปรียบเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดใน สแตก ดังนี้
- ถ้ามีความสำคัญมากกว่า จะถูกพุชลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้องทำการพ็อปตัวดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์โพสฟิกซ์
(4) ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่พุชลงในสแตก แต่มีผลให้ตัวดำเนินการอื่น ๆ ถูกพ็อปออกจากสแตกนำไปเรียงต่อกันในนิพจน์โพสฟิกซ์ จนกระทั่งเจอตัวดำเนินการวงเล็บเปิด “(” จะพ็อปวงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
(5) เมื่อทำการอ่านตัวอักษรในนิพจน์อินฟิกซ์หมดแล้ว ให้ทำการพ็อปตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์โพสฟิกซ์ จะได้นิพจน์โพสฟิกซ์ตามที่ต้องการ

ตัวอย่าง ขั้นตอนการแปลงนิพจน์ Infix t - 7 + ( 8 - m + n * s ) - ( v * u + a - d ) / 56 ไปเป็นนิพจน์ Postfix

ในการคำนวณค่านิพจน์โพสฟิกซ์ที่แปลงมาเรียบร้อยแล้ว ตัวแปลภาษาจะทำการคำนวณโดยใช้โครงสร้างสแตกช่วยอีกเช่นกัน ซึ่งวิธีการคำนวณค่ามีลำดับขั้นตอนดังต่อไปนี้
(1) อ่านตัวอักษรในนิพจน์โพสฟิกซ์จากซ้ายไปขวาทีละตัวอักษร แล้วทำข้อ 2
(2) ถ้าเป็นตัวถูกดำเนินการ ให้ทำการพุชตัวถูกดำเนินการนั้นลงในสแตก แล้วกลับไปอ่านตัวอักษรใหม่เข้ามา ในข้อ 1
(3) ถ้าเป็นตัวดำเนินการ ให้ทำการพ็อปค่าจากสแตก 2 ค่า โดยตัวแรกเป็นตัวถูกดำเนินการตัวที่ 2 และตัวต่อมาเป็นตัวถูกดำเนินการตัวที่ 1
(4) ทำการคำนวณ ตัวถูกดำเนินการที่ 1 ด้วย ตัวถูกดำเนินการที่ 2 โดยใช้ตัวดำเนินการในข้อ 3
(5) ทำการพุชผลลัพธ์ที่ได้จากการคำนวณในข้อ 4 ลงในสแตก
(6) ถ้าตัวอักษรในนิพจน์โพสฟิกซ์ยังอ่านไม่หมดให้กลับไปทำข้อ1 ถ้าหมดแล้วจบการทำงาน

ตัวอย่าง ขั้นตอนแสดงการคำนวณค่านิพจน์ Infix จากนิพจน์ Postfix
t7-8m-ns*++vu*a+d-56/- โดยใช้โครงสร้างสแตกช่วยในการคำนวณ

ขั้นตอนที่ 1