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

QUEUE

คุณสมบัติที่สำคัญ

-  เป็นโครงสร้างข้อมูลแบบต่อเนื่อง

-  มีการทำงานแบบ First in First out (FIFO)

-  จะต้องทำการเพิ่มข้อมูลทางด้านท้าย (rear) ของคิว และลบข้อมูลทางด้านหน้า (front) ของคิวเท่านั้น

-  การ implement การทำงานแบบคิว อาจใช้ Array หรือ Linked List

แถวคอย

ประโยชน์ของคิว

 -  ลักษณะของคิวเหมือนแถวคอย หรือการเข้าคิวรอซื้อของเป็นกลไกสำคัญสำหรับระบบปฏิบัติการ

 -  การส่งงานไปยังเครื่องพิมพ์ในระบบคอมพิวเตอร์ 

 -  ระบบการจัดการจราจรทางอากาศ 

เป็นต้น

การสร้างคิว

-  ใช้ pointer 2 ตัวในการลำดับคิว คือ front และ rear 

-  front คือตำแหน่งที่ข้อมูลออก จะอยู่ด้านหน้าคิว

-  Rear  คือตำแหน่งที่ข้อมูลเข้า จะอยู่ด้านท้ายของคิว

แถวคอย

ปฏิบัติการกับคิว

-  การเพิ่มข้อมูลเข้าไปในคิว(enqueue) หรือการ insert

-  การนำข้อมูลออกจากคิว (dequeue) หรือการ delete

Queue Implementation

-  Array

-  Linked List

ตัวอย่างการแทนคิวด้วย Array, size = 6

Queue : Array Implementation

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

-ก่อนนำสมาชิกเข้าคิว ต้องตรวจสอบว่าคิวเต็มหรือไม่ โดยที่ ถ้า rear = maxQ แสดงว่าคิวเต็ม (เมื่อ maxQ คือขนาดของคิว)

-ถ้าคิวเต็ม (full) จะไม่สามารถนำข้อมูลเข้าได้อีก จะทำให้เกิดการล้นของคิว (queue overflow)

-การนำสมาชิกเข้าในคิว จะเข้าทางด้านท้ายคิว (rear)

-ดังนั้นการนำสมาชิกเข้าคิว จึงเป็นการเพิ่มค่าพอยน์เตอร์ rear

-หากมีสมาชิกในคิวเพียงค่าเดียวพอยน์เตอร์ rear และ front จะเท่ากัน

Queue : Array Implementation

การนำข้อมูลออกจากคิว (dequeue)

-ก่อนนำสมาชิกออกจากคิว ต้องตรวจสอบดูก่อนว่าคิวว่างเปล่าหรือไม่ โดยเงื่อนไขการตรวจสอบคือ front = rear = 0

-ถ้าคิวว่าง จะไม่สามารถนำสมาชิกออกไม่ได้ จะเกิดปรากฏการณ์ขาดแคลนคิว (queue underflow)

-การนำสมาชิกออกจากคิว จะทำด้านหน้าคิว (front)

-ดังนั้นการนำสมาชิกออกจากคิวจึงเป็นการเพิ่มค่าพอยน์เตอร์ front 

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

เป็นการแก้ปัญหาคิวเต็ม ทั้งที่ยังมีเนื้อที่ว่างอยู่

เป็นการใช้เนื้อที่ให้เกิดประโยชน์สูงสุด

ลักษณะของคิวแบบวงกลม

-เหมือนคิวธรรมดาคือมีตัวชี้ 2 ตัวคือ front และ rear สำหรับแสดงตำแหน่งหัวคิวและท้ายคิวตามลำดับ

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

-คิววงกลมจัดการปัญหานี้โดย กรณี rear ชี้อยู่ที่ตำแหน่งสุดท้ายของคิว ถ้าหากมีการเพิ่มข้อมูล ค่าของ rear จะสามารถวนกลับมาชี้ยังตำแหน่งแรกสุดของคิวได้

-ดังนั้นคิววงกลมจะสามารถเพิ่มข้อมูลเข้าไปในคิวได้ จนกว่าคิวจะเต็มจริง ๆ

การดึงข้อมูลออกจากคิววงกลม (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 ค่า ย้ายไปชี้ที่ตัวถัดไป

Tree

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

องค์ประกอบของทรี

   โหนด ( Node ) ที่ใช้สำหรับบรรจุข้อมูลโดยจะมีกิ่งซึ่งเป็นเส้นที่โยงโหนด

เข้า ด้วยกันที่เรียกปลาจำนวนของ บรานช์ (Branch) ที่สัมพันธ์กับโหนด

เรียกว่า ดีกรี (Degree) และถ้าหากที่เป็นที่ที่ไม่ใช่ที่ว่างหนวดแรกจะเรียกรูท 

(root) โดยโหนดทุก ๆ โหนดยกเว้นรูทโหนดจะมีเพียง 1 predecessor ในขณะ

ที่ successor อาจเป็น 0 หรือ 1 หรือมากกว่า 1 ก็ได้ สำหรับ Leaf ก็คือโหนดใบ

ที่ไม่มีบรานช์เชือมโยงไปยังโหนดถัดไปหรือโหนดที่ไม่มีตัวตามหลังหรือ Successor

นั่นเองในขณะที่ โหนดพ่อ (Parent) จะมี่โหนดตามหลังหรือโหนดลูก (Child)ต่อท้าย

โหนดลูกตั้งแต่สองโหนดหรือมากกว่าที่มาจากพ่อเดียวกันจะเรียกว่า โหนดพี่น้อง (Siblings)

     โหนดต่าง ๆ ภายในทรีจะอยู่ในระดับที่ต่างกันโดยเริ่มต้นจากรูทโหนดซึ่งถือเป็นระดับ

แรกสุด(Level) ส่วนลูกๆ ของรูทโหนดก็คือระดับที่ 1 (Lelvel) และลูกๆ ของโหนด

ในระดับที่ 1 ก็จะอยู่ในระดับที่ 2 (Level 2) ซึ่งจะเพิ่มระดับไปเรื่อยๆเมื่อลูกหลานเพิ่ม

ขึ้น

ซับทรี (Subtrees)

หมายถึง โครงสร้างที่เชื่อมต่อกันภายใต้ Root โดย

- Node แรกของ Subtrees จะเป็น  Root ของ Subtree นั้น และใช้เป็นชื่อเรียก Subtree

- Subtree สามารถแบ่งย่อยเป็น Subtree ได้อีกจนกว่าจะ  Empty

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

  ไบนารีทรี หมายถึงทรีที่มีโหนดลูกไม่เกิน สองโหนด ประกอบด้วยโหนดลูกทางซ้าย

(Left child)และโหนดลูกทางขวา(Right child) โหนดลูกอาจเป็นทรีย่อย

ก็ได้ซึ่งแบ่งออกเป็น ทรี ย่อยทางซ้ายและทรีย่อยทางขวาและโหนดลูกแต่ละโหนด

อาจมีหนดลูกเพียงด้านซ้ายหรือด้านขวาด้านเดียวก็ได้สำหรับโหนดของทรีมีจำนวน

เป็น 0 เรียกว่าทรีว่าง (Empty Tree)

การท่องผ่าน Binary tree

  การท่องผ่านโหนดหมายถึงการเข้าไปในโครงสร้างต้นไม้เพื่อนำข้อมูลในโหนดมา

แสดงหรือเพื่อการค้นหาเพื่อประมวลผลการเดินเยี่ยมโหนดมี 3 วิธี

1. imorder trabersal หรือ symmetric order จะทำการเยี่ยมโหนดในต้นไม้

ย่อยทางซ้ายแบบอินออเดอร์ก่อนเยี่ยมโหนดรากและเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบ

อินออเดอร์(Left/ Root/ Right)

2. preorder traversal จะทำการเยี่ยมโหนดรากก่อน เยี่ยมโหนดในต้นไม้ย่อยทาง

ซ้ายแบบ พรีออเดอร์ และเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบพรีออเดอร์

(Root/Left/Right)

3. postorder traversal หรือ Endorder จะทำการเยี่ยมโหนดในต้นไม้ย่อยทาง

ซ้ายแบบ โพสออเดอร์ก่อนเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบโพสออเดอร์และเยี่ยมโหนด

ราก(Left/Right/Root)