โครงสร้างข้อมูลแบบทรี

ทรี  ( Trees )

                   ลิสต์แบบไม่ใช่เชิงเส้น(Non-Linear Lists) คือลิสต์ที่สมาชิกแต่ละตัวสามารถมี
สมาชิกตัวถัดไป(Successor) ได้มากกว่าหนึ่งตัว ลิสต์แบบไม่ใช่เชิงเส้นนี้สามารถแบ่งออกเป็น
2 ประเภทด้วยกัน คือ ทรีและกราฟ (Trees and Graphs) สำหรับโครงสร้างข้อมูลแบบทรี สมา
ชิกแต่ละตัวยกเว้นรูทโหนดจะมีสมาชิกตัวก่อนหน้า (Predecessor) เพียงหนึ่งตัว  ในขณะที่โครง
สร้างข้อมูลแบบกราฟ สมาชิกแต่ละตัวสามารถมี Predecessorมากกว่าหนึ่ง

                       ทรีเปรียบเสมือนกับต้นไม้ที่มีราก (Root) และมีลำต้นที่แผ่กิ่งก้านสาขา  โดยแต่ละ
กิ่ง(Branch)ก็จะมีการผลิใบ (Leaf) ไปทั่ว ซึ่งเป็นไปตามความสัมพันธ์ในลักษณะแบบลำดับชั้น
(Hierarchical Relationship) และตัวทรีมีโครงสร้างแบบลำลับชั้นนี้เอง จึงมักนำไปใช้เพื่อนำ
เสนอเป็นแผนผังองค์กร (Organization Chart) โครงสร้างไดเรกทอรี (Diractory) หรือแม้กระ
ทั่งสมาชิกครอบครัวของทรีเอง

                   ทรีประกอบด้วยโหนด (Node) ที่ใช้สำหรับบรรจุข้อมูล โดยจะมีกิ่งซึ่งเป็นเส้นที่เชื่อม
โยงโหนดเข้าด้วยกันที่เรียกว่าบรานช์ (Branch) จำนวนของบรานช์ที่สัมพันธ์กับโหนดเรียกว่าดีกรี
(Degree) และ ถ้าหากทรีนั้นเป็นทรีที่ไม่ใช่ที่ว่าง โหนดแระจะเรียกว่ารูท (Root) โดยโหนดทุก ๆ
โหนดยกเว้นรูทโหนดจะมีเพียง 1 Predecessor ในขณะที่ Successor อาจเป็น 0 หรือ 1 หรือ
มากกว่า 1 ก็ได้
                   สำหรับ Leaf ก็คือโหนดใบที่ไม่มีบรานช์เชื่อมโยงไปยังโหนดตัวถัดไป กล่าวคือ โหนด
ใบก็คือโหนดใบที่ไม่มีตัวตามหลังหือ Successor นั่นเอง ในขณะที่โหนดพ่อ (Parent) จะมีโหนด
ตามหลัง หรือกล่าวอีกนัยหนึ่งว่าโหนดที่มีตัวก่อนหน้าก็คือโหนดลูก (Child) โดยที่โหนดลูกตั้งแต่
สองโหนดหรือมากกว่าที่มาจากพ่อเดียวกันจะเรียกว่าโหนดพี่น้อง (Siblings)  สำหรับความสัมพันธ์
อื่น ๆ ภายในครอบครัวของทรีไม่ว่าจะเป็น ลุง ป้า น้า อา หรือหลาน เหลน โหลนนั้น ไม่มีความจำ
เป็นต้องนำมาใส่ใจขอให้พิจารณาเพียงความสัมพันธ์หลักตัวใหญ่ ๆ ก็เพียงพอ เช่น บรรพบุรุษ
(Ancestor) หรือลูกหลาน (Descendent) เป็นต้น

                   โหนดต่าง ๆ ภายในทรีจะอยู่ในระดับที่แตกต่างกัน โดยเริ่มต้นจากรูทโหนด ซึ่งถือเป็น
ระดับแรกสุด (Level 0) ส่วนลูก ๆ ของรูทโหนดก็คือระดับที่ 1 (Level 1) และลูก ๆของโหนดในระ
ดับที่1 ก็จะอยู่ในระดับที่ 2 (Leve l ) ซึ่งจะเพิ่มระดับไปเรื่อย ๆ เมื่อมีลูกหลานเพิ่มขึ้น ดังนั้นในการ
คำนวณระดับความสูงหรือความลึกของทรีจะคำนวณได้จากการนำค่าระดับสูงสุด (Leaf Node) ของ
ทรีนั้นมาบวกด้วย 1

 ทรี (Tree)

                    เมื่อได้เข้าถึงศัพท์ต่าง ๆ ที่เกี่ยวข้องกับทรีแล้ว ต่อไปนี้ทำการพิจารณาทรีจากรูปที่
  เพื่อนำไปประกอบคำอธิบายให้เข้าใจดียิ่งขึ้น ดังรายละเอียดต่อไปนี้

1. โหนดแรก (Root Node)

                    คือโหนด A ซึ่งโหนดรากหรือรูทโหนด ถือเป็นโหนดแรกสำหรับโครงสร้างทรีที่ใช้เป็น
โหนดเริ่มต้น เพื่อขยายลูกหลานต่อไป
- โหนดพ่อ (Parents) คือโหนด A,B และ F ซึ่งก็คือโหนดที่มี Successor
- โหนดลูก (Children) คือโหนด B,E,F,C,D,G,H และ I ซึ่งก็คือโหนดที่มี Predecessor
- โหนดพี่น้อง (Siblings) คือโหนด {B,E,F},{C,D}และ{G,H,I}
- โหนดใบ (Leaf Node) คือโหนด C,D,E,G,H และ I ซึ่งก็คือโหนดที่ไม่มี Successor

- ดีกรีทั้งหมดของทรี มีค่าเท่ากับ 8

- ดีกรีทั้งหมดของโหนด F มีค่าเท่ากับ 3

- จำนวนของ Leaf โหนด มีค่าเท่ากับ 6

- ระดับความสูงหรือความลึกของทรี คำนวณได้จากสูตร Height =2+1=3

                  นอกจากนี้  ทรียังสามารถแบ่งย่อยออกเป็นซับทรี  (Subtrees) หรือเรียกว่าทรีย่อย
ซึ่งซับทรีเหล่านี้จะเป็นโครงสร้างที่มีการเชื่อมโยงถัดจากรูทโหนด  สำหรับโหนดแรกของซับทรีก็
คือรูทโหนดของซับทรีนั้น ๆ  และยังใช้เป็นชื่อเรียกของซับทรีนั้นด้วย  นอกจากนี้ซับทรียังสามารถ
แบ่งส่วนย่อยออกเป็นซับทรีย่อย ๆ ได้อีก

 ไบนารีทรี (Binary Tees)

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

คุณสมบัติของไบนารีทรี (Properties)
                   ด้วยคูณสมบัติของไบนารีทรีจึงทำให้ไบนารีทรีมีคุณสมบัติพิเศษกว่าทรีทั่วไป ซึ่งประ
กอบด้วยคุณสมบิติที่สามารถนำไปคำนวณเพื่อหาผลลัพธ์ได้ดังต่อไปนี้

 - ความสูงน้อยที่สุดของทรี (Minimum Height)
                   หากต้องการจัดเก็บโหนดจำนวน N โหนดในไบนารีทรี ความสูงน้อยที่สุดของทรีดัง
กล่าวสามารถคำนวณได้จากสูตร
Hmin = [log2N]+

- จำนวนโหนดน้อยที่สุด (Minimum Nodes)
                เราสามารถคำนวณเพื่อการตัดสินใจว่า จำนวนโหนดน้อยที่สุดที่สามารถมีได้ใน
ไบนารีทรีมีจำนวนเท่าไรได้จากสูตร
Nmin =H

- จำนวนโหนดมากที่สุด (Maximum Nodes)
                สำหรับสูตรการคำนวณหาจำนวนโหนดมากที่สุดที่มีได้ในไบนารีทรี จะพิจารณาจาก
ความเป็นจริงด้านคุณสมบัติของไบนารีทรีคือ แต่ละโหนดสามารถมีลูกได้สูงสุดไม่เกิน 2 โหนด
ซึ่งสามารถคำนวณได้จากสูตร
Nmix =2H-1

- ความสมดุล (Balance)
                ความสมดุลของไบนารีทรีจะสามารถทราบได้จากค่า Balance Factor เท่ากับ
0 ซึ่งค่าดังกล่าวคำนวณได้จากการนำความสูงของซับทรีด้านซ้าย (HL) มาหักลบกับความสูงของ
ซับทรีด้านขวา (HR) ที่เป็นไปตามสูตรดังนี้
B = Hl-HR
และจากสูตรดังกล่าว  ความสมดุลของทรีจากรูปที่ 6.5 ก็คือ (a)=0,(b)=0,(c)=1,(d)=1,(e)=0,
(f)=1,(g)=-2 และ (h)=2

แสดงการคำนวณความสมดุลของไบนารีทรี

ไบนารีทรีแบบสมบูรณ์และเกือบสมบูรณ์ (Complete  and Nearly Complete
Binary Trees)
                ไบนารีทรีแบบสมบูรณ์นั้นจะมีจำนวนโหนดสูงสุดที่สามารถมีได้ ซึ่งเป็นไปตามสูตร
Nmax โดยโหนดของซับทรีด้านซ้ายและซับทรีด้านขวาจะมีจำนวนเท่ากัน  สำหรับตัวอย่างไบนารี
ทรีแบบสมบูรณ์ แสดงไว้ดังรูปที่ 6.6 (a) ในขณะที่ไบนารีทรีเกือบสมบูรณ์ก็จะเป็นไปตามสูตร
Hmin หรือเป็นทรีที่มีโหนดเต็มทุกโหนด  ยกเว้นในระดับสุดท้ายที่มีโหนดเฉพาะทางด้านซ้าย
ซึ่งเป็นไปดังรูปที่ 6.6 (b)

- แบบสมบูรณ์จะมี Subtree ด้านซ้ายและขวาเท่ากัน

- แบบเกือบสมบูรณ์ Subtree  ทางด้านซ้ายจะไม่มี

 

การแทนไบนารีทรีในหน่วยความจำ  (Binary Tree Representions)
                         เราสามารถแทนโครงสร้างไบนารีทรีในหน่วยความจำด้วยอาร์เรย์หรือลิงก์ลิสต์
ซึ่งมีรายละเอียดดังต่อไปนี้
การแทนไบนารีทรีด้วยอาร์เรย์
                         ในที่นี้จะกล่าวถึงการแทนโครงสร้างไบนารีทรีในหน่วยความจำด้วยอาร์เรย์หนึ่ง
มิติโดยกรณ์ที่ทรีอยุ่ในรูปแบบของไบนารีทรีแบบสมบูรณ์ ก็จะลำดับตำแหน่งข้อมูลในทรีในแต่ละ
ระดับด้วยการเรียงจากซ้ายไปขวา จากรูปที่ 6.7 เป็นตัวอย่างไบนารีทรีแบบสมบูรณ์  เมื่อนำมา
แทนโครงสร้างด้วยอาร์เรย์หนึ่งมิติ ก็จะมีการลำดับตำแหน่งข้อมูลดังนี้

 

ตัวอย่างไบนารีทรีแบบสมบูรณ์  

แบบทดสอบ โครงสร้างข้อมูลแบบทรี

1.โครงสร้างข้อมูลแบบต้นไม้เป็นโครงสร้างชนิดใด

  ก. ชนิดเชิงเส้น

  ข. ชนิดไม่เชิงเส้น

  ค. ชนิดตัดสินใจเลือก

  ง. ชนิดทำงานซ้ำ

2. โหนดพิเศษโหนดหนึ่งที่อยู่บนสุดแรกเรียกว่าอะไร

  ก. Father

  ข. Subtree

  ค. Leat Node

  ง. Root Node

3. Level มีความหมายตรงกับข้อใด

  ก. รูท

  ข. ดีกรีของโหนด

  ค. โหนดที่เป็นใบ

  ง. ระดับของโหนด

4. ดีกรีของโหนดคืออะไร

  ก. รูทโหนด

  ข. จำนวนต้นไม้ 1 ต้น

  ค. ต้นไม้แบบพรีออเดอร์

  ง. จำนวนต้นไม้ย่อยของโหนดนั้น

5. ป่าไม้ในโครงสร้างข้อมูลแบบต้นไม้ หมายถึงสิ่งใด

  ก. กลุ่มของต้นไม้

  ข. ต้นไม้ย่อยซ้าย

  ค. ต้นไม้ย่อยขวา

  ง. การดูแลต้นไม้

6. โครงสร้างข้อมูลแบบต้นไม้ มีลักษณะคล้ายสิ่งใด

  ก. ใบไม้

  ข. รากของต้นไม้

  ค. ลำต้นของต้นไม้

  ง. กิ่งก้านของต้นไม้

7. ต้นไม้ธรรมชาติจะงอกจากล่างขึ้นบน ส่วนโครงสร้างข้อมูลแบบต้นไม้นั้นจะเจริญเติบโตอย่างไร

  ก.จากล่างไปบน

  ข. จากบนลงล่าง

  ค. จากซ้ายไปขวา

  ง. จากขวาไปซ้าย

8. ต้นไม้ Binary ที่แต่ละโหนดภายในจะมีโหนดย่อยซ้ายโหนดย่อยขวาและโหนดใบหมายถึงต้นไม้แบบใด

  ก. ต้นไม้ไบนารีคู่

  ข. ต้นไม้ไบนารีเดี่ยว

  ค. ต้นไม้ไบนารีแบบสมบูรณ์

  ง. ต้นไม้ไบนารีแบบไม่สมบูรณ์

9. ข้อใดไม่ใช่การแทนต้นไม้ไบนารีในหน่วยความจำ

  ก. การแทนโดยอาศัยพอยน์เตอร์

  ข การแทนโดยอาศัยแอดเดรสของโหนด

  ค. การแทนแบบวีแควนเชียล

  ง. การแทนแบบลำดับชั้น

10. LVR คือวิธีการเดินเข้าแบบใด

  ก. แบบพรีออร์เดอร์

  ข. แบบอินออร์เดอร์

  ค. แบบโพสต์ออร์เดอร์

  ง. ไม่มีข้อใดถูก

 

เฉลย  1.ข  2.ง  3.ง  4.ง  5.ก  6.ง  7.ข  8.ค  9.ง  10.ข 

โครงสร้างข้อมูลแบบสแตก

โครงสร้างข้อมูลแบบสแตก

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

โครงสร้างข้อมูลแบบสแตก (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.ก