โครงสร้างข้อมูลเรื่องทรี

เรื่อง Tree

เนื้อหา

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

- นิยามของทรี

- นิยามที่เกี่ยวข้องกับทรี

- การแทนที่ทรีในหน่วยความจำหลัก

- การแปลงทรีทั่วไปให้เป็นไบนารีทรี

- การท่องไปในทรี

- เอกซเพรสชั่นทรี

- ไบนารีเซิร์ชทรี

จุดประสงค์การเรียนรู้

1. เพื่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบทรี

2. เพื่อให้ทราบนิยามของทรี และที่เกี่ยวข้อง

3. เพื่อให้นักศึกษาทราบวิธีการแทนที่ทรีใน หน่วยความจำหลัก

4. เพื่อให้นักศึกษาทราบการแปลงทรีให้เป็นไบ นารีทรี

5. เพื่อให้นักศึกษาทราบวิธีการท่องไปในทรี

6. เพื่อให้นักศึกษาทราบกระบวนการเอกซเพรสชั่นทรี

7. เพื่อให้นักศึกษาทราบวิธีการไบนารีเซิร์ซทรี

ทรี (Tree)ป็นโครงสร้างข้อมูลที่ความสัมพันธ์ ระหว่าง โหนดจะมัความสัมพันธ์ลดหลั่นกันเป็นลำดับ เช่น (Hierarchical Relationship) ได้มีการนำรูปแบบทรีไปประยุกต์ใช้ในงาน ต่าง ๆ อย่างแพร่หลาย สวนมากจะใชสำหรับแสดง ความสัมพันธ์ระหว่างข้อมูล เช่น แผนผังองค์ประกอบของหน่วยงานต่าง ๆ โครงสร้างสารบัญหนังสือ เป็นต้นแต่ละโหนดจะมีความสัมพันธ์กับ โหนดในระดับที่ต่ำลงมา หนึ่งระดับได้หลาย ๆโหนด เรียกโหนดดั้งกล่าวว่า โหนดแม่(Parent orMother Node)โหนดที่อยู่ต่ำกว่าโหนดแม่อยู่หนึ่งระดับเรียกว่า โหนดลูก (Child or Son Node)โหนดที่อยู่ในระดับสูงสุดและไม่มีโหนดแม่เรียกว่า โหดราก (Root Node) Data Structure โหนดที่มีโหนดแม่เป็นโหนดเดียวกัน รียกว่า โหนดพี่น้อง (Siblings)โหนดที่ไม่มีโหนดลูก เรียกว่า โหนดใบ (Leave Node)เส้นเชื่อมแสดงความสัมพันธ์ระหว่าง โหนดสองโหนดเรียกว่า กิ่ง (Branch)

นิยามของทรี1. นิยามทรีด้วยนิยามของกราฟ ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop)ในโครงสร้าง โหนดสองโหนด ใดๆในทรีต้องมีทางตัดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่ง ทั้งหมด N-1 เส้น การเขียนรูปแบบทรี อาจเขียนได้ 4

2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟทรีประกอบด้วยสมาชิกที่เรียกว่าโหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่า นัลทรี (Null Tree)และถามโหนดหนึ่งเป็นโหดราก ส่วนที่เหลือจะแบ่งเป็น ทรีย่อย (Sub Tree)T1, T2, T3,…,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี

นิยามที่เกี่ยวข้องกับทรี1.ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออกหรือเซตของทรีทแยกจากกัน (Disjoint Trees)2.ทรีที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมี ความสัมพันธ์ที่แน่นอน เช่น ไปทางขวาไปทางซ้าย เป็นต้น

3.ทรีคล้าย (Similar Tree) คือทรีที่มีโครงสร้างเหมือนกันหรือทรีที่มีรูปร่างของทรีเหมือนกันโดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด4.ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์โดยต้องเป็นทรีที่คล้ายกันและแต่ละโหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน

5.กำลัง (Degree) หมายถึงจำนวนทรีย่อยของโหนด นั้น ๆ เช่นในรูปโหนด “B” มีกำลังเป็น 1 เพราะมีทรีย่อย คือ {“D”}ส่วนโหนด “C” มีค่ากำลังเป็นสองเพราะมีทรีย่อย คือ {“E”, “G”, “H”, “I”} และ {“F”}
6.ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่ระดับ 1 และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1หน่วยซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่างจากโหนดราก เรียกวา ความสูง (Height)หรือความ ลึก (Depth)

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

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

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

ไบนารีทรีที่ทุก ๆ โหนดมีทรีย่อยทางซ้ายและทรีย่อยทางขวา ยกเว้นโหนดใบ และโหนดใบทุกโหนดจะต้องอยู่ที่ระดับเดียวกันเรียกว่า ไบนารีทรีแบบสมบูรณ์ (complete binary tree)สามารถคำนวณจำนวนโหนดทั้งหมดในไบนารีทรีแบบสมบูรณ์ได้ถ้ากำหนดให้ Lคือระดับของโหนดใด ๆ และ N คือจำนวนโหนดทั้งหมดในทรีจะได้ว่า
ระดับ 1 มีจำนวนโหนด 1 โหนด
ระดับ 2 มีจำนวนโหนด 3 โหนด
ระดับ 3 มีจำนวนโหนด 7 โหนด
ระดับ L มีจำนวนโหนด 2L - 1โหนด
นั้นคือ จำนวนโหนดทั้งหมดในทรีสมบูรณ์ที่ มี L ระดับ สามารถคำนวณได้จากสูตรดั้งนี้

การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็นไบนารีทรี มีลำดับขั้นตอนการแปลง ดั้งต่อไปนี้
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบความสัมพันธ์ ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จบให้ทรีย่อยทางขวาเอียงลงมา 45 องศา

การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี (Traversing Binary Tree) เพื่อเข้าไปเยือนทุก ๆโหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆโหนด ๆ ละหนึ่งครั้งวิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการเยือนอย่างไร โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N)ทรีย่อยทางซ้าย (แทนด้วย L)หรือทรีย่อยทางขวา (แทนด้วย R)

มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ NLR LNR LRN NRL RNL และ RLN แต่วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นคือ NLR LNR และ LRN ซึ่งลักษณะการนิยามเป็นนิยามแบบ รีเคอร์ซีฟ(Recursive) ซึ่งขั้นตอนการท่องไปในแต่ละแบบมีดังนี้
1. การท่องไปแบบพรีออร์เดอร์(Preorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธีNLR มีขั้นตอนการเดินดังต่อไปนี้
(1) เยือนโหนดราก
(2) ท่องไปในทรีย่อยทางซ้ายแบบพรีออร์เดอร์
(3) ท่องไปในทรีย่อยทางขวาแบบพรีออร์เดอร์

2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LNRมีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบอินออร์เดอร์
(2) เยือนโหนดราก
(3) ท่องไปในทรีย่อยทางขวาแบบอินออร์เดอร์3. การท่องไปแบบโพสออร์เดอร์(Postorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LRN มีขั้นตอนการเดินดังต่อไปนี้
(1) ท่องไปในทรีย่อยทางซ้ายแบบโพสต์ออร์เดอร์
(2) ท่องไปในทรีย่อยทางขวาแบบโพสต์ออร์เดอร์

เอ็กซ์เพรสชันทรี (Expression Tree)
เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ(Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรืออาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression)นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอนในการคำนวณตามความสำคัญของเครื่องหมายด้วยโดยมีความสำคัญตามลำดับดังนี้
- ฟังก์ชัน
- วงเล็บ
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน (unary)
- คูณ หรือ หาร
- บวก หรือ ลบ
- ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
การแทนนิพจน์ในเอ็กซ์เพรสชันทรี ตัวถูกดำเนินการจะเก็บอยู่ที่โหนดใบส่วนตัวดำเนินการจะเก็บในโหนดกิ่งหรือโหนดที่ไม่ใช่โหนดใบเช่น นิพจน์ A + B สามารถแทนในเอ็กซ์เพรสชันทรีได้ดังนี้


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

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

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

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

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


ค. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้ายและทรีย่อยทางขวาต้องเลือกโหนดมาแทนโหนดที่ถูกดึงออก โดยอาจจะเลือกมาจากทรีย่อยทางซ้ายหรือทรีย่อยทางขวาก็ได้
- ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรีย่อยทางซ้ายต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อยทางซ้ายนั้น
- ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมาจากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อยทางขวานั้น

แบบทดสอบ

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

เนื้อหา
- โครงสร้างข้อมูลแบบสแตก
- การดำเนินงานพื้นฐานของสแตก

- การแทนที่ข้อมูลของสแตก
- การประยุกต์ใช้สแตก

จุดประสงค์การเรียนรู้

1. เพื่อให้นักศึกษาทราบโครงสร้างข้อมูลแบบสแตกและการทำงาน
2. เพื่อให้นักศึกษาทราบการดำเนินงานพื้นฐานของสแตก
3. เพื่อให้นักศึกษาทราบการแทนที่ของข้อมูลแบบสแตก

4. เพื่อให้นักศึกษาทราบวิธีการประยุกต์ใช้สแตก

สแตก(Stack)เป็นโครงสร้างข้อมูลที่ ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่าการเพิ่มหรือลบข้อมูลในสแตก จะกระทำที่ปลายข้างเดียวกัน ซึ่งเรียกว่า Topของสแตก (Top Of Stack)และ ลักษณะที่สำคัญของสแตก คือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า LIFO (Last In First Out)การดำเนินงานพื้นฐานของสแตกการทำงานต่าง ๆของสแตกจะกระทาที่ปลายข้างหนึ่งของสแตกเท่านั้นดั้งนั้นจะต้องมีตัวชี้ตำแหน่งข้อมูลบนสุดของสแตกด้วยการทำงานของสแตกจะประกอบด้วยกระบวนการ 3กระบวนการที่สำคัญ คือ

1.Push คือ การนำข้อมูลใส่ลงไปในสแตกเช่น สแตก s ต้องการใส่ข้อมูล iในสแตกจะได้ push(s,i)คือ ใส่ข้อมูล i ลงไปที่ท็อปของสแตก sในการเพิ่มข้อมูลลงในสแตก จะต้องทำการ ตรวจสอบว่าสแตก เต็มหรือไม่ ถ้าไม้เต็มก็ สามารถเพิ่มข้อมูลลงไปในสแตกได้แล้วปรับตัวชี้ตำแหน่งให้ไปชี้ที่ตำแหน่งข้อมูลใหม่ ถ้าสแตกเต็ม (Stack Overflow)ก็จะไม่สามารถเพิ่มข้อมูลเขาไปในสแตกได้อีก

2.Pop คือการนำข้อมูลออกจากส่วนบนสุดของสแตกเช่น ต้องการนำข้อมูลออกจากสแตกsไปไว้ที่ตัวแปร iจะได้ i = pop (s)การนำข้อมูลออกจากสแตกถ้าสแตกมีสมาชิกเพียง 1ตัวแล้วนำสมาชิกออกจากสแตก จะเกิดสภาวะสแตกว่าง(Stack Empty) คือ ไม่มีสมาชิกอยู่ในสแตกเลยแต่ถ้าไม่มีสมาชิกในสแตกแล้วทำการ popสแตกจะทำให้เกิดความผิดพลาดที่เรียกว่าStack Underflow เพราะฉะนั้นก่อนนำข้อมูลออกจากสแตกจะต้องตรวจสอบก่อนว่าสแตกว่างหรือเปล่าจึงจะนำข้อมูลออกจากสแตกได้ และ ปรับตัวชี้ตำแหน่งให้ไปชี้ตำแหน่งของข้อมูลที่ต่อจากข้อมูลที่ถูกนำออกไป3.Stack Top ป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกแต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตกตัวอย่าง
การแทนที่ข้อมูลของสแตก
การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1. การแทนที้ข้อมูลของสแตกแบบลิงค์ลิสต
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสตจะประกอบไปด้วย 2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 2ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data)และพอยเตอร์ ที่ชี้ไปยังข้อมูลการดำเนินการเกี่ยวกับสแตกการดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack
2. Push Stack
3. Pop Stack
4. Stack Top
5. Empty Stack
6. Full Stack
7. Stack Count
8. Destroy Stack

1. Create Stack จัดสรรหน่วยความจำให้แก่ Head Nodeและส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
Algorithm CreateStack
Nothing
Post Head node allocated or error returned
Return Pointer to head node or null pointer if no
memory
1. if (memory available)
1 allocate (StackPrt)
2 StackPtr->count=0
3 StackPtr->top=null pointer
2. else
1 StackPtr=null pointer
3. return StackPtr
End
CreateStack2.Push Stackการเพิ่มข้อมูลลงไปในสแตก

Algorithm PushStack
Pre Stack is a pointer to the stack head structure
Data contains data to pushed into stack
Post Data have been pushed in stack
Return True if successful; False if memory overflow
1. if (stack full)
1 success = false
2. else
1 allocate (newPtr)
2 newPtr->data =data
3 newPtr->next =stack->top
4 stack->top =newPtr
5 stack->count =stack->count+1
6 succes = true
3. return success
3.Pop stack การยำข้อมูลบนสุดออกจากสแตก
Algorithm PopStack
Pre Stack is a pointer to the stack head structure
DataOut is a reference variable to receive the data
Post Data have been returned to calling algorithm
Return True if successful; False if underflow
1. if (stack empty)
1 success = false
2. else
1 dltPtr->data =stack->top
2 dataOut =stack->top->data
3 stack->top =stack->top
4 stack->count =stack->count-1
5 recycle (dltPtr)
6 succes = true
3. return successEnd PopStack

4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกโดยไม่มีการลบข้อมูลออกจากสแตก
Algorithm StackTop
Pre Stack is a pointer to the stack head structure
DataOut is a reference variable to receive the data
Post Data have been returned to calling algorithm
Return True if data returned; False if underflow
1. if (stack empty)
1 success = false
2. else
1 dataOut = stack->top->data
2 succes = true
3. return successEnd StackTop

5.Empty Stack เป็นการตรวจสอบการวางของสแตกเพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow
Algorithm EmptyStack
Pre Stack is a pointer to the stack head structure
Post Returns stack status
Return Boolean, true: stack empty, false: stack contains data
1. if (stack not empty)
1 result = false
2. else
1 result = true
3. return result
End EmptyStack

6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
Algorithm FullStack
Pre Stack is a pointer to the stack head structure
Post Returns stack status
Return Boolean, true: stack full, false: memory available
1. if (memory available)
1 result = false
2. else
1 result = true
3. return result
End FullStack

7. Stack Count เป็นการนับจำนวนสมาชิกในสแตก
Algorithm StackCount
Pre Stack is a pointer to the stack head structure
Post Returns stack count
Return integer count of number of elements in stack
1. Return (stack->count)
End StackCount

8.Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ใน สแตก

Algorithm DestroyStack
Pre Stack is a pointer to the stack head structure
Post Stack empty and all nodes recycled
Return null pointer
1. if (stack not empty)
1 loop (stack->top not null)
1 temp = stack->top
2 stack->top = stack->top->link
3 recycle (temp)
Recycle (stack)
Return null pointer
End DestroyStack
Stack Definition for Array Implementation
stackAry dataType>
stackMax
End Stack

การดำเนินการเกี่ยวกับสแตกการดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack
2. Push Stack
3. Pop Stack
4. Stack Top
5. Empty Stack
6. Full Stack
7. Stack Count
8. Destroy Stack

1. Create Stack
Algorithm CreateStack
stackElem contains size of stack
Head node and array allocated or error returned
Return Pointer to head node or null pointer if no memory
1. if (memory not available)
1 StackPtr = null
1 allocate (StackPtr)
2 StackPtr->count = 0
3 StackPtr->top = -1
4 StackPtr->stackMax=stackElem
5 if (memory not available)
1 recycle (StackPtr)
2 StackPtr = null
6 else1 allocate (StackPtr->stackAry)
3. return StackPtr
End CreateStack

2. Push Stack
Algorithm PushStack
Pre Stack is a pointer to the stack head structureData contains data to be pushed into stack
Post Data have been pushed in stack
Return True if successful ; False if memory overflow
1. if (stack->count is at maximum)
1 success = false

1 stack->count = stack->count + 1
2 stack->top = stack->top + 1
3 stack->stackAry[stack->top] = data
4 success = true
3. Return success
End PushStack

3. Pop Stack
Algorithm PushStack
Pre Stack is a pointer to the stack head structureDataOut contains a reference variable to receive the data
Post Data have been returned to calling algorithm
Return True if successful ; False if underflow
1. if (stack empty)
1 success = false
2. else
1 dataOut = stack->stackAry[stack->top]
2 stack->top = stack->top - 1
3 stack->count = stack->count - 1
4 success = true
3. Return success
End PopStack

4. Stack Top
Algorithm StackTop
Stack is a pointer to the stack headstructure
Data have been returned to calling algorithm
Return True if data returned ; False if underflow
1. if (stack->count zero)
1 success = false
1 dataOut = stack->stackAry[stack->top].data
2 success = true
3. return success
End StackTop

5. Empty Stack
Algorithm EmptyStack
Pre Stack is a pointer to the stack headstructure
Post Return stack status
Return Boolean; True: stack empty , False: stackcontain data
1. if (stack->count > 0)
1 result = false
2 else
1 result = true
3. return result
End EmptyStack

6. Full Stack
Algorithm Full
StackStack is a pointer to the stack
head structure
Post Return stack status
Return Boolean; True: stack full , False:
memory available
1. if (stack->count < result =" false" result =" true">
7. Stack Count
Algorithm StackCount
Pre Stack is a pointer to the stack headstructure
Post Return stack count
Return Integer count of number of elements in stack
1. return (stack->count)
End StackCount
8. Destroy Stack
Algorithm DestroyStack
Pre Stack is a pointer to the stack head structure
Post Head structure and array recycled
Return null pointer
1.if (stack no empty)
1 recycle (stack->stackAry)
2 recycle (stack)
2.return null pointer
End DestroyStack
การประยุกต์ใช้สแตก
การประยุกต์ใช้สแตก จะใช้ในงานด้าน ปฏิบัตการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้ หลังสุด เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการโปรแกรมที่เรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทาง คณิตศาสตร์ และรีเคอร์ชั่น (Recursion)
การทำงานของโปรแกรมที่มีโปรแกรมย่อย
การทำงานของโปรแกรมหลักที่เรียกใช้โปรแกรมย่อยและในแต่ละโปรแกรมย่อยก็มีการเรียกใช้โปรแกรมย่อยต่อไปอีก สแตกจะสามารถเขามาช่วยในการทำงาน คือ แต่ละจุดของโปรแกรมที่เรียกใช้โปรแกรมย่อยจะเก็บเลขที่ของค่ำสั่งถัดไปที่เครื่องต้องกลับมาทำงานไว้ในสแตก หลังจากเสร็จสิ้นการทำงานในโปรแกรมย่อยแล้วจะทำการ pop ค่าเลขที่คำสั่งออกมาจากสแตก เพื่อกลับไปทำงานที่คำสั่งต่อจากคำสั่งที่เรียกใช้โปรแกรมย่อย
แสดงโปรแกรมหลักที่มีการเรียกใช้โปรแกรมย่อยการคำนวณนิพจน์ทางคณิตศาสตร์ในการเขียนนิพจน์ทางคณิตศาสตร์เพื่อการคำนวณจะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วยโดยทั่วไปนิพจน์ทางคณิตศาสตร์สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator 3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2

ตัวอย่างนิพจน์คณิตศาสตร์ในรูปแบบต่าง ๆ
นิพจน์ Postfix นิพจน์ Prefix
AB+C- - +ABC
ABC*+DE/- - +A*BC/DE
AB*C+DE/- - +*ABC/DE

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

ค่าลำดับความสำคัญของตัวดำเนินการ
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์
1. อ่านอักขระในนิพจน์ Infix เข้ามาที่ละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถามความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถามความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัว ดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4.ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก popออกจากสแตก นำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ popวงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5.เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix หมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุก ตัวในสแตกนำมาเรียงต่อในนิพจน์
ตัวอย่าง
การแปลงนิพจน์ Infix เป็นนิพจน์ Postfix นิพจน์ A-B/C+D*Eตัวที่อ่านเข้ามา ผลลัพธ์ในสแตก นิพจน์ Postfix
A ว่าง A
- - A
B - AB
/ -/ AB
C -/ ABC
+ + ABC/-
D + ABC/-D
* +* ABC/-D
E +* ABC/-DE
ABC/-DE*+
นิพจน์ A*(B+C-D)/Eในการคำนวณค่า Postfix ที่แปลงมาแล้ว ตัวแปลภาษาจะทำการคำนวณโดยใช้โครงสร้างสแตกช่วยอีกเช่นกัน ขั้นตอนในการคำนวณ
1. อ่านตัวอักษรในนิพจน์ Postfix จากซ้ายไปขวาทีละ ตัวอักษร
2. ถ้าเป็นตัวถูกดำเนินการ ให้ทำการ push ตัวถูกดำเนินการ นั้นลงในสแตก แล้วกลับไปอ่านอักษรตัวใหม่เข้ามา
3. ถ้าเป็นตัวดำเนินการ ให้ทำการ pop ค่าจากสแตก 2 ค่า โดยตัวแรกเป็นตัวถูกดำเนินการตัวที่ 2 และตัวที่ 1ตามลำดับ
4. ทำการคำนวณ ตัวถูกดำเนินการตัวที่ 1ด้วยตัวถูกดำเนินการตัวที่ 2โดยใช้ตัวดำเนินการในข้อ 3
5. ทำการ push ผลลัพธท์ได้จากการคำนวณในข้อ 4 ลงสแตก
6. ถ้าตัวอักษรในนิพจน์ Postfix ยังอ่านไม่หมดให้กลับไปทำข้อ 1 ใหม่

Algorithm PostfixEvaluate
Pre a valid expression
Post postfix value computed
Return value of expression
1. exprSize= length of string
2. Stack = createStack
3. Index = 1
4. Loop (index<=exprSize) 1 if (expr[index] is operand 1 pushStack(stack,exp[index]) 1 popStack(stack, operand2) 2 popStack(stack, operand1) 3 operator = expr[index] 4 value = calculate (operand1, operator,
5 pushStack(stack,value)
3 index= index+1
5. popStack(stack,result)
6. destroyStack(stack)
7. return (result)
End PostfixEvaluate 

ตัวอย่าง
ขั้นตอนการคำนวณจากนิพจน์ Postfix ABC+D-*E/

แบบทดสอบ

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.ก