บทที่ 8 ทรี (Tree)

ทรี (Tree)

    โครงสร้างข้อมูลที่ออกแบบมาให้มีลักษณะไม่เป็นเชิงเส้น มีการจัดเก็บข้อมูลเชื่อมโยงกันเป็นระดับชั้น โดยเริ่มจากโหนดแรกที่อยู่บนสุดเรียกว่า Root Node เชื่อมโยงไปยังโหนดระดับรองลงไป แต่ละระดับก็มีการเชื่อมโยงโหนดระดับต่อไป ซึ่งเรียกว่า Subtree

  

    โครงสร้างข้อมูลแบบต้นไม้ มีคุณสมบัติดังนี้

   1. มีโหนดที่เรียกว่า รากหรือรูต (Root node) , R
   2. โหนดที่ไม่ใช่รูตแบ่งย่อยออกเป็น n กลุ่ม โดยที่แต่ละกลุ่มไม่มีโหนด ร่วมกันเลย  เช่น กลุ่ม T1 , T2 ,…..Tn (n >=0) แต่ละกลุ่มก็เป็นต้นไม้เหมือนกัน จะเรียกว่าต้นไม้ย่อย (Subtree)
     ลักษณะของทรี

    

        จากรูป

    R   เป็นรูทของต้นไม้ย่อย A,B,C,D

   A  เป็นรูทของต้นไม้ย่อย E,F,G

   F  เป็นรูทของต้นไม้ย่อย J

   B   เป็นรูทของต้นไม้ย่อย H และ I 

      

     ชื่อส่วนต่างๆของต้นไม้

      ระดับของโหนด (Level)

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

      ดีกรีของโหนด คือ จำนวนต้นไม้ย่อยของโหนดนั้น    

      โหนดที่เป็นใบ หมายถึง โหนดที่มีดีกรีเป็น 0 ส่วนโหนดที่มีดีกรีไม่เท่ากับ 0 เรียกว่า โหนดภายใน หรือ interior node  หรือ branch node

    Immediate Successor คือโหนดทั้งหลายของต้นไม้ย่อย i ที่มีค่าระดับต่ำกว่าโหนด i อยู่หนึ่ง 

   Immediate Predecessor คือโหนดที่มีค่าระดับสูงกว่าโหนด i อยู่หนึ่ง

      

     โครงสร้างต้นไม้ (Tree Structure)

    Level แสดงถึงหน่วยระยะทางตามแนวดิ่งของโหนดว่าอยู่ห่างจาก 

    Root Node เป็นระยะเท่าไรและทุกกิ่งมีความยาวเท่ากันคือ 1 หน่วย

    

      Degree แสดงถึงจำนวนของ Subtree ของโหนดนั้น เช่น A มี Degree2,X มี Degree 1

     Leaf Node แสดงถึงโหนดที่มี Degree = 0 เช่น C, D, E, I ,G ส่วนโหนดที่มี Degree <> 0 เรียกว่า   Branch Node หรือ Interior Node

     Predecessor หมายถึง ตัว Node ที่อยู่ก่อนหน้า

     Successor    หมายถึง ตัว Node ที่มาที่หลัง เช่น R, B, H เป็น Predecessor ของ E, I, 

      I เป็น Successor ของ H

     

      ต้นไม้แบบไบนารี (Binary Tree)

        ต้นไม้ไบนารีเป็น rooted binary tree ที่ว่างเปล่า  หรือประกอบด้วยรูตโหนดและต้นไม้ไบนารี 2 กลุ่มที่ไม่มีโหนดร่วมกัน  แต่ละกลุ่มจะมีชื่อเรียก (โดยตำแหน่งที่อยู่หรือที่เขียน) ว่าต้นไม้ย่อยทางซ้าย (left subtree) และต้นไม้ย่อยทางขวา (right subtree) ตามลำดับ คำว่า ว่างเปล่า ในนิยามหมายความว่า ต้นไม้ไบนารีต้นนั้นมีแต่รูตโหนดเพียงโหนดเดียวเท่านั้น

ต้นไม้ไบนารีแบบสมบูรณ์  (Complete Binary Tree)  

     ต้นไม้ไบนารีแบบสมบูรณ์  หมายถึง ต้นไม้ไบนารีที่แต่ละโหนดภายในมีโหนดย่อยซ้ายและขวา (นั่นคือแต่ละโหนดภายในมี left son และ right  son ) และโหนดใบ (leaf nodes) ทั้งหลายอยู่ในระดับที่ n รูป (ก) เป็นต้นไม้ไบนารีแบบสมบูรณ์ที่มี 3 ระดับ

ต้นไม้ไบนารี

      

ต้นไม้ไบนารีแบบสมบูรณ์ที่มีโหนดใบอยู่ที่ระดับ n จะมีโหนดทั้งหมดเท่ากับ 2n-1

จากรูป จำนวนโหนดเท่ากับ 23-1 =  7 โหนด

     การเปลี่ยน Tree ให้เป็น Binary Tree

     ต้นไม้แบบออดินารี(ordinary) คือต้นไม้ที่มีดีกรีสูงสุดของแต่ละโหนดเป็นเท่าไรก็ได้ ซึ่งการเปลี่ยนให้เป็น binary tree เป็นการจัดให้แต่ละโหนดมีดีกรีสูงสุดเท่ากับสอง  มีขั้นตอนดังนี้

 1. พิจารณาที่กิ่งทางซ้ายสุดที่อยู่ใต้พ่อเดียวกัน

 2. ต่อกิ่งของโหนดทางซ้ายสุดในขั้นที่ 1 ไปทางขวาตามลำดับอาวุโสกับพี่น้องที่เกิดจากพ่อเดียวกัน 

 3. ทำขั้นที่ 1 และ 2 จนครบทุกโหนด

 4. ปรับมุมของแต่ละกิ่ง ประมาณ 45 องศา

      

    การท่องต้นไม้ (Tree Traversal)

     Tree Traversal หมายถึงการไปยังโหนดเพื่อประมวลผลบางอย่างที่ต้องการกระทำกับโหนดนั้น เช่น หาข่าวสาร แบ่งออกเป็น 3 วิธี (ที่นิยมใช้)

 1. Pre-Order Traversal (RTLTR)

        2. In-Order Traversal (TLRTR)

        3. Post-Order Traversal (TLTRR)

   การท่องผ่าน Binary Tree
        การท่องผ่านโหนด หมายถึง การเข้าไปในโครงสร้างต้นไม้เพื่อนำข้อมูลในโหนดมาแสดง หรือเพื่อการค้นหา หรือการประมวลผล การเดินเยี่ยมโหนดมี 3 วิธี

 1. Inorder traversal หรือ Symmetric order    จะทำการเยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบอินออเดอร์ ก่อนเยี่ยมโหนดรากและเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบอินออเดอร์ (Left/ Root/Right)

 2. Preorder traversal จะทำการเยี่ยมโหนดรากก่อน เยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบพรีออเดอร์ และเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบพรีออเดอร์ (Root/ Left/ Right)

 3. Postorder traversal หรือ Endorder  จะทำการเยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบ โพสออเดอร์ ก่อนเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบ  โพสออเดอร์ และเยี่ยมโหนดราก   (Left/ Right/ Root)

    

     1.แบบอินออเดอร์ (Left/ Root/Right)  จากภาพจะได้ BAC   

     2.แบบพรีออเดอร์(Root/ Left/ Right) จากภาพจะได้ ABC

     3.แบบโพสออเดอร์(Left/ Right/ Root) จากภาพจะได้ BCA 

     Expression Tree

    เป็นต้นไม้แบบไบนารีที่ โหนดใบคือ operands, เช่นค่าคงที่หรือตัวแปร, และโหนดรากคือ operators

จากรูปแสดง   Expression tree ของ (a + b * c) + ((d * e + f ) * g)

     Expression Tree 

     คือต้นไม้ที่สร้างขึ้นจากตัวกระทำ(operand)     และเครื่องหมาย(operators) ทางคณิตศาสตร์ของนิพจน์ โดยการวางตัวกระทำที่โหนดใบ(leave node) และวางเครื่องหมายไว้ที่โหนดภายใน

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

    

     การสร้าง Expression Tree

      อ่านสัญลักษณ์จากนิพจน์ที่ละตัว ถ้าตัวที่อ่านมาเป็น operand ให้สร้างโหนดของ tree หนึ่งโหนดแล้ว push มันลงใน stack ถ้าตัวที่อ่านมาเป็น operator ให้ pop จาก stack 2 ครั้ง ซึ่งจะได้ trees T1 และ T2 (T1 นำออกก่อน) แล้วให้นำมาสร้างเป็น tree ใหม่ที่มีราก (root) เป็นตัว operator และมี left และ right children เป็น T2 และ T1 ตามลำดับ จากนั้นให้ใส่ tree ใหม่นี้กลับลง stack

บทที่ 7 กราฟ (Graph)

กราฟ (Graph)

    กราฟ (Graph)  เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นอีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงานที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน 

    ตัวอย่าง

     

        V = {A,B,C,D,E,F,G}

       E = {ab,ac,ad,be,cd,cf,de,ef,fg,eg}

    โครงสร้างข้อมูลแบบกราฟ (Graph)

    ศัพท์ที่เกี่ยวข้อง

   1. เวอร์เทก (Vertex)  หมายถึง  โหนด

   2. เอดจ (Edge)หมายถึงเส้นเชื่อมต่อระหว่างเวอร์เท็กซ์บนกราฟ แบบ Undirected Graph

   3. Arc หมายถึง เส้นที่เชื่อมต่อระหว่างเวอร์เท็กซ์บนกราฟ แบบ Directed Graph

  4. ดีกรี (Degree)หมายถึงจำนวนเส้นเข้าและออก ของโหนดแต่ละโหนด

     แอดจาเซนท์โหนด (Adjacent Node) หมายถึง โหนดที่มีการเชื่อมโยงกัน

      Graph แบ่งเป็น 1.Directed Graph (Digraph)   

                                2.Undirected Graph

    โครงสร้างข้อมูลแบบกราฟ (Graph)

     

    แอดจาเซนท์โหนด (Adjacent Node)

    A กับ B ใช่

    D กับ F ไม่ใช่

    

      

       เส้นทาง (Path) 

   ใช้เรียกลำดับของ เวอร์เทก (Vertex) ที่เชื่อมต่อกันจากจุดหนึ่งไปยังอีกจุดหนึ่ง

     (A,B,C,D,E)

     (A,B,E,F)

     Cycle

     Path ที่ประกอบด้วยอย่างน้อย 3 Vertex และมีจุดเริ่มต้นและสิ้นสุดเดียวกัน เช่น

    (B,C,E,B)

    (B,C,D,E,B)

     ลูป (Loop)

  มีเพียง Arc เดียวและมีจุดเริ่มต้นและสิ้นสุดเดียวกัน

     Directed Graph : มีการกำหนดทิศทาง

     Strongly Connected   ทุก ๆ 2 Vertex มี Path ทั้งไปและกลับ 

     (ทุกโหนดในกราฟมีพาทติดต่อถึงกันหมด)

    Weakly Connected : มีอย่างน้อย 2 Vertex ที่มี Path ในทิศทางเดียว(บางโหนดไม่สามารติดต่อไปยังทุกโหนดในกราฟนั้นได้)

    สูตรหาจำนวนเอดจ์ของกราฟสมบูรณ์แบบมีทิศทาง  =  N * (N –1)

 จากภาพที่ (ข) ซึ่งเป็นกราฟแบบมีทิศทาง และจำนวนเวอร์เทกซ์ที่มีทั้งหมดเท่ากับ 4 เวอร์เทกซ์ จึงคำนวณหาจำนวนเอดจ์ได้ดังนี้

  สูตรหาจำนวนเอดจ์ของกราฟมีทิศทาง     =  N * (N –1)

         = 4 * ( 4 – 1)

         = 4 * 3

         = 12 เส้น

     Undirected Graph : ไม่มีการกำหนดทิศทาง

     

  

เป็นกราฟที่ไม่ระบุทิศทางของการเชื่อมต่อ

    ซึ่งสามารถทำให้สามารถเดินทางไปมาระหว่างกันได้

       สูตรหาจำนวนเอดจ์ของกราฟสมบูรณ์แบบไม่มีทิศทาง 

  = (N * (N – 1)) / 2

  กราฟแบบไม่มีทิศทาง และจำนวนเวอร์เทกซ์ที่มีทั้งหมด   เท่ากับ 4 เวอร์เทกซ์ จึงคำนวณหาจำนวนเอดจ์ได้ดังนี้

   สูตรหาจำนวนเอดจ์ของกราฟไม่มีทิศทาง  = (N * (N – 1)) / 2

           = (4 * (4 – 1)) / 2

           = (4 * 3 ) / 2

           = 12 / 2

          = 6 เส้น

    กราฟที่มีน้ำหนัก (Weighted Graphs)

     กราฟที่แต่ละเอดจ์จะมีค่าบ่งบอกถึงความหมายอย่างใดอย่างหนึ่ง เช่น ระยะทาง ความเร็ว เวลาเดินทาง ค่าโดยสาร เป็นต้น 

 กราฟที่ไม่มีน้ำหนัก (Unweighted Graphs)

    เป็นกราฟที่ไม่กำหนดน้ำหนักของเส้นเชื่อมต่อโดยให้แต่ละเส้นมีน้ำหนักเป็น 1  เท่ากัน

     หมดทุกเส้น

  การเก็บข้อมูลในหน่วยความจำสามารถทำได้ 2 แบบ ดังนี้

   1.Adjacency Matrix  :   ใช้อาร์เรย์เก็บข้อมูล

   2. Adjacency List  :  ใช้ลิงค์ลิสต์เก็บข้อมูล

     Adjacency Matrix

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

     Mk เป็นเมทริกซ์ของกราฟใด ๆ  k คือทางเดินที่มีความยาว k จากโหนดหนึ่งไปอีกโหนดหนึ่ง 

      0 : ไม่เป็นแอดจาเซนซีกัน

      1 : เป็นแอดจาเซนซีกัน

     

    การแทนกราฟด้วยอะเรย์สองมิติ

   

  Adjacency List

     Graph Traversal

    สามารถทำได้ 2 วิธี

1. แนวลึก : Depth-first Traversal  

2. แนวราบ : Breath-first Traversal

     Breath-first Traversal

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

   1. Enqueue vertex

   2. Dequeue vertex และประมวลผล

   3. Enqueue adjacent ทั้งหมดของ Vertex ในข้อ 2

   4. ทำซ้ำข้อ 2-3 จนกว่าจะครบทุก Vertex และ Queue ว่าง

    

     Network

    คือ Graph ที่ทุก Edge มี Weight กำกับโดยความหมายของ Weight นั้นขึ้นอยู่กับการใช้งาน

   Adjacency Matrix

Adjacency List

    Minimum Spanning Tree (MST) 

    คือSpanning Tree ที่มีผลรวมของ Weight ทั้งหมดน้อยที่สุด

   1.ใส่ Vertex เริ่มต้นใน Tree

   2.เลือก Edge จาก Vertex ใน Tree ไปยัง Vertex ที่ไม่อยู่ใน Tree และมี Weight ต่ำสุด

  3.ทำซ้ำข้อ 2 จนกว่าจะครบทุก Vertex

 Shortest Path หมายถึง Path ที่สั้นที่สุดระหว่าง 2 Vertexหาเส้นทางการส่งข้อมูลจากต้นทางไปปลายทาง โดยให้มีระยะทางสั้นที่สุด

   1.ใส่ Vertex เริ่มต้นใน Tree

   2.เลือก Edge จาก Vertex ใน Tree ไปยัง Vertex ที่ไม่อยู่ใน Tree และมีผลรวมของ Weight ต่ำสุด

   3.ทำซ้ำข้อ 2 จนกว่าจะครบทุก Vertex

  minimum Spanning Tree เป็นรูปแบบของการค้นหาโดยกำหนดเรียกใช้โหนดทุกโหนดและทุกเส้นการเชื่อมต่อ  มาลำดับความสำคัญของน้ำหนักโดยเริ่มจากค่าน้อยที่สุดในข่ายงาน  ทำการเชื่อมต่อคู่โหนดนั้น  และดำเนินการต่อไปในค่าน้ำหนักที่ต่อกัน  แต่ถ้าโหนดใดมีการเชื่อมต่อคู่โหนดแล้วจะไม่เชื่อมต่ออีก

   Shortest Path เป็นอัลกอริทึมที่ใช้ในการหาระยะทางที่สั้นที่สุดเช่นเดียวกับ  MST  แต่จะเปลี่ยนจากการหาเส้นทางจากโหนดแรกไปยังโหนดปลายทางของข่ายงาน  เป็นโหนดที่กำหนดเป็นโหนดต้นทางไปยังโหนดต่าง ๆ โดยหาระยะทางสั้นที่สุดแต่ละเส้นทาง

 Minimum Spanning Tree

Spanning Tree หมายถึง Tree ที่ประกอบด้วยทุก Vertex ใน Graph ซึ่งอาจมีได้มากกว่า 1 แบบ

บทที่ 6 คิว Queue

คิว Queue

     ลักษณะโครงสร้างข้อมูลแบบคิว (Queue)

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

    ข้อมูลที่นำเข้าไปเก็บก่อนจะถูกนำออกมาทำงานก่อน ส่วนข้อมูลที่เข้าไปเก็บทีหลังก็จะถูกนำออกมาใช้งานทีหลัง คุณสมบัติที่เรียกว่า  FIFO (First-In-First-Out)ขั้นตอนที่ซับซ้อนกว่าสแตก  เนื่องจากต้องจัดการกับตัวชี้ front และ rear ให้ถูกต้องตัวชี้ Front ชี้ไปที่สมาชิกตัวแรก และตัวชี้ Rear ชี้ไปที่สมาชิกตัวสุดท้ายของคิว โดยที่เวลาข้อมูลจะเข้าสู่คิวจะเข้าทาง R ส่วนเวลาที่ข้อมูลจะออกจากคิวออกทาง F 

     การแทนข้อมูลของคิว

     

    การดำเนินการกับคิว

      ➧การเพิ่มข้อมูลในคิว (Enqueue)

     ➧การดึงข้อมูลจากคิว (Dequeue)

     ➧การตรวจสอบคิวว่าง (Empty)

     ➧การตรวจสอบคิวเต็ม (Full)

     การเพิ่มข้อมูลในคิว (Enqueue)

    การเพิ่มข้อมูลในคิว ข้อมูลจะถูกเพิ่มเข้ามาทางด้าน Rear ของคิว

  ขั้นตอนการเพิ่มข้อมูลลงในคิว

ตรวจสอบว่าคิวเต็มหรือไม่ กรณีเกิดคิวเต็มค่าของ Rear จะเท่ากับขนาดสูงสุดของตัวแปรอาร์เรย์ถ้าคิวเต็มควรแจ้งด้วยว่า คิวเต็ม ไม่สามารถเพิ่มข้อมูลได้

    การนำข้อมูลเข้าสู่คิวจะไม่สามารถนำเข้าในขณะที่คิวเต็มหรือไม่มีที่ว่าง ถ้าพยายามจะทำจะเกิด errorเรียกว่า  overflow

    ถ้าคิวยังว่างอยู่ ให้ขยับ Rear ไปที่ตำแหน่งถัดไป 1 ตำแหน่ง

 นำข้อมูลที่ต้องการเพิ่มมาเก็บไว้ ณ ตำแหน่งใหม่ของ Rear

ถ้าข้อมูลที่เพิ่มเข้าไปเป็นค่าเดียวในคิว ให้ขยับ Front มาอยู่ตำแหน่งเดียวกันกับ Rear นั่นคือ Front = 1

     

การดึงข้อมูลจากคิว (Dequeue)

      🔜 ข้อมูลจะถูกดึงออกจากคิวผ่านทาง Front   กรณีถ้าข้อมูลอยู่ภายในคิวมีเพียงตัวเดียว ค่า Front จะมีค่าเท่ากับ Rear

       🔜ขั้นตอนการดึงข้อมูลจากคิว

       🔜ตรวจสอบดูก่อนว่า คิวว่างหรือไม่ ถ้าคิวว่างให้แจ้งออกมาว่า คิวว่าง ดึงข้อมูลไม่ได้

      🔜การนำข้อมูลออกจากคิว  จะไม่สามารถนำอะไรออกจากคิวที่ว่างเปล่า  ถ้าพยายามจะทำจะเกิด error ที่เรียกว่า underflow

      🔜ถ้าคิวไม่ว่าง ให้ดึงข้อมูลที่ Front ออกมาเก็บไว้ในตัวแปร (ก็คือ ตัวข้อมูลที่ดึงออกมาได้)

      🔜ตรวจสอบดูว่า ข้อมูลที่ถูกดึงออกมาเป็นข้อมูลตัวสุดท้ายในคิวหรือไม่ นั่นคือ ดูว่า Front = Rear หรือไม่

      🔜 ถ้า Front = Rear นั่นคือ ข้อมูลที่ดึงออกมาเป็นข้อมูลตัวสุดท้าย ฉะนั้นตอนนี้คิวว่างแล้ว วิธีการบอกว่าคิวว่างก็คือ Front = Rear = 0

       🔜ถ้า Front != Rear คือ คิวไม่ว่าง ก็ให้ขยับ Front ขึ้นไปอีก 1 ขั้น

      การตรวจสอบคิวว่าง (Empty)

     การตรวจสอบว่าคิวว่างหรือไม่นั้น เป็นงานประจำที่จะต้องทำเมื่อต้องการดึงข้อมูลออกจากคิว ซึ่งมีหลักการในการพิจารณาง่ายๆ คือ กรณีที่จะเกิดคิวว่างได้ก็ต่อเมื่อ Front = Rear = 0 เท่านั้น

    การตรวจสอบคิวเต็ม (Full)

     การตรวจสอบว่าคิวเต็มหรือไม่นั้น เป็นการดำเนินการที่จำเป็นต้องทำเสมอเมื่อต้องการที่จะเพิ่มข้อมูลเข้าไปในคิวซึ่งมีหลักการในการพิจารณาคือกรณีเกิดคิวเต็มค่าของ Rearจะมีค่าเท่ากับความจุของคิวนั้น

    คิวว่าง (Empty) และคิวเต็ม (Full)

  

     คิววงกลม (Circular Queue)

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

     ⦽ลักษณะของคิววงกลม คือ การมองภาพตัวแปรอาร์เรย์ที่ใช้แทนคิวให้เป็นวงกลม นั่นคือ ให้ถือว่าด้านหน้า (Front) ของคิวตำแหน่งต่อจากด้านหลังของคิว (Rear) เสมือนรูปวงกลม 

     ⦽ในคิวแบบธรรมดา  เมื่อ R = N  จะหมายถึงคิวเต็ม  แต่คิวแบบนี้ เมื่อR = N  จะปรับให้  R = 1

  

    การดำเนินการกับคิววงกลม

   การตรวจสอบคิวเต็มในคิววงกลม (Full)

   การตรวจสอบคิวว่างในคิววงกลม (Empty)

   การเพิ่มข้อมูลเข้าไปในคิววงกลม (Enqueue)

  

   การดึงข้อมูลออกจากคิววงกลม (Dequeue)

   ⧪ การตรวจสอบคิวเต็มในคิววงกลม (Full)

      🔺การตรวจสอบว่าคิววงกลมมีข้อมูลเก็บอยู่จนเต็มหรือไม่นั้น จะมีวิธีการทดสอบที่แตกต่างจากการตรวจสอบคิวปกติ เนื่องจากคิววงกลมมีลักษณะวนเป็นวงกลม ดังนั้น ตำแหน่งของข้อมูลมีโอกาสที่จะวนจากตำแหน่งสูงสุดกลับมายังตำแหน่งที่ 1 ได้เสมอ

       🔺ลักษณะค่าของ Front และ Rear เมื่อเกิดคิววงกลมเต็มมีอยู่ 2 แบบเมื่อ Front อยู่ที่ 1 และ Rear อยู่ที่ตำแหน่งสูงสุดของคิว นั่นคือ อยู่ที่ค่า Max เมื่อ Front อยู่ที่ตำแหน่งใดๆ ภายในคิววงกลม (ที่ไม่ใช่ตำแหน่งที่ 1) ค่าของ Rear ก็จะอยู่ตำแหน่งที่อยู่ด้านหน้าของ Front ไปอีก 1 ค่า (Rear = Front -1)

    

   ⧪ การเพิ่มข้อมูลเข้าไปในคิววงกลม (Enqueue)

     🔺ต่างไปจากการเพิ่มข้อมูลเข้าไปในคิวปกติ ตรงที่เมื่อ Rear มีค่าไปถึงค่าสูงสุดของอาร์เรย์แล้ว ถ้าจะต้องมีการขยับเพิ่มขึ้น ค่า Rear ถัดไปก็คือ วนกลับมาที่ค่า 1 อีกครั้ง

      🔺ขั้นตอนการเพิ่มข้อมูลเข้าไปในคิววงกลม

      ตรวจสอบดูก่อนว่าคิววงกลมเต็มหรือไม่ ถ้าเต็มก็ให้แจ้งผลออกไป

      เพิ่มค่าตำแหน่งของ Rear ให้ไปชี้ ณ ตำแหน่งถัดไป โดยถ้าเดิมตำแหน่งของ Rear คือตำแหน่งสูงสุดของคิวแล้ว ตำแหน่งถัดไปของ Rear ก็คือ 1 ส่วนถ้ากรณีเดิมตำแหน่งของ Rear อยู่ ณ ตำแหน่งใดๆ ก็ตาม ตำแหน่งถัดไปก็คือ เพิ่มค่าขึ้นไปอีก 1  

      นำค่าที่ต้องการใส่ในคิวมาใส่ ณ ตำแหน่งใหม่ของ Rear

      กรณีถ้าค่าที่เพิ่งใส่เข้าไปเป็นค่าแรกของคิววงกลม (Rear = 1) ให้เลื่อน Front 

     มาชี้ที่ 1 ด้วย 

     ⧪การดึงข้อมูลออกจากคิววงกลม (Dequeue)

      ขั้นตอนการดึงข้อมูลออกจากคิววงกลม

    🔼 ตรวจสอบคิววงกลมเป็นคิวว่างหรือไม่ ถ้าเป็นคิวว่างควรแจ้งออกมาว่าเป็นคิวว่าง

     ถ้าไม่ใช่คิวว่าง ให้นำข้อมูลตำแหน่ง Front ออกจากคิววงกลม (เก็บค่าไว้ในตัวแปร)

    🔼 ตรวจสอบดูว่า ข้อมูลตัวที่กำลังจะถูกดึงนี้ เป็นข้อมูลตัวสุดท้ายที่เหลืออยู่ในวงกลม 🔼ถ้าไม่ ถ้าใช่ให้ย้ายค่า Front และ Rear กลับไปอยู่ ณ ตำแหน่งเริ่มต้น 

     🔼ถ้าไม่ใช่ข้อมูลตัวสุดท้ายที่เหลืออยู่ ให้ตรวจสอบอีกว่า ข้อมูลตัวนี้มีค่า Front อยู่ทตำแหน่งสูงสุดในอาร์เรย์หรือไม่ ถ้าใช่ให้ย้าย Front ลงมาที่ตำแหน่งค่า 1

     🔼ถ้าไม่ใช่ ให้เพิ่มค่า Front ขึ้นไปอีก 1 ค่า ย้ายไปชี้ที่ตัวถัดไป