วันพุธที่ 9 มีนาคม พ.ศ. 2559

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

ความหมายของข้อมูล

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

โครงสร้างข้อมูล

    1.โครงสร้างข้อมูล (data structures) เกิดจากคำสองคำ คือ โครงสร้าง และ ข้อมูล
      2.โครงสร้าง เป็นความสัมพันธ์ระหว่างสมาชิกในกลุ่ม
      3.โครงสร้างข้อมูล หมายถึง ความสัมพันธ์ระหว่างข้อมูลที่อยู่ในโครงสร้างนั้น

ขั้นตอนการพัฒนาโปรแกรม(steps in Program Development )

มี 7 ขั้นตอน ประกอบด้วย
1.1 กำหนดปัญหา(Define the Problem)
1.2 ร่างรายละเอียดแนวทางการแก้ไขปัญหา(Outline the Solution)
1.3 พัฒนาอัลกอลิทึม(Develop and Algorithm)
1.4 ตรวจสอบความถูกต้องของอัลกอริทึม(Test the  Algorithm for Correctness)
1.5 เขียนโปรแกรม(Proramming)
1.6 ทดสอบโปรแกรม(Testing)
1.7 จัดทำเอกสารและบำรุงรักษาโปรแกรม(Document and Maintain the Program)
1.1 กำหนดปัญหา(Define the Problem) ประกอบด้วย
-Input
-Outputs
-Processing
1.2 ร่างรายละเอียดแนวทางการแก้ไขปัญหา(Outline the Solution)
 -แตกงานให้เป็นช้นย่อยๆหรือเป็นขั้นเป็นตอน(หลังจากกำหนดปัญหา)
          -การร่างรายละเอียดแนวทางการแก้ไขปัญหาต่างๆประกอบด้วย

          -ขั้นตอนการประเมณผลส่วนหลักๆ
         
          -ส่วนหลักของงานที่ได้มีการแตกย่อย(Subtask)
          
          -ส่วนความสัมพันธ์กับผู้ใช้งาน
          
          -โครงสร้างที่ใช้ควบคุม เช่น การวนซ้ำ หรือการกำหนดทางเลือก
         
          -ตัวแปรและโครงสร้างของเรคอร์ด
          
          -ตรรกะโปรแกรม(Logic) 
1.3 พัฒนาอัลกอลิทึม(Develop and Algorithm)
-ขั้นตอนที่ใช้อธิบายลำดับการทำงาน และหากได้ปฏิบัติตามขั้นตอนของอัลกิริทึมที่ออกมา
         -ซูโดโค้ดเป็นตัวแทนอัลกอริทึมเพื่อใช้แก้ไขปัญาหาทางคอมพิวเตอร์ 

1.4 ตรวจสอบความถูกต้องของอัลกอริทึม(Test the  Algorithm for Correctness) เป็นขั้นตอนที่สำคัญที่สุด

          ตรวจสอบทั้งตรรกะของอัลกอริทึม

          ขั้นตอน ตัวแปรหลักและการนำข้อมูลทดสอบเข้าไปประมวลผลในแต่ละ

1.5 เขียนโปรแกรม(Proramming)
-นำอัลกอริทึมที่ได้รับการออกแบบอย่างสมบูรณ์มาพัฒนาด้วยการเขียนโปรแกรม(ชุดคำสั่ง)
         -เลือกใช้ภาษาระดับสูงเพื่อใช้เขียนโปรแกรม เช่น c,PASCAL เป็นต้น

1.6 ทดสอบโปรแกรม(Testing)
 -นำข้อมูลป้อนเข้าไปเพื่อทดสอบบนเครื่องกับโปรแกรมที่ได้เขียนขึ้นว่าถูกต้องหรือไม่
          -การตรวจสอบ
 -รูปแบบชุดคำสั่ง(Syntax Errors)
 -โปรแกรม(Logic Errors)
1.7 จัดทำเอกสารและบำรุงรักษาโปรแกรม(Document and Maintain the Program)

         การจัดทำเอกสารประกอบโปรแกรมจะต้องจัดทำขึ้นตั้งแต่ขั้นตอน การกำหนดปัญหาจนถึงขั้นตอน

สุดท้าย คือการทดสอบผลลัพธ์
        เอกสารประกอบโปรแกรมประกอบด้วย
            
     เอกสารภายนอก(External document) เช่น ผังโครงสร้างอัลกอริทึมที่ใช้แก้ปัญหาและผลของการทดสอบข้อมูล
              
 เอกสารภายใน(Internal document) คือ ชุดคำสั่งในโปรมแกรม

          การบำรุงรักษาโปรแกรมจะเกี่ยวข้องกับการดูแลและปรับปรุงโปรแกรม

ข้อมูลและรูปแบบของข้อมูล
       ข้อมูลชนิดจำนวนเต็ม (integer)
        ข้อมูลชนิดจำนวนจริง (real หรือ floating point)
        ข้อมูลชนิดตัวอักขระ (character)

     

โครงสร้างข้อมูลในภาษาคอมพิวเตอร์

      แบ่งเป็น 2 ประเภท คือ

1.โครงสร้างข้อมูลทางกายภาพ (physical data structures)
2.โครงสร้างข้อมูลทางตรรกะ  (logical data structures)

โครงสร้างข้อมูลทางกายภาพ
    เป็นโครงสร้างข้อมูลทั่วไปที่มีใช้ในภาษาคอมพิวเตอร์ ซึ่งแบ่งออกเป็น 2 ประเภทตาม
ลักษณะข้อมูล ดังนี้
   1. ข้อมูลเบื้องต้น (primitive data types)

   2. ข้อมูลโครงสร้าง (structured data types)

      โครงสร้างข้อมูลทางตรรกะ
     เป็นโครงสร้างข้อมูลที่เกิดจากจินตนาการของผู้ใช้เพื่อใช้แก้ปัญหาในโปรแกรมที่สร้าง
ขึ้น จำแนกได้เป็น 2 ประเภท ดังนี้
   1. โครงสร้างข้อมูลแบบเชิงเส้น (linear data structures)
   2. โครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น (non-linear data structures)

โครงสร้างข้อมูลที่ทางกายภาพ

เป็นโครงสร้างข้อมูลที่ใช้โดยทั่วไปในภาษาคอมพิวเตอร์ แบ่งออกเป็น 2 ประเภท ตามลักษณะข้อมูล คือ
1. ชนิดข้อมูลพื้นฐาน (Primitive Data Type) ใช้เก็บค่าพื้นฐานต่าง ๆ เช่น เลขจำนวนเต็ม เลขทศนิยม อักขระ และ ข้อมูลตรรกกะ 
2 ข้อมูลโครงสร้าง (Structured Data Types) ได้แก่ แถวลำดับ ระเบียนข้อมูล และ แฟ้มข้อมูล
โครงสร้างข้อมูลทางครรกะ( Logical Data Structure) 

จะมีลักษณะเป็นข้อมูลเชิงจำนวน และได้มีการประมวลมาแล้ว
1.ข้อมูลแบบเชิงเส้น บอกความสัมพันธ์ บอกความเกี่ยวโยง ได้แก่ ลิสต์ แสตก คิว สตริง
2 .ข้อมูลแบบไม่เชิงเส้น ได้แก่ ทรี กราฟ

โครงสร้างข้อมูลทางครรกะ


ขั้นตอนวิธี Algorithm

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


วิธีการเขียนอัลกอริทึม
1.ภาษาเขียน คือ การบรรยายเป็นย่อหน้าหรือเป็นข้อๆด้วยภาษาไทยหรือภาษาอังกฤษก็ได้


การเขียนผังงาน  มี 3 แบบ 
1. ผังงานแบบเรียงลำดับ  (Sequemce Flowchart) 
เป็นการเขียนผังงานแบบง่ายที่สุด ทำงานจากบนลงล่าง ตามลูกศร
2. ผังงานแบบมีทางเลือกหรือแบบมีเงื่อนไข   (Selectiom or Condition
 Flowchart)  
คือตรวจสอบเงื่อนไขถ้าเป็นจริง ก็ทำงานตามเงื่อนไขที่เป็นจริง ถ้าเป็นเท็จก็ทำตาม
เงื่อนไขที่เป็นเท็จ
กรณี 1 ทางเลือก
กรณีที่ 2 แบบ 2 ทางเลือก แล้วแต่ผู้ใช้ว่าถ้าเป็นจริงทำตามเงื่อนไข ถ้าเป็นเท็จจะ
ทำงานหรือไม่

3. ผังงานแบบการทำงานแบบวนซ้ำ  (Repetiton or Loop Flowchart) 

รหัสจำลองที่เรียกว่า การเขียนซูโดโค้ด (Pseudo Code) 
     คือการเขียนคำอธิบายขั้นตอนการทำงานของโปรแกรมโดยใช้ถ้อยคำผสมระหว่าง
ภาษาอังกฤษและภาษาการเขียนโปรแกรมแบบโครงสร้างซึ่งจะช่วยให้ผู้เขียน
โปรแกรมสามารถพัฒนาขั้นตอนต่าง ๆ  ให้เป็นโปรแกรมได้ง่ายขึ้น  ส่วนใหญ่มักใช้คำ
เฉพาะ  (Reserve Word)ที่มีในภาษาการเขียนโปรแกรมและมักเขียนด้วยตัวอักษรตัว
ใหญ่  ซูโดโค้ดที่ดี  จะต้องมีความชัดเจน  สั้น  และได้ใจความ  ข้อมูลต่าง ๆ  ที่ใช้จะ
ถูกเขียนอยู่ในรูปของตัวแปร

                                บทที่ 2 อาร์เรย  (Array ) 

อาร์เรย์ (Array) 

          คือ  การรวมกลุ่มของตัวแปรที่สามารถใช้ตัวแปรชื่อเดียวแทนสมาชิกได้หลายๆตัวในคราวเดียวกัน  ด้วยการใช้อเลขดรรชนี (Index) หรือชับสคริปต์ (Subscrip) เป็นตัวอ้างอิงตำแหน่งสมาชิกบนตัวแปรนั้นๆ

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

 คุณสมบัติสำคัญของอาร์เรย์มีดังนี้

             1. อาร์เรย์เป็นตัวแทนกลุ่มข้อมูลที่มีความสัมพันธ์กัน 
             2. สมาชิกในอาร์เรย์จะมีคุณสมบัติเหมือนๆกัน  กล่าวคือต้องมีชนิดข้อมูลเหมือนกันทั้งหมด
             3. ขนาดของอาร์เรย์จะมีขนาดดคงที่เมื่อได้ถูกสร้างขึ้น
             4. อาร์เรย์เป็นข้อมูลที่ผู้ใช้สามารถอ้างอิงเพื่อเข้าถึงข้อมูลที่ต้องการได้ทันที
            

           การอ้างอิงตำแหน่งสมาชิกในอาร์เรย์

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

            การจัดเก็บอาร์เรย์ในหน่วยความจำ

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

              การจัดเก็บข้อมูลใน อาร์เรย์ มี 3 แบบคือ


              อาร์เรย์ 1 มิติ (One-Dimension Array)


   คือ อะเรย์ที่มีเพียง 1 แถวนอน แต่มี แถวตั้งหลายแถว ซึ่งในการระบุตำแหน่งหรือตัวชี้(index) จะมีแต่ระบุแต่ตำแหน่งของแถวตั้งเท่านั้น โดยนับเริ่มจาก 0
               Array Name   คือ ชื่อของอาร์เรย์

               L   คือขอบเขตล่างสุด (Lower Bound)       
 
               U   คือขอบเขตบนสุด (Upper Bound)

                          LOC ( a [ i ] )  =  B + w ( i – L )

               LOC ( a [ i ] )   = ตำแหน่งแอดเดรสที่เก็บ a[i] ในหน่วยความจำ

                B    = แอสเดรสเริ่มต้นของ a 

                w    = จำนวนช่องของหน่วยความจำที่จัดเก็บข้อมูลต่อหนึ่งสมาชิก

                 ตัวอย่างเช่น ขนาดหน่วยความจำที่ใช้เก็บข้อมูลสมาชิก 1 ตัวของแต่ละช่องเท่ากับ 4 ไบต์ (32 บิต) 

ดังนั้น กำหนดให้

                  กำหนดให้ : แอดเดรสเริ่มต้น (Base Address) = 1000

                                                              W      = 1

                อยากทราบว่าอาร์เรย์ a[10] ถูกจัดเก็บไว้ในหน่วยความจำแอดเดรสใด ก็สามารถ

คำนวณได้จากสูตรดังต่อไปนี้

                LOC (a[i]     = B + w(i – L)

                LOC (a[10] = 1000 + 1(10 – 0)

                                    = 1010

                 ดังนั้นตำแหน่งอาร์เรย์ a[10] จะถูกเก็บไว้ในหน่วยความจำแอดเดรสที่ 1010 นั่นเอง
                   
          รูปที่1  แสดงอาร์เรย์  number ที่จัดเก็บอยู่ภายในหน่วยความจำคอมพิวเตอร์

                  อาร์เรย์สองมิติ (Two  Dimension  Array) 
                  
                   อาร์เรย์สองมิติจะมีรูปแบบตารางที่ประกอบด้วยแถว (Row) และคอลัมม์ (Column) การอ้าองอิง

อาร์เรย์สองมิติจึงต้องระบุบแนวแถวและคอลัมม์  สำหรับรูปแบบทั่วไปของโครงสร้างข้อมูลอาร์เรย์สองมิติ  คือ

                                                   ArrayName [L1 : U1 , L2 : U2]       
            
                    โดยที่  ArrayName  คือชื่อของอาร์เรย์

                    L1   คือขอบเขตล่างสุด  (Lower Bound)  ของแถว

                   U1  คือขอบเขตบนสุด  (Upper Bound)   ของแถว

                   L2   คือขอบเขตล่างสุด  (Lower Bound)  ของคอลัมน์

                  U2  คือขอบเขตบนสุด  (Upper Bound)   ของคอลัมน์

                 โดยสมมติว่าได้มีการกำหนดให้ K[4,3] หรือ K[0:3,0:2] ด้วยภาษา C ดังนี้

                  int K[4] [3];

                ซึ่งแสดงได้ดังรูป

                        
                 รูปที่ 2  รูปแสดงอาร์เรย์สองมิติชื่อ K ที่มีขนาดมิติ 4 x 3

          อย่างไรก็ตาม การจัดเก็บอาร์เรย์สองมิติในหน่วยความจำยังสามารถจัดเก็บได้ 2 วิธี 
ด้วยกันคือ
  1. การจัดเก็บด้วยการเรียงแถวเป็นหลัก (Row Major Order)
  2. การจัดเก็บด้วยการเรียงคอลัมน์เป็นหลัก (Column Major Order)
                ในกรณีการจัดเก็บอาร์เรย์สองมิติในหน่วยความจำด้วยการเรียงแถวเป็นหลัก การจัด 
เรียงจะเริ่มต้นตั้งแต่แถวแรกและเรียงลำดับต่อไปในแต่ละคอลัมน์จนครบ จากนั้นก็ขึ้นแถวใหม่ 
ไปเรื่อยๆ จนกระทั่งแถวสุดท้าย


       


                  รูปที่ 3 ข้อมูลของอาร์เรย์สองมิติชื่อ K ที่จัดเก็บอยู่ในหน่วยความจำหลักในรูปแบบเรียงแถวเป็นหลัก (Row Major Order)

                อาร์เรย์สามมิติ(Three Dimension Array) 

               หากพิจารณาให้ดี จะเห็นว่าอาร์เรย์ สามมิตินั้นก็คือการนำอาร์เรย์สองมิติมาเรียงซ้อนกันหลายๆ 

ชั้น (Page) ทำให้อาร์เรย์สามมิติ  นอกจากจะมีแถวและคอลัมน์แล้วก็จะมีความลึกเพิ่มขึ้นอีก ซึ่งความลึกนี้เอง

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

               ArrayName [L1 : U1 , L2 : U2 , L3 : U3]    
                                            
              โดยที่  ArrayName  คือชื่อของอาร์เรย์

              L1     คือขอบเขตล่างสุด  (Lower Bound)  ของชั้น

             U1      คือขอบเขตบนสุด  (Upper Bound)   ของชั้น

             L2      คือขอบเขตล่างสุด  (Lower Bound)  ของแถว

             U2     คือขอบเขตบนสุด  (Upper Bound)   ของแถว

             L3      คือขอบเขตล่างสุด  (Lower Bound)  ของคอลัมน์

             U3     คือขอบเขตบนสุด  (Upper Bound)   ของคอลัมน์

           โดยสมมติว่าได้มีการกำหนดให้ S[3,4,5] หรือ S[0:2, 0:3, 0:4] ด้วยภาษา C ดังนี้

           Int S [3] [4] [5] ;

          ในการอ้างสมาชิกแต่ละตัวบนแถวลำดับสามมิติสามารถกำหนดให้เป็นไปดังนี้คือ

          S [0, 0, 0], S [0, 0 1], S [i, j, k], … , S [2, 3, 4]

          การจัดเก็บอาร์เรย์สามมิติในหน่วยความจำ จะเป็นในลักษณะเช่นเดียวกันกับที่ผ่านมา 

คือเรียงลำดับเป็นแนวเดียว อีกทั้งยังสามารถจัดเก็บด้วยการเรียงแถวเป็นหลัก หรือคอลัมน์เป็นหลัก 

เช่นเดียวกับอาร์เรย์สองมิติที่ผ่านมา และต่อไปนี้คือสูตรการคำนวณหาแอดเดรสของอาร์เรย์สามมิติ

แบบแถวเป็นหลัก
    
            LOC (S[i, j, k] ) = B + [w X R X C (i-L1) ]  + [w X C (j-L2) ]  + [w(k- L3) ]

            และจากรูป คืออาร์เรย์สามมิติชื่อ S ที่จัดเก็บภายในหน่วยความจำในรูปแบบแถวเป็น

หลักในที่นี้ต้องการทราบตำแหน่งแอดเดรสที่เก็บข้อมูลอาร์เรย์ S ชั้นที่ 0 แถวที่ 3 คอลัมน์ 4

จากรูปแบบของอาร์เรย์สามมิติ         S[L1 : U1 , L2 : U2 , L3 :U3]

ได้มีการประกาศอาร์เรย์ด้วยภาษา C ดังนี้  S [3] [4] [5]

ผลที่ได้ อาร์เรย์ K จะมีขอบเขตระหว่าง     K [0:2, 0:3, 0:4]

LOC (S[i, j, k] )    = B + [w X R X C (i-L1) ]+ [w X C (j-L2) ]+ [w(k- L3) ]

LOC (S[0, 3, 4] ) = 500 + [4 X 4 X 5 (0-0) ]+ [4 X 5 (3-0) ]+ [4(4- 0) ]

                             = 500 + 0 + 60 +16

                             = 576


ดังนั้นอาร์เรย์ S ชั้นที่ 0 แถวที่ 3 คอลัมน์ 4 จะจัดเก็บอยู่ในตำแหน่งแอดเดรสที่ 576
                   

                      บทที่ 3  ลิงก์ลิสต์ (Linked Lists)


          

ลิงลิสต์ (Linked  List)

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

        ในส่วนของข้อมูลจะมีการจัดเก็บสารสนเทศที่สามารถนำไปใช้ในการประมวลผลตามที่ต้อง

การต่อไป

         ลิงค์ (Link)

         ในส่วนของลิสต์นั้น จะใช้สำหรับเชื่อมโยงไปยังข้อมูลโดยเริ่มต้นจากเฮดพอยน์เตอร์ที่ชี้ไป 

ยังตำแหน่งโหนดแรกของลิสต์ จากนั้นลิงก์ในแต่ละโหนดก็จะเชื่อมโยงไปยังโหนดตัวถัดไปเรื่อยๆ

ส่วนชื่อของลิสต์จะเป็นชื่อเดียวกันกับชื่อตัวแปรพอยน์เตอร์โดยลิงก์ลิสต์อย่างง่ายที่จะกล่าวถึงต่อ

ไปนี้คือ ซิงเกิลลิงก์ลิสต์ (Single-Linked List) ซึ่งจะมีเพียงลิงก์เดียวที่ใช้เชื่อมโยงไปยังโหนด

ตัวถัดไป
 ตัวอย่างการแทนลิงก์ลิสต์ในหน่วยความจำ

โครงสร้างข้อมูลแบบลิงก์ลิสต์ (Linked List Data Structure)
                 สำหรับโครงสร้างข้อมูลลิงก์ลิสต์ ประกอบด้วย
 โครงสร้างโหนดส่วนหัว (Head Node Structure)
            ภายในโหนดส่วนหัวจะมีเพียงหนึ่งพอยน์เตอร์ที่จะชี้ไปยังลิสต์ คือ เฮดพอยน์เตอร์ ภายใน
โครงสร้างส่วนนี้จะมี Metadata ที่เอาไว้อธิบายข้อมูลภายในลิสต์ ภายในนี้คือฟิลด์ Count เพื่อ
เอาไว้บอกว่าในลิสต์นี้มีจำนวนสมาชิกทั้งหมดเท่าไร ซึ่งสามารถเพิ่มหรือลดลงได้ หากมีการแข้
ไขข้อมูลในลิสต์
โครงสร้างโหนดข้อมูล (Data  Node Structure)
             โครงสร้างโหนดข้อมูลประกอบด้วยส่วนข้อมูลและลิงก์ สำหรับข้อมูล (Data type) ของ
ลิสต์นั้นจะขึ้นอยู่กับการนำไปประยุกต์ใช้ แต่ปกติแล้ว ชนิดข้อมูลจะเป็นไปในลักษณะที่แสดงไว้ที่
ด้านล่างและที่สำคัญ ชนิดข้อมูลจะต้องได้รับการปรับปรุงรายละเอียดอยู่เสมอหลังจากถูกสร้างขึ้น
           ความจริงแล้วมีโครงสร้างข้อมูลอยู่หลายชนิดที่สามารถนำมาสร้างลิสต์ แต่หัวข้อต่อไปนี้จะขอ
              กล่าวถึงการสร้างลิสต์ด้วยลิงก์ลิสต์เป็นสำคัญ โดยสามารถสรุปคุณสมบัติของลิงก์ลิสต์ได้ดังนี้ คือ
1.ลิงก์ลิสต์จะใช้เฮดพอยน์เตอร์ (pHead) เป็นตัวชี้ไปยังโหนดแรกของลิสต์ ในขณะที่พอยน์
เตอร์หรือลิงก์ของแต่ละโหนดก็จะเชื่อมโยงลิงก์ไปยังโหนดตัวถัดไป โดยโหนดตัวสุดท้ายที่ไม่
มีลิงก์ให้เชื่อมต่อจะถูกกำหนดค่าให้เป็น null ซึ่งในที่นี้ใช้สัญลักษณ์   S  แทน

2. โหนดข้อมูลจะประกอบด้วย Data และ Link โดยที่

- Data คือข้อมูลหรือสารสนเทศที่สามารถนำไปใช้ประโยชน์
- Link คือตัวชี้หรือพอยน์เตอร์ที่ใช้สำหรับเชื่อมโยงไปยังโหนดถัดไป

3. ไม่มีความสัมพันธ์ทางกายภาพระหว่างโหนด

4. ข้อมูลที่จัดเก็บภายในหน่วยความจำไม่จำเป็นต้องอยู่ติดกัน

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

ข้อดีของลิงก์ลิสต์
1.เป็นโครงสร้างที่ง่ายต่อการเพิ่มหรือลบข้อมูล

2.ไม่จำเป็นต้องขยับอิลิเมนต์ของลิสต์ไปข้างหน้าเพื่อให้เกิดพื้นที่ว่าง ในกรณีที่มีการลบอิลิเมนต์
    ตรงส่วนหน้าหรือส่วนกลางของลิสต์เช่นเดียวกับอาร์เรย์

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

 การสร้างลิสต์ (Create List)
                ฟังก์ชัน Create List เป็นการกำหนดโครงสร้างโหนดส่วนหัวและกำหนดค่าเริ่มต้น 
ให้   กับ metadata  สำหรับลิสต์โดยในที่นี้จะมี   metadata   อยู่  2  ตัวด้วยกัน  แต่ก็อาจขยาย 
เพิ่มเติมได้


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

                  1.จัดสรรหน่วยความจำสำหรับโหนดใหม่พร้อมกับข้อมูล 
                  2.กำหนดตัวชี้ให้กับลิงก์ฟิลด์ของโหนดใหม่ 
                  3.นำตัวชี้ที่อยู่ก่อนหน้าโหนดใหม่ชี้มายังโหนดใหม่ 
                 จาก 3 ขั้นตอนของการแทรกโหนดเข้าไปยังลิสต์ข้างต้น เป็นเพียงการนำเสนอขั้น 
ตอน ในรูปแบบอย่างง่ายเพื่อให้เกิดความเข้าใจในเบื้องต้นเท่านั้น แต่ความเป็นจริงยังมีรายละเอียด
         อีกหลายอย่าง
                 ในการแทรกโหนดเข้าไปในลิสต์นั้น ขั้นตอนแรกจำเป็นต้องรู้ตำแหน่งที่อยู่ของโหนด 
ก่อนหน้าโหนดใหม่ที่ต้องการจะแทรกเสียก่อน ซึ่งโหนดนี้จะระบุตัวชี้ที่เป็นไปได้ทั้ง 2 สถานะด้วย 
กันคือ อาจเป็นแอดเดรสของโหนดถัดไป หรือเป็นค่า null ก็ได้ การที่จำเป็นต้องรู้ตำแหน่งโหนด 
ก่อนหน้าก็เพราะว่าโหนดนี้จะมีลิงก์ที่ใช้สำหรับเชื่อมโยงไปยังโหนดถัดไป ซึ่งลิงก์ดังกล่าวนี้จะนำ 
มาแทนตำแหน่งลิงก์ของโหนดใหม่เพื่อชี้ไปยังโหนดข้างหลัง (Successor) ที่อยู่ถัดจากโหนด 
ใหม่นั่นเอง แต่กรณีดังกล่าวเป็นการประยุกต์ใช้กับการแทรกระหว่างโหนดภายในลิสต์ แต่ถ้าเป็น 
กรณีลิงก์ของโหนดก่อนหน้ามีค่าเป็นnull นั่นหมายความว่าเป็นการแทรกโหนดที่ท้ายลิสต์ในการ 
แทรกโหนดเพิ่มเข้าไปในลิสต์สามารถกระทำได้ 4 รูปแบบด้วยกันคือ 
              1. การแทรกโหนดในลิสต์ว่าง (Insert into Empty List) 
                   กรณีนี้เป็นการแทรกโหนดเพิ่มเข้าไปในลิสต์ในขณะที่ลิสต์ว่างเปล่าหรือไม่มีข้อมูล 
ใดๆ อยู่นั่นหมายถึงเป็นการแทรกสมาชิกตัวแรกเข้าไป ซึ่งขณะนั้นเฮดพอยน์เตอร์จะมีค่าเป็น  
null เนื่องจากเป็นลิสต์ว่าง หลังจากนั้นมีลิสต์ใหม่ที่ต้องการแทรกเพิ่มเข้ามา (pNew) 
(a) Before add
                  
                                                                       (b) After add

รูป แสดงการแทรกโหนดเมื่อลิสต์ภายในว่าง

           2 การแทรกโหนดที่ตำแหน่งแรก (Insert at Beginning) 
               เป็นการแทรกโหนดเข้าไปไว้ในตำแหน่งโหนดแรก ซึ่งทำให้โหนดที่เคยอยู่ลำดับแรก 
เดิมต้องมาต่อท้ายโหนดใหม่ที่แทรกเข้าไป ขั้นตอนแรกของการแทรกข้อมูลที่โหนดแรกของลิสต์  
จะต้องทราบถึงตัวชี้ของตัว Predecessor ก่อน ซึ่งหากไม่มี หรือมีค่าเป็น nullก็หมายความว่า 
เป็นการแทรกโหนดแรกในลิสต์ว่างเปล่า
                               การแทรกโหนดที่ลำดับแรกจะมีวิธีการคือ ให้นำตัวชี้ของโหนดใหม่ชี้ไปยังโหนดแรก

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

           เดรสของโหนดใหม่อยู่แล้วหลังจากที่ได้สร้างขึ้นมา

                                                                     (a) Before add
                   
                                                           (b) After add

                     รูป  แสดงการแทรกโหนดไว้ที่ตำแหน่งแรกของลิสต์

        3 การแทรกโหนดที่กึ่งกลางของลิสต์ (Insert in Middle) 
            การเพิ่มโหนดในส่วนกลางของลิสต์หรือการแทรกระหว่างโหนด ในขั้นตอนแรก ต้องรู้ตำ 
แหน่งโหนดก่อนหน้าเสียก่อน ซึ่งก็คือตัว Predecessor (pPre) ความสำคัญของโหนด  
Predecessor ก็คือจะมีลิงก์ที่ใช้เชื่อมโยงไปยังโหนดถัดไป 
            ในการแทรกโหนดระหว่างสองโหนด ตัวชี้หรือลิงก์ฟิลด์ของโหนดใหม่จะชี้ไปยังโหนด  
Successor ในขณะที่ตัวชี้ pPre ก็จะชี้ไปยังโหนดใหม่ 

                                                   (a) Before add
                   
                                                       (b) After add 
รูป  แสดงแทรกโหนดที่กึ่งกลางของลิสต์

          4 การแทรกโหนดที่ท้ายลิสต์ (Insert at End) 
              เมื่อมีการเพิ่มโหนดที่ส่วนท้ายของลิสต์ เราต้องการเพียงแค่ตัวชี้ของ Predecessor  
เพื่อชี้ไปยังโหนดใหม่เท่านั้น ซึ่งในที่นี้จะไม่มีโหนด Successor เนื่องจากเป็นการแทรกที่ท้าย 
ลิสต์ดังนั้นลิงก์ฟิลด์ของโหนดใหม่จึงถูกกำหนดให้เป็นค่า null

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

a) Before add

            
(b) After add

รูป  การแทรกโหนดไว้ที่ส่วนท้ายของลิสต์ 

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


                  การลบโหนด (Delete Node) 
                  อัลกอริทึมการลบโหนดออกจากลิสต์นอกจากจะนำโหนดที่ถูกลบส่งคืนแก่หน่วยความ 
จำระบบเพื่อจะได้นำไปใช้งานอื่นต่อไปแล้ว ยังต้องมีการปรับเปลี่ยนตัวชี้ใหม่ด้วย สำหรับขั้นตอน 
แรกของการลบโหนด จะต้องค้นหาตำแหน่งของโหนดที่ต้องลบ (pLoc) ภายในลิสต์ให้พบก่อน 
เมื่อพบตำแหน่งโหนดที่ต้องการลบภายในลิสต์แล้ว จะทำให้ทราบตำแหน่งแอดเดรสของ 
Predecessor(pPre) ซึ่งก็คือโหนดที่อยู่ก่อนหน้าโหนดที่ต้องการลบนั่นเอง หลังจากนั้นก็จะ 
กำหนดลิงก์ฟิลด์ของโหนด Predecessorชี้ไปยังโหนด Successor ซึ่งเป็นโหนดที่อยู่ด้านหลัง 
โหนดที่ถูกลบ จากนั้นก็จะนำพื้นที่หน่วยความจำที่เก็บโหนดที่ถูกลบไปนั้นส่งคืนแก่ระบบเพื่อนำ 
ไป ใช้งานอื่นต่อไป
                 1.การลบโหนดที่ตำแหน่งแรก  (Delete First Node)

                  เมื่อรู้ตำแหน่งแรกแล้ว (pLoc) ต่อมาก็ให้ทำการรีเซตเฮดพอยน์เตอร์เพื่อชี้ไปยัง 
โหนดSuccessor ที่อยู่ถัดไปจากโหนดแรกที่ต้องการลบ จากนั้นก็จะนำโหนดที่ถูกลบส่งคืนแก่ 
ระบบ และเนื่องจากในที่เป็นการลบโหนดแรกออกจากลิสต์ ตัวโหนด Predecessor (pPre) ที่อยู่ 
ก่อนหน้านั้นจึงไม่มีดังนั้นโหนด pPre จึงถูกกำหนดค่าให้เป็น null ซึ่งก็หมายถึงเป็นการลบโหนด 
ที่ตำแหน่งแรกนั่นเอง

               2 การลบโหนดโดยทั่วไป  (General Delete Case) 
                การลบโหนดออกจากลิสต์ในกรณีทั่วไป ซึ่งประกอบด้วยการลบโหนดที่อยู่กึ่งกลางภาย 
ในลิสต์ และการลบโหนดที่ท้ายลิสต์ ทั้งสองกรณีต่างก็สามารถใช้ตรรกะเดียวกันในการใช้งานใน 
การลบโหนดลบโหนดออกจากลิสต์ ไม่ว่าจะเป็นโหนดที่อยู่กึ่งกลางลิสต์หรือที่ท้ายลิสต์ก็ตามขั้น 
ตอน แรกจำเป็นต้องรู้ตำแหน่งโหนดที่ลบเสียก่อน จากนั้นก็กำหนดตัวชี้ของโหนด Predecessor 
ให้ชี้ไปยังโหนดSuccessor ที่อยู่ถัดจากโหนดในตำแหน่ง pLoc หรือโหนดที่ต้องการลบนั่นเอง 
โดยแสดงขั้นตอนการกระทำได้ดังรูป

                                          (a) Before delete
      
                                               (b) After delete
รูป การลบโหนดออกจากลิสต์โดยทั่วไป
                      ส่วนกรณีการลบโหนดที่ท้ายลิสต์ออกเมื่อโหนดท้ายลิสต์ได้ถูกลบออกไปแล้ว 
ค่าของ null pointer จะถูกย้ายไปเก็บไว้ในตำแหน่งฟิลด์ของโหนด Predecessorดังนั้น 
โหนดที่เคยอยู่ก่อนหน้าก็จะกลายเป็นโหนดในลำดับสุดท้าย ส่วนโหนดท้ายลิสต์ที่ถูกลบไป 
ก็จะส่งคืนกลับไปยังระบบ

                      การค้นหาข้อมูลภายในลิสต์ (Search List)

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

                การแทรกโหนด  ที่จำเป็นต้องรู้ตำแหน่งตัว Predecessorหรือโหนดก่อนหน้าของ 
โหนดที่ต้องการจะแทรกก่อน

                การลบโหนดออกจากลิสต์  ขั้นแรกต้องค้นหาโหนดที่ต้องการลบให้พบก่อน แล้วจึง 
ค่อย กำหนดให้โหนด Predecessor ชี้ไปยังตำแหน่งโหนด Successor จากนั้นจึงปลดโหนดที่ 
ลบไปนั้นคืนแก่ระบบ

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

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

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

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

               จำนวนสมาชิกในลิสต์  (List  Count) ฟังก์ชัน List  Count ภายในโมดูลจะมีเพียง 
ประโยคคำสั่งเดียวเท่านั้น แต่ก็เป็นฟังก์ชันที่มีความสำคัญทีเดียว เพราะว่าจะแจ้งจำนวนสมาชิก
หรือจำนวนอิลิเมนต์ที่มีอยู่ในขณะนั้นให้กับโมดูลที่เรียก แทนที่จะต้องท่องเข้าไปในลิสต์เพื่อนับ 
สมาชิกแต่ละอิลิเมนต์แทน
บทที่ 4
โครงสร้างข้อมูลแบบสแตก

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

โครงสร้างข้อมูลแบบสแตก (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 ก็จะเสียไปไม่สามารถนำมาใช้ได้อีก

            7. หลังจากเสร็จสิ้นการประมวลผลของฟังก์ชั่น A (ตัวแปร S จะถูก pop ออกจากสแตก)
Reserved
By
System
Programs
And
procedures

D

D

D




P
Q
R
Operating
system
Low Memory
                        Top of heap
           
Top of stack

           


            8. หลังจากเสร็จสิ้นการประมวลผลของโปรแกรม main() (ตัวแปร P, Q, R จะถูก pop ออกจากสแตก)
Reserved
By
System
Programs
And
procedures

D

D

D





Operating
system
Low Memory
                        Top of heap
            
Top of stack

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
เมื่ออ่านอักขระหมดแล้ว แต่สแตกไม่เป็นสแตกว่างให้แสดงผล error

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
เขียนโดย ที่ ไม่มีความคิดเห็น:
สมัครสมาชิก: บทความ (Atom)