บทที่ 5 คิว ( Queues )

บทที่ 5 คิว (Queue)

นิยามของคิว

     คิวมีโครงสร้างแบบเชิงเส้นเหมือนสแตก ต่างกันที่คิว มีตัวชี้ 2 ตัว คือ หัว (head)  และ หาง (tail) มีลักษณะแบบเข้าก่อนออกก่อน

การกระทำที่เกี่ยวข้องข้อมูลโครงสร้างแบบคิว
     -  การสร้างคิว (create)
     -  การนำสมาชิกข้อมูลเข้าคิว (enqueue)
     -  การนำสมาชิกออกจากคิว (dequeue)
     -  การทดสอบคิวว่าง (empty)
     -  การทดสอบคิวเต็ม (full)
     -  การทำให้คิวเป็นคิวว่าง (clear)

ลักษณะของโครงสร้างข้อมูลแบบแถวคอย
     -  คล้ายโครงสร้างขอมูลแบบสแตก
     -  ข้อมูลเข้าและออกจะทำตรงปลายคนละด้านกับสแตก
     -  ข้อมูลที่เข้ามาใหม่จะเพิ่มเข้ามาทางด้านหลัง (rear) ถ้าคิวเต็มแล้ว ยังมีการเพิ่มสมาชิกอีก จะเกิด Queue Overflow
     -  ข้อมูลที่นำออกจะอยู่ทางด้านหน้า (front) ถ้านำคิวออกจนคิวว่าง แต่ยังมีการนำออกอีก จะเกิด Queue Underflow
     -  เป็นแบบเข้าก่อนออกก่อน

การสร้างคิวด้วยอาร์เรย์ มี 4 ขั้นตอน
     1. การสร้าง
     2. การนำข้อมูลเข้า
     3. การนำข้อมูลออก
     4. การแสดงข้อมูล

     การสร้าง เป็นการแทนที่ข้อมูลคิวด้วยอาร์เรย์ เนื้อที่หน่วยความจำแบบ static นั่นคือ มีการกำหนดพื้นที่ล่วงหน้าว่ามีขนาดเท่าใด มีการกำหนดตัวชี้ 2 ตัว คือ F และ R เพื่อบอกตำแหน่งแรกสุด และ หลังสุด   

    การนำข้อมูลเข้า จะนำข้อมูลเข้าทางด้านหลัง โดยมี R เป็นตัวชี้ตรงตำแหน่งสุดท้ายไปเรื่อย ๆ จ นคิวเต็ม  

    การนำข้อมูลออก จะนำข้อมูลออกทางด้านหน้า โดยมี  F  เป็นตัวชี้ตำแหน่งที่ตัวแรก ลดถัดตามลำดับเรื่อย ๆ จนคิวว่าง

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

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

การประยุกต์ใช้คิว      ชนิดโครงสร้างข้อมูลแบบคิวมีความสำคัญมากในการดำเนินงานของระบบปฏิบัติการ ตัวอย่างเช่น
      - การใช้ทรัพยากร CPU จาก Server หรือ การใช้ทรัพยากร System Printer สำหรับผู้ใช้หลายคน 
      - ระบบปฏิบัติการจะใช้ชนิดข้อมูลแบบคิวในการจัดระเบียบผู้ใช้