โครงสร้างข้อมูลแบบสแตก
โครงสร้างแบบอาร์เรย์และลิงค์ลิสท์
เป็นโครงสร้างที่เราสามารถแทรกหรือลบอิลิเมนท์ในตำแหน่งใดๆ ของรายการได้ตามต้องการ
แต่มีการใช้งานหลายอย่างที่เราต้องการเฉพาะการแทรกหรือการลบข้อมูลในตำแหน่งสุดท้ายเท่านั้น
ซึ่งโครงสร้างข้อมูลที่ใช้ในงานลักษณะนี้ คือ โครงสร้างสแตก
โครงสร้างข้อมูลแบบสแตก (Stack)
สแตกเป็นโครงสร้างข้อมูลที่ถูกกล่าวถึงมากโครงสร้างหนึ่ง
ซึ่งมักจะใช้เป็นประโยชน์ในการอินเตอร์รัพต์
การกระโดดไปมาระหว่างโปรแกรมย่อย การเขียนโปรแกรมแบบเรียกใช้ตัวเอง
(recursive) นอกจากนั้นแล้วโครงสร้างข้อมูลชนิดนี้มักจะใช้ช่วยในการเข้าไปในโครงสร้างแบบพิเศษ
เช่น เครือข่าย หรือต้นไม้ โดยจะช่วยในการจำเส้นทาง
และงานที่เรานำโครงสร้างแบบสแตกแล้วเราพบเห็นบ่อยๆ คือ การยกเลิกคำสั่ง (Undo)
ในไมโครซอฟท์เวิร์ด
สแตกเป็นโครงสร้างแบบเชิงเส้น ที่มีลักษณะที่ว่า การนำข้อมูลเข้าสู่สแตก (insertion)
และการนำข้อมูลออกจากสแตก (deletion) สามารถจะทำได้ที่ปลายด้านหนึ่งของลิสท์ที่แทนสแตกเท่านั้น
ดังนั้นอันดับของการนำสมาชิกเข้าและออกจากสแตกมีความสำคัญ คือ
สมาชิกที่เข้าไปอยู่ในสแตกก่อนจะออกจากสแตกหลังสมาชิกที่เข้าไปใน สแตกทีหลัง
นั่นคือ การเข้าทีหลังออกก่อน จึงเรียกลักษณะแบบนี้ว่า LIFO (Last In
First Out)
สแตกประกอบด้วยส่วนสำคัญ ๆ 2 ส่วน คือ
1. ตัวชี้สแตก หรือ Stack
Pointer ซึ่งเป็นตัวควบคุมการนำสมาชิกเข้า หรือออกจากสแตก เป็นตัวใช้บอกว่าสแตกนั้นเต็มหรือยัง
2. ส่วนสมาชิกของสแตก หรือจะเรียกอีกอย่างว่า Stack Element สมาชิกของสแตกนี้จะเป็นข้อมูลชนิดเดียวกันทั้งหมด
การสร้างสแตก
ในการแทนโครงสร้างข้อมูลแบบสแตกจะใช้โครงสร้างข้อมูลแบบอาร์เรย์
หรือลิงค์ลิสท์ก็ได้ ทั้งนี้แล้วแต่ความเหมาะสมในการนำไปใช้ในการทำงาน ถ้าใช้การแทนที่ข้อมูลของสแตกด้วยอะเรย์ซึ่งเป็นการจัดสรรเนื้อที่หน่วยความจำแบบสแตติก
ก็จะต้องมีการกำหนดขนาดของสแตกล่วงหน้าว่าจะมีขนาดเท่าใด
แต่ถ้าเลือกการแทนที่ข้อมูลของสแตกด้วยลิงค์ลิสต์ซึ่งเป็นการจัดสรรเนื้อที่หน่วยความจำแบบไดนามิก
สแตกจะไม่มีวันเต็มตราบใดที่ยังมีเนื้อที่ในหน่วยความจำ นั้นคือ
หน่วยความจำจะถูกจัดสรรเมื่อมีการขอใช้จริงๆ
ระหว่างการประมวลผลโปรแกรมผ่านตัวแปรชนิด pointer แต่ในที่นี้จะกำหนดให้ตัวสแตกเป็นแบบอาร์เรย์
นอกจากตัวสแตกเองแล้ว
ในการทำงานกับสแตกยังต้องกำหนดตัวแปรเพิ่มอีกหนึ่งตัวเพื่อเก็บตัวชี้สแตก (Stack
Pointer) โดยเริ่มแรกในขณะที่สแตกยังไม่มีข้อมูล
ตัวชี้สแตกก็จะชี้ที่ 0 (ยังไม่ได้ชี้ที่ช่องใดๆ ในสแตก)
การดำเนินงาน
ทำงานกับโครงสร้างข้อมูลแบบสแตกได้แก่ การ PUSH และการ
POP
การ PUSH
เป็นการกระทำหรือการทำงานของสแตกที่นำข้อมูลเข้าสู่สแตก โดยก่อนที่จะนำข้อมูลเข้านั้น
จะต้องมีการจัดการให้ตัวชี้สแตกชี้ไปยังช่องหรือตำแหน่งต่อไปของส่วนของตัวสแตกก่อน
ซึ่งเป็นช่องหรือตำแหน่งที่ว่างอยู่ไม่มีข้อมูล แล้วจึงค่อยทำการ PUSH ข้อมูลลงสู่สแตกในตำแหน่งที่ตัวชี้สแตกชี้อยู่
ในกรณีที่ PUSH ข้อมูลลงสู่สแตก จนตัวชี้สแตกเท่ากับจำนวนช่องของสแตกแล้ว
จะไม่สามารถทำการ PUSH ข้อมูลลงสแตกได้อีก
เนื่องจากตัวชี้สแตกไม่สามารถที่จะขยับไปยังช่องต่อไปได้ จะเกิด Error ที่เรียกว่า Stack
Overflow
ALGORITHM PUSH
เพื่อใช้ในการแทรกข้อมูล x เข้า Stack โดยที่
TOP แทน ตัวชี้สแตก
N แทน จำนวนช่องของสแตก
X แทน ข้อมูล
ST แทน สแตก
1. [ ตรวจสอบ Overflow ]
IF TOP
>= N THEN
PRINT “ STACK OVERFLOW “
EXIT
ENDIF
2. [ เพิ่มค่า Stack Pointer ]
TOP =
TOP + 1
3. [ แทรกข้อมูลเข้า Stack ]
ST
(TOP) = X
4. [ จบการทำงาน ]
EXIT
การ POP
เป็นการกระทำหรือการทำงานของสแตกที่นำข้อมูลที่เก็บอยู่ในสแตกออกจากสแตกมาใช้งาน
โดยการ POP นี้ เมื่อทำการ POP ข้อมูลนั้นออกจากสแตกแล้ว
จะต้องมีการจัดการให้ตัวชี้สแตกชี้ไปยังช่องหรือตำแหน่งก่อนหน้าข้อมูลที่ได้ทำการ POP
ข้อมูลออกไป
การ POP ข้อมูลนี้จะทำการนำข้อมูลในส่วนบนสุดของสแตกออกไปทำงานตามต้องการ
แต่การ POP ข้อมูลนี้จะไม่สามารถ POP ข้อมูลออกจากสแตกที่ว่างเปล่าหรือไม่มีข้อมูลได้
ถ้าเราพยายาม POP ข้อมูลออกจากสแตกที่ว่างเปล่า จะเกิด Error
ที่เรียกว่า Stack
Underflow
ALGORITHM POP
เพื่อใช้ในการลบข้อมูล x จาก Stack โดยที่
TOP แทน ตัวชี้สแตก
N แทน จำนวนช่องของสแตก
Y แทน ข้อมูล
ST แทน สแตก
1. [ ตรวจสอบ Underflow ]
IF TOP
<= 0 THEN
PRINT “ STACK UNDERFLOW “
EXIT
ENDIF
2. [ นำข้อมูลที่ต้องการออกจาก Stack เก็บไว้ที่ Y ]
Y = ST
(TOP)
3. [ ลดค่า Stack Pointer ]
TOP =
TOP - 1
4. [ จบการทำงาน ]
EXIT
เปรียบเทียบประสิทธิภาพของการสร้างสแตกด้วยอะเรย์และลิงค์ลิสต์
การเลือกการแทนที่ข้อมูลสแตกด้วยอะเรย์
มีข้อจำกัดสำหรับขนาดของสแตกและจะต้องจองเนื้อที่เท่ากับขนาดที่ใหญ่ที่สุดของสแตกไว้เลย
เพราะเป็นการจัดสรรเนื้อที่ในหน่วยความจำแบบสแตติก
ส่วนการเลือกการแทนที่ข้อมูลสแตกด้วยลิงค์ลิสต์
ไม่มีข้อจำกัดของขนาดของสแตกและหน่วยความจำจะถูกใช้ก็ต่อเมื่อมีข้อมูลจริงๆ
แล้วเท่านั้น เพราะเป็นการจัดสรรเนื้อที่หน่วยความจำแบบไดนามิก
ซึ่งทำให้ประหยัดเนื้อที่ในหน่วยความจำมากกว่า
แต่การเขียนโค้ดสำหรับการแทนที่ข้อมูลสแตกด้วยอะเรย์ง่ายกว่าการแทนที่ข้อมูลด้วยลิงค์ลิสต์
2. การใช้สแตกในกระบวนการเรียกใช้โพรซีเจอร์หรือฟังก์ชัน
สแตกเป็นโครงสร้างข้อมูลที่มีประโยชน์มาก
ถูกนำไปใช้ทั้งในซอฟท์แวร์ระบบ (System Software) และในการประยุกต์โดยยูสเซอร์
(user) เช่น
ช่วยคอมไพเลอร์ (Compiler) สร้างกฏเกณฑ์ของโปรแกรมมิ่งเกี่ยวกับการเรียกโปรแกรมย่อย
(Subprogram call) ที่ว่าโปรแกรมย่อยใดที่ถูกเรียกทำงานที่หลังสุด
ต้องทำงานเสร็จก่อน ดังรูป
 |
.
|
|
.
|
|
.
|
|
|
.
|
|
.
|
|
.
|
|
|
CALL B
|
|
.
|
|
.
|
|
1000
|
.
|
|
.
|
|
.
|
|
|
.
|
|
CALL C
|
|
.
|
|
|
.
|
4200
|
.
|
|
.
|
โปรแกรม
A โปรแกรม B โปรแกรม C
|
|
|
|
|
|
|
|
|
|
 |
|
4200 |
TOP |
 1000 |
TOP
|
1000
|
|
สแตกที่ใช้เก็บแอดเดรสของโปรแกรม
จากรูปแสดงการเรียกใช้โปรแกรมย่อย
B และ C โดยในโปรแกรมหลัก A มีคำสั่งเรียกโปรแกรมย่อย B และในโปรแกรมย่อย B
มีคำสั่งเรียกโปรแกรมย่อย C
โปรแกรมย่อย C ต้องถูกกระทำเสร็จก่อน
ตามมาด้วยโปรแกรมย่อย B และโปรแกรมหลัก A ซึ่งลำดับของการทำงานของคำสั่งแสดงด้วยลูกศร
โดยสแตกช่วยเก็บที่อยู่ของคำสั่งถัดจากคำสั่งเรียกใช้โปรแกรมย่อย
ซึ่งคำสั่งนี้จะเป็นคำสั่งที่ถูกทำงานต่อหลังจากได้ทำงานตามคำสั่งในโปรแกรมย่อยที่เรียกไป
จากรูปสมมติว่าในขณะทำงานคำสั่งถัดจาก CALL B ในโปรแกรมหลัก A
อยู่ ณ แอดเดรส 1000 และที่อยู่ของคำสั่งถัดจาก
CALL C ในโปรแกรมย่อย B
อยู่ ณ แอดเดรส 4200 เมื่อโปรแกรมหลัก A ทำงานมาถึงคำสั่ง CALL B แอดเดรส 1000 จะถูก PUSH ลงสู่สแตก และเช่นกันเมื่อโปรแกรมย่อย B
ถูกทำงานมาถึงคำสั่ง CALL C แอดเดรส 4200
จะถูก PUSH ลงสู่สแตก ดังรูป ดังนั้นหลังจากทำงานตามคำสั่งในโปรแกรมย่อย C
จนหมดแล้ว
แอดเดรสของคำสั่งถัดไปที่จะถูกทำงานจะถูก POP ออกจากสแตก
คือคำสั่งที่แอดเดรส 4200 และเมื่อจบโปรแกรมย่อย B
คำสั่งที่จะถูกทำงานต่อไปจะถูก POP ออกจากสแตกเช่นเดียวกัน คือคำสั่งที่แอดเดรส 1000
3. การตรวจสอบอักขระสมดุล (Balancing
Symbol)
ผู้ที่มีประสบการณ์ในการเขียนโปรแกรมมาแล้ว
จะพบว่าสิ่งที่เรามักจะหลงลืมเมื่อเขียนโปรแกรม และทำให้เกิดข้อผิดพลาด
อยู่บ่อย ๆ คือ การหลงลืมอักขระสมดุล เช่น { คู่กับ },
[ คู่กับ ], ( คู่กับ ) เป็นต้น
ซึ่งในการตรวจสอบอักขระสมดุลนั้น คอมไพเลอร์นำชนิดข้อมูลแบบสแตกมาประยุกต์ใช้ได้
โดยมีวิธีการดังนี้
ให้อ่านอักขระทีละตัว
- ถ้า
อักขระเป็นอักขระเปิด เช่น {, [, (, เป็นต้น ให้ Push
ลงสแตก
- ถ้า
อักขระเป็นอักขระปิด เช่น }, ], ), เป็นต้น
ให้ตรวจสอบว่าอักขระบน Top ของสแตกเป็นอักขระเปิดที่คู่กันหรือไม่
ถ้าใช่ ให้ Pop อักขระนั้นออกจากสแตก แต่ถ้าไม่ใช่ แสดงผล error
แบบทดสอบสแตก
1.การนำข้อมูลเข้าสแต็กเรียกว่าอะไร
ก. Push
ข. Pop
ค. Stack
ง. Top
2. คุณสมบัติของสแต็กที่เรียกว่า LIFO เนื่องจากสาเหตุใด
ก. มีบัฟเฟอร์สำรองและจัดสรรการเข้าออกของข้อมูล
ข. ข้อมูลเข้าก่อนออกก่อนข้อมูลเข้าทีหลัง ออกทีหลัง
ค. ข้อมูลเข้าก่อนออกทีหลัง ข้อมูลเข้าที่หลังออกก่อน
ง. ข้อมูลเข้าก่อนมีสิทธิออกก่อน หรือทีหลังก็ได้
3. ข้อใดที่กล่าวถึง Operations เกี่ยวกับสแต็กไม่ถูกต้อง
ก. Push A
ข. Push 20
ค. Pop A
ง. Pop
4. ขณะที่สแต็กว่าง ถ้ามีการดำเนินการ Push W , Push D , Push x , Push Q , หลังจากนั้นทำการ Pop ค่าที่ออกจากแสต็กคือค่าใดบ้าง
ก. W D X Q
ข. W D Q X
ค. Q X D W
ง. Q X W D
5. ข้อใดที่เป็นนิพจน์อินฟิกซ์
ก. A+B-C
ข. +AB-C
ค. +-ABC
ง. AB+C-
6. ข้อใดที่เป็นนิพจน์โฟสต์ฟิกซ์
ก. A+B-C
ข. +AB-C
ค. +-ABC
ง. AB+C-
7. ข้อใดเป็น Operators ทั้งหมด
ก. + - * / ^
ข. + ( ) = >
ค. A Z % ( ) ^
ง. + % ( ) ^
8. นิพจน์ AB+ เรียกว่านิพจน์อะไร
ก. นิพจน์อินฟิกซ์
ข. นิพจน์โพสต์ฟิกซ์
ค. นิพจน์พรีฟิกซ์
ง. ไม่มีข้อใดถูก
9. แปลงนิพจน์ A+B/C*D=E
ก. ABC/D*+E-
ข. ABC/D*E+ -
ค. ABC/D+E* -
ง. ABC/D*E+ -
10. แปลงนิพจน์พรีฟิกซ์ - 5 + 9 * 3 – 1 2 เป็นนิพจน์โพสต์ฟิกซ์ได้คำตอบตามข้อใด
ก. 5 9 3 1 2 - * + -
ข. 5 - 9 + 3 * 1 - 2
ค. 5 9 - 3 * 1 + 2
ง. - + * - 5 9 3 1 2
เฉลย1. ก 2. ค 3.ข 4.ก 5.ก 6.ค 7.ข 8.ข 9.ก 10.ก
ไม่มีความคิดเห็น:
แสดงความคิดเห็น