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

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

                      ทรี (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 จงเลือกคำตอบที่ถูกต้องเพียงคำตอบเดียว โดยทำเครื่องหมาย X ทับตัวเลือกที่ต้องการ

1.โครงสร้างข้อมูลแบบต้นไม้เป็นโครงสร้างชนิดใด
ก. ชนิดเชิงเส้น
ข. ชนิดไม่เชิงเส้น
ค. ชนิดตัดสินใจเลือก
ง. ชนิดทำงานซ้ำ

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

3. Level มีความหมายตรงกับข้อใด
ก. รูท
ข. ดีกรีของโหนด
ค. โหนดที่เป็นใบ
ง. ระดับของโหนด

4. ดีกรีของโหนดคืออะไร
ก. รูทโหนด
ข. จำนวนต้นไม้ 1 ต้น
ค. ต้นไม้แบบพรีออเดอร์
ง. จำนวนต้นไม้ย่อยของโหนดนั้น

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

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

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

8. ต้นไม้ Binary ที่แต่ละโหนดภายในจะมีโหนดย่อยซ้ายโหนดย่อยขวาและโหนดใบหมายถึงต้นไม้แบบใด
ก. ต้นไม้ไบนารีคู่
ข. ต้นไม้ไบนารีเดี่ยว
ค. ต้นไม้ไบนารีแบบสมบูรณ์
ง. ต้นไม้ไบนารีแบบไม่สมบูรณ์

9. ข้อใดไม่ใช่การแทนต้นไม้ไบนารีในหน่วยความจำ
ก. การแทนโดยอาศัยพอยน์เตอร์
ข การแทนโดยอาศัยแอดเดรสของโหนด
ค. การแทนแบบวีแควนเชียล
ง. การแทนแบบลำดับชั้น

10. LVR คือวิธีการเดินเข้าแบบใด
ก. แบบพรีออร์เดอร์
ข. แบบอินออร์เดอร์
ค. แบบโพสต์ออร์เดอร์
ง. ไม่มีข้อใดถูก

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

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

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

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


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

การประยุกต์ใช้งานของสแตก
สแตกเป็นโครงสร้างที่มีประโยชน์มาก ถูกนำไปประยุกต์ใช้ในหลายๆ ด้าน เช่น

1. การจัดการหน่วยความจำ
โดยทั่วไปการจัดการหน่วยความจำจะเป็นดังนี้

Reserved By System	Programs And procedures	Dynamic Varible Heap	Local Variable stack	Operating system
Low Memory		Available space		High Memory

ลองมาดูตัวอย่างของการจัดเก็บค่าของตัวแปรในหน่วยความจำในตัวอย่าง 

1 ---->     main () {                                                                                                 // Start main ()

                        int    P, Q, R;                                                                                  // User defined

2 ---->             void  A (void) {                                                                              // Start function A

                                int    S;                                                                                    // User defined

3 ---->                             B() ;

7 ---->    }                                                                                         // End function A

3 ---->             void  B (void) {                                                                              // Start function B

                                struct list {

                                        int                    data;

                                        struct list        *link;

                                } node;

                                struct list                *D ;

                                int    X, Y;                                                                                //User  defined

4 ---->                     new(D);

                                new(D);

5 ---->                     new (D);

6 ---->                     }                                                                                               // End function B

2 ---->             A;

8 ---->     }                                                                                                               // End main ()

ภาพของค่าของตัวแปรในหน่วยความจำเมื่อกำลังประมวลผลโปรแกรม ณ จุดต่างๆ เป็น ดังนี้ 

1. เมื่อเริ่มทำงานในส่วน main() เนื้อที่หน่วยความจำในสแตกจะถูกใช้สำหรับตัวแปร P, Q, R

Reserved By System	Programs And procedures				P Q R	Operating system
Low Memory		Top of heap				Top of stack

2. เมื่อเรียกใช้ฟังก์ชั่น A จะเข้าไปทำงานในส่วนของฟังก์ชั่น A และเนื้อที่หน่วยความจำในสแตกจะถูกใช้สำหรับตัวแปร S

Reserved By System	Programs And procedures				S	P Q R	Operating System
Low Memory		Top of heap				Top of stack

3. เมื่อเรียกใช้ฟังก์ชั่น B จะเข้าไปทำงานในส่วนของฟังก์ชั่น B และเนื้อที่หน่วยความจำในสแตกจะถูกใช้สำหรับตัวแปร X, Y

Reserved By System	Programs And procedures				X Y	S	P Q R	Operating system
Low Memory		Top of heap				Top of stack

   4. หลังคำสั่ง new (D)

Reserved By System

Programs And procedures

D

X Y

S

P Q R

Operating system

Low Memory

Top of heap

Top of stack

   5. หลังคำสั่ง new (D)

Reserved By System

Programs And procedures

D

D

D

X Y

S

P Q R

Operating system

Low Memory

Top of heap

Top of stack

   6. หลังจากเสร็จสิ้นการประมวลผลของฟังก์ชั่น B (ตัวแปร X, Y จะถูก Pop ออกจาก สแตก )

Reserved By System

Programs And procedures

D

D

D

S

P Q R

Operating system

Low Memory

Top of heap

Top of stack

       

ข้อสังเกต ถ้าเราเรียกใช้ตัวแปรแบบไดนามิกและเราไม่ได้ทำการ delete เมื่อไม่ต้องการใช้แล้ว (เช่นเราออกจากฟังก์ชั่น B แล้ว ) เนื้อที่ใน heap ก็จะเสียไปไม่สามารถนำมาใช้ได้อีก

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)
ผู้ที่มีประสบการณ์ในการเขียนโปรแกรมมาแล้ว จะพบว่าสิ่งที่เรามักจะหลงลืมเมื่อเขียนโปรแกรม และทำให้เกิดข้อผิดพลาด
4. การแปลงนิพจน์ infix ให้เป็น postfix
โดยปกติเวลาเขียนโปรแกรมสั่งให้เครื่องคำนวณต้องเขียนนิพจน์ที่ต้องการไปในตัวโปรแกรม ซึ่งนิพจน์เหล่านี้เรียกว่า นิพจน์ infix คือนิพจน์ที่มี ตัวดำเนินการ (Operator) อยู่ระหว่างตัวถูกกระทำ (Operand) เช่น A + B เครื่องหมาย + เป็นโอเปอเรเตอร์ระหว่างโอเปอร์แรนด์ A และ B ซึ่งเห็นว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย

ตัวดำเนินการ ก็คือ เครื่องหมายทางคณิตศาสตร์ สำหรับการคำนวณต่างๆ เรียงตามลำดับการดำเนินการก่อน-หลัง (precedence) ได้แก่

ยกกำลัง ^

คูณ หาร * , /

บวก ลบ + , -

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

ข้อเสียของนิพจน์ infix ที่ทำให้คอมไพเลอร์ยุ่งยาก คือ ลำดับความสำคัญของโอเปอร์เรเตอร์ (Precedence) ที่ต่างกัน เช่น เครื่องหมายยกกำลัง (^) มีความสำคัญมากกว่าเครื่องหมายคูณ (*) และหาร (/) และเครื่องหมายคูณและหารมีความสำคัญมากกว่าเครื่องหมายบวก (+) และลบ (-) เครื่องหมายใดมีลำดับความสำคัญมากกว่าจะถูกคำนวณก่อน (ถ้าไม่มีวงเล็บกำกับ) เช่น A + B * C เครื่องจะคำนวณ B * C ก่อนแล้วนำผลลัพธ์นั้นไปบวกกับค่า A ซึ่งจะทำงานเหมือนกับ A + (B * C) ส่วนนิพจน์ใดที่มีโอเปอร์เรเตอร์ที่มีลำดับความสำคัญเท่ากัน การคำนวณจะกระทำจากซ้ายไปขวา เช่น A – B + C จะทำ A – B ก่อน แล้วจึงนำผลลัพธ์นั้นไปบวกกับค่า C

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

AB+ หมายถึง A + B

AB- หมายถึง A - B

AB* หมายถึง A * B

AB/ หมายถึง A / B

AB^ หมายถึง A ^ B

ข้อดีของนิพจน์ postfix คือเป็นนิพจน์ที่มีการคำนวณตามโอเปอร์เรเตอร์ที่มาก่อนหลัง เช่น นิพจน์ ABC*+ หมายถึง ทำการคูณแล้วจึงทำการบวก ซึ่งคือต้องคำนวณ B*C ก่อน แล้วจึงนำผลลัพธ์นั้นไปบวกกับ A ต่อไป 

อัลกอริทึ่มแปลงนิพจน์ INFIX ให้เป็นนิพจน์ POSTFIX
            เนื่องจากนิพจน์ infix มีลำดับความสำคัญของเครื่องหมายโอเปร์เรเตอร์ ซึ่งหมายความว่า โอเปร์เรเตอร์ที่มาก่อน อาจจะไม่ใช่โอเปอร์เรเตอร์ที่ถูกประมวลผลก่อน ดังนั้น สแตกซึ่งมีคุณสมบัติเป็นไลโฟลิสท์จึงมีส่วนช่วยในการแปลงนิพจน์ infix ให้เป็นนิพจน์ postfix ในการนี้มีสิ่งที่เกี่ยวข้อง 3 อย่าง คือ

1. ข้อมูลเข้าซึ่งเป็นนิพจน์ infix
2. ข้อมูลออกหรือนิพจน์ postfix
3. สแตกที่ใช้เก็บโอเปอร์เรเตอร์
ข้อมูลเข้าจะถูกอ่านมาทีละอักขระ (character) แล้วดำเนินการต่อไปดังนี้
1. ถ้าข้อมูลเข้า (input character) เป็นโอเปอร์แรนด์ ให้พิมพ์ออกเป็นผลลัพธ์ (postfix string)
2. ถ้าข้อมูลเข้าเป็นโอเปอร์เรเตอร์ ให้ทำดังนี้
2.1 ถ้าสแตกยังว่างอยู่ ให้ PUSH โอเปอร์เรเตอร์ลงสแตก
2.2 ถ้าสแตกยังไม่ว่าง ให้เปรียบเทียบ โอเปอร์เรเตอร์ที่เข้ามากับโอเปอร์เรเตอร์ที่ ท็อปของสแตก
2.2.1 ถ้าโอเปอร์เรเตอร์ที่เข้ามามี precedence น้อยกว่าหรือเท่ากับโอเปอร์เรเตอร์ที่ท็อปของสแตก ให้ POP โอเปอร์เรเตอร์จากสแตกไปเป็นผลลัพธ์ และเปรียบเทียบกับโอเปอร์เรเตอร์ที่ท็อปของสแตกต่อไป หยุดเมื่อโอเปอร์เรเตอร์ที่เป็นข้อมูลเข้ามี precedence มากกว่าโอเปอร์เรเตอร์ที่ ท็อปของสแตก หลังจากนั้นให้ PUSHข้อมูลลงสแตก
2.2.2 ถ้าโอเปอร์เรเตอร์ที่เข้ามามี precedence มากกว่าโอเปอร์เรเตอร์ที่ท็อปของสแตก ให้ PUSH ลงสแตก
3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิดให้ PUSH ลงสแตก
4. ถ้าข้อมูลเข้าเป็นวงเล็บปิดให้ POP ออกจากสแตกจนกว่าจะถึงวงเล็บเปิด และนำผลที่ POP ออกไปเป็นผลลัพธ โดยทิ้งวงเล็บปิดและเปิดทิ้งไป
5. ถ้าข้อมูลหมด ให้ POP Operator ที่ยังคงเหลือในสแตกไปไว้เป็นผลลัพธ์จนสแตกว่าง

ตัวอย่างของการแปลงนิพจน์ Infix เป็น Postfix
นิพจน์ Infix : A – B * C

INPUT	STACK	OUTPUT
A		A
-	-	A
B	-	AB
*	-*	AB
C	-*	ABC
		ABC*-

                 นิพจน์ Postfix ที่ได้ คือ : ABC*-

นิพจน์ Infix : A * (B + C)

INPUT	STACK	OUTPUT
A		A
*	*	A
(	* (	A
B	* (	AB
+	* ( +	AB
C	* ( +	ABC
)	*	ABC+
		ABC+*

 นิพจน์ Postfix ที่ได้ คือ : ABC+*

นิพจน์ Infix : A ^B ^ (C + D)

INPUT	STACK	OUTPUT
A		A
^	^	A
B	^	AB
^	^ ^	AB
(	^ ^ (	AB
C	^ ^ (	ABC
+	^ ^ ( +	ABC
D	^ ^ ( +	ABCD
)	^ ^	ABCD +
		ABCD + ^ ^

นิพจน์ Postfix ที่ได้ คือ : ABCD+^^

นอกจากวิธีการแปลงนิพจน์ Infix เป็น Postfix ตามข้างต้นแล้ว ยังสามารถทำได้ด้วยตนเองโดยไม่อาศัย Stack ก็ได้ ซึ่งมีวิธีการดังนี้
1. เข้าวงเล็บนิพจน์ Infix ให้ครบตามลำดับการคำนวณ
2. ย้าย Operator ทั้งหมดไปแทนที่เครื่องหมายวงเล็บปิดที่สอดคล้องกับ Operator นั้น ตามลำดับ
3. ลบเครื่องหมายวงเล็บเปิดให้หมด จะได้นิพจน์ Postfix

การหาค่าผลลัพธ์จากนิพจน์ Postfix
การหาค่าทางคณิตศาสตร์จากนิพจน์ Postfix มีขั้นตอนใหญ่ ๆ 2 ขั้นตอน คือ
1. ถ้าเป็น Operand ให้ PUSH ลงสู่สแตก
2. ถ้าเป็น Operator ให้ POP ค่า 2 ค่า จากสแตก แล้วดำเนินการโดยใช้ Operator ตัวนั้น ในการนี้ให้ใช้ค่าแรกที่ได้จากสแตกเป็น Operand ตัวที่ 2 จากนั้นก็เก็บค่าผลลัพธ์ในสแตก

ตัวอย่างของการแปลงหาค่านิพจน์ Postfix
นิพจน์ Postfix : 1 6 3 / 4 * + 7 –

INPUT	CALCULATE	STACK
1		1
6		1  6
3		1  6  3
/	6 / 3	1  2
4		1  2  4
*	2  *  4	1  8
+	1  +  8	9
7		9  7
-	9  -  7	2

 ผลลัพธ์ที่ได้ คือ : 2   

          

สรุปขั้นตอนในการหาผลลัพธ์ของนิพจน์ Postfix
1. ค้นหาเครื่องหมายดำเนินการทางซ้ายสุด ของนิพจน์
2. เลือกตัวถูกดำเนินการ 2 ตัว ที่อยู่ติดกับเครื่องหมายดำเนินการทางซ้าย
3. ประมวลผลตามเครื่องหมายดำเนินการนั้น
4. แทนที่เครื่องหมายดำเนินการและตัวถูกดำเนินการ ด้วยผลลัพธ์ที่ได้
5. รีเคอร์ซีฟโปรแกรมมิ่ง

               สแตกนอกจากจะใช้จัดการกับการเรียกใช้โปรแกรมย่อยแล้ว ในบางภาษายังใช้จัดการกับการรีเคอร์ชั่น (recursion) หรือการเรียกใช้ตัวเอง
              ในการเขียนโปรแกรมที่ต้องทำซ้ำซ้อน สามารถทำได้โดยการใช้หลักการทำซ้ำซ้อนด้วย LOOP การเขียนโปรแกรมแบบนี้เรียกว่า โปรแกรมวนซ้ำ (iterative) และแบบรีเคอร์ซีฟ (recursive) คือกระบวนการที่ฟังก์ชั่นหรือโปรแกรมเรียกตัวเองซ้ำๆ จนกว่าจะถึงเงื่อนไขที่กำหนด ซึ่งจะใช้การประมวลผลแบบนี้กับการคำนวณ ที่แต่ละขั้นตอนอยู่ในรูปของผลลัพธ์ที่ได้จากขั้นตอนก่อนหน้า ปัญหาที่ต้องทำซ้ำ ส่วนมากจะเขียนในรูปแบบนี้ได้ เบื้องหลังการโปรแกรมแบบรีเคอร์ซีฟคือ หลักการที่เรียกว่า รีเคอร์ชั่น (recursion) ซึ่งหมายถึงการนิยามปัญหาหรือนิยามสูตรคณิตศาสตร์ของสิ่งหนึ่งโดยใช้ตัวมันเอง ตัวอย่างที่ใช้บ่อยคือ การหาค่าแฟกทอเรียล

ฟังก์ชั่นแฟกทอเรียล
ผลคูณของเลขจำนวนเต็ม 1 ถึง n เรียกว่า n แฟกทอเรียล สามารถแสดงโดย n!

n!  =  1 * 2 * 3 …. (n-2) * (n-1) * n

                เพื่อความสะดวก กำหนด 0! = 1 ดังนั้น ฟังก์ชั่นจะไม่มีค่าเป็นลบ ซึ่งเราจะได้

                0!  =    1                                                 1!    =     1                                                          2!   =   1 * 2  =   2

                3!  =    1 * 2 * 3   =   6                           4!    =     1 * 2 * 3 * 4   =   24

                5!  =   1 * 2 * 3 * 4 * 5   =   120             6!    =     1 * 2 * 3 * 4 * 5   =   720                      และต่อ ๆ ไป

สังเกต

5!    =    5 * 4!      =      5 * 24     =     120

          และ

6!    =    6 * 5!      =    6 * 120     =    720

         นั่นคือ ทุก ๆ ค่าของ n ที่เป็นบวกจะได้

n!  =  n * (n – 1)!

                ดังนั้นฟังก์ชั่นแฟกทอเรียลจะกำหนดได้ดังนี้

                   (a)      if  n  =  0   then   n! = 1

                   (b)      if  n  >  0   then   n!  =  n (n – 1)!

       

สังเกตว่านิยามนี้ n! เป็นรีเคอร์ซีฟ เนื่องจากมีการเรียกใช้ตัวเอง เมื่อใช้ (n – 1)! แต่อย่างไรก็ตาม
ตัวอย่าง จงหาค่า 4!
ในกรณีที่ใช้วิธีการแก้ปัญหาแบบการวนซ้ำ ก็คือ

4!  =  4 * 3 * 2 * 1   =   24

                ในกรณีที่ใช้วิธีการแก้ปัญหาแบบรีเคอร์ชั่น ก็คือ

                         1.      4!      =       4 * 3!                  

                         2.               3!      =       3 * 2!

                         3.                         2!      =       2 * 1!                  

                         4.                                  1!      =       1 * 0!

                         5.                                            0!      =    1

                         6.                                  1!    =    1 * 1   =   1

                         7.                         2!    =    2 * 1   =   2

                         8.               3!    =    3 * 2   =   6

                         9.      4!    =    4 * 6   =   24

                Step 1    การหาค่าของ  4!  ทำได้โดยนำ  4 * 3!  ซึ่งเราจะยังไม่หาค่าของ  4!  จนกว่าจะทราบค่าของ  3!

                Step 2    การหาค่าของ  3!  ทำได้โดยนำ  3 * 2!  ซึ่งเราจะยังไม่หาค่าของ  3!  จนกว่าจะทราบค่าของ  2!

                Step 3    การหาค่าของ  2!  ทำได้โดยนำ  2 * 1!  ซึ่งเราจะยังไม่หาค่าของ  2!  จนกว่าจะทราบค่าของ  1!

                Step 4    การหาค่าของ  1!  ทำได้โดยนำ  1 * 0!  ซึ่งเราจะยังไม่หาค่าของ  1!  จนกว่าจะทราบค่าของ  0!

                Step 5    จากนิยาม  ค่าของ 0!  เท่ากับ  1 

                Step 6    เป็นการทำกลับโดยนำค่า 0! ซึ่งเท่ากับ 1 ไปแทนในการหาค่า  1!  จะได้ค่า  1!  =  1 * 1  =  1

                Step 7    เป็นการทำกลับโดยนำค่า 1! ซึ่งเท่ากับ 1 ไปแทนในการหาค่า  2!  จะได้ค่า  2!  =  2 * 1  =  2

                Step 8    เป็นการทำกลับโดยนำค่า 2! ซึ่งเท่ากับ 2 ไปแทนในการหาค่า  3!  จะได้ค่า  3!  =  3 * 2  =  6

                Step 9    เป็นการทำกลับโดยนำค่า 3! ซึ่งเท่ากับ 6 ไปแทนในการหาค่า  4!  จะได้ค่า  4!  =  4 * 6  =  24

ถ้าให้ FACT (n) แทนฟังก์ชันที่ใช้คำนวณหาแฟกทอเรียลของ n จะเขียนได้ว่า

FACT (n) = n * FACT (n – 1)

ถ้าต้องการหา FACT (4) จะต้องผ่านการคำนวณ ดังนี้

FACT (4)  =  4 * FACT (3)

FACT (3)  =  3 * FACT (2)

FACT (2)  =  2 * FACT (1)

FACT (1)  =  1 * FACT (0)

                รูปข้างล่างแสดงสแตกช่วยในการหา n! เมื่อ n = 4 โดยที่สแตกเก็บค่า n และ FACT(n-1) ไว้ในแต่ละครั้งที่มีการหาค่า FACT (n) ใด ๆ เนื่องจากในแต่ละขั้นยังไม่สามารถคำนวณได้ จนกว่าจะได้ค่า FACT (0) จึงต้อง PUSH ค่า n และ FACT (n – 1) ไว้ในสแตก เมื่อถึงจุดที่หาค่า FACT (0) ซึ่งมีค่าเป็น 1

									1!	1	FACT (0)
						2!	2	FACT (1)	2!	2	FACT (1)
			3!	3	FACT (2)	3!	3	FACT (2)	3!	3	FACT (2)
4!	4	FACT (3)	4!	4	FACT (3)	4!	4	FACT (3)	4!	4	FACT (3)

               เมื่อหาค่า FACT (0) ได้แล้ว ก็ให้ POP ข้อมูลที่จะนำไปใช้ออกจากสแตก

2!	2	1
3!	3	FACT (2)	3!	3	2
4!	4	FACT (3)	4!	4	FACT (3)	4!	4	6

แบบทดสอบ

1.โครงสร้างข้อมูลแบบสแตกจะแบ่งออกเป็น กี่ส่วน *

•  ก.1 ส่วน คือ ตัวชี้สแตก ( Stack Pointer )
•  ข.2 ส่วน คือ ตัวชี้สแตก ( Stack Pointer )และสมาชิกของสแตก ( Stack Element )
•  ค.3ส่วน คือ ตัวชี้สแตก ,ตัวรับค่า ,ตัวเก็บค่า
•  ง.4ส่วน คือ ตัวชี้สแตก ,ตัวรับค่า ,ตัวเก็บค่า และตัว output

2. “ CreateStack( ) “ มีความจำเป็นเป็นอย่างไรสำหรับสแต็ก *

•  ก. ใช้สร้างแสต็กขึ้นมาใช้งานใหม่
•  ข.เพิ่มค่าใหม่ของแสต็ก
•  ค.ใช้ทับค่าเดิมเข้าไปแทนที่
•  ง.ใช้สำหรับการตรวจสอบสแต็ก

3. ปัญหาของสแตกมีกี่ข้อ *

•  ก. 1 ข้อ
•  ข. 2 ข้อ
•  ค. 3 ข้อ
•  ง. 4 ข้อ

4. โครงสร้างสแตกข้อมูลที่รู้จักและนำมาใช้งานชนิดหนึ่ง และมีข้อกำหนดให้ชุดปฏิบัติการ สามารถเพิ่มและ ลบข้อมูลได้กี่ด้าน และจะต้องลบข้อมูล ด้านใด *

•  ก. 3 ด้าน คือ ด้าน ขวา
•  ข. 4 ด่าน คือด้าน ล่าง
•  ค. ด้านเดียว คือด้าน บน
•  ง. 2 ด้าน คือด้าน ซ้าย

5. สแตก (Stack) มีลักษณะเป็นอย่างไร *

•  ก. เป็นเชิงเส้น
•  ข. เป็นเชิงเดี่ยว
•  ค. เป็นสี่เหลี่ยม
•  ง. เป็นวงกลม1

6. การทำงานของสแตกเมื่อมีค่าใดส่งเข้ามาเป็นตัวสุดท้ายจะอยู่ที่ตำแหน่งใด*

•  ก.ล่างสุด
•  ข.บนสุด
•  ค.ตรงกลาง
•  ง.ด้างข้าง

7. Push(value, stack) คืออะไร *

•  ก.ใช้เพิ่มค่าใหม่เก็บลงในสแตกที่ใช้งานอยู่
•  ข.ใช้สร้างสแตกใหม่
•  ค.ใช้เลดค่าในสแตกที่ใช้งานอยู่
•  ง. ถูกทุกข้อ

8. จงแปลง 26 จากฐาน 10ไปเป็นฐาน 2 เท่ากับเท่าไร *

•  ก. 11100
•  ข. 01010
•  ค. 10100
•  ง. 11010

9. ด้านบนสุดของสแตก เรียกว่า? *

•  ก.Stack
•  ข.Linear List
•  ค.Stack Pointer
•  ง.Top of Stack

10. สแตกมีลักษณะคล้ายกับอะไรมากที่สุด *

•  ก.ที่วางจาน หรือถาดในร้านอาหาร
•  ข. ลานจอดรถ
•  ค.ชั้นวางของ
•  ง. ขั้นบันได