บทที่ 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 ค่า ย้ายไปชี้ที่ตัวถัดไป