บทที่5โครงสร้างข้อมูลคิว(Queue)
คิว (Queue) เป็นโครงสร้างข้อมูลที่รู้จักและนำมาใช้งานมากเช่นเดียวกับ Stack มีลักษณะเป็นรายการในแนวเชิงเส้น (Linear List) แต่ลักษณะการทำงานจะตรงกันข้ามกับ Stack คือ การเพิ่มข้อมูลจะเพิ่มไปตอนท้ายของรายการได้เพียงด้านเดียว เรียกว่า ส่วนหลัง (Rear) และตอนนำค่าออกมาใช้งานหรือลบค่าออกจาก Queue จะลบออกทางตอนต้น เรียกว่า ส่วนหน้า (Front) ซึ่งถ้า Q แทนโครงสร้างของ Queue จะกำหนดให้
Front(Q) เป็น ส่วนหน้าของ Q
Rear(Q) เป็น ส่วนท้ายของ Q
โดยมีรูปแบบ ดังนี้
Q = { Q1 , Q2 , Q3 , …, QT};
Front(Q) คือ Q1 และ Rear(Q) คือ QT (กรณีที่มีจ านวนสมาชิกเท่ากับ T)
ค่าที่เข้ามาก่อนจะถูกน าไปใช้งานก่อนเสมอ ลักษณะของคิวจะถูกน าไปประยุกต์เพื่อแก้ไขปัญหาต่าง ๆ เช่น จ าลอง (Simulation) การท างานของระบบงานจริงที่มีลักษณะเข้าก่อนออกก่อน เช่น การเข้าแถวซื้อของหรือช าระเงิน, ส ารวจปริมาณรถ ติดเพื่อควบคุมไฟจราจร, การส่งข่าวสารในเครือข่าย, การสั่งพิมพ์ข้อมูลทางเครื่องพิมพ์ หรือแม้กระทั่งการสับตู้รถไฟบนราง
หลักการนี้เรียกว่า “เข้าก่อนออกก่อน” หรือ First-In First-Out : FIFO หรือ
Last-InLast-Out : LILO หรือ First-Come First-Served : FCFS
การปฏิบัติการของคิว มีชุดปฏิบัติการ ดังนี้
1. CreateQueue() ใช้สำหรับสร้างคิวขึ้นมาใหม่
2. Insert(,<ชื่อตัวแปรของโครงสร้างข้อมูลคิว>) ใช้สำหรับนำค่าเข้าไปเก็บใน โครงสร้างข้อมูลคิว
ส่วนกรณีที่ต้องการทราบว่ามีข้อมูลให้ดึงออกไปใช้งานอีกหรือไม่จะใช้วิธีตรวจสอบกับ Front และ Rear ถ้าเป็น ตัวอย่างด้านล่างก็ตรวจสอบว่า Front มากกว่า Rear หรือไม่ ถ้าใช่ก็หมายความว่าในคิวไม่มีข้อมูลอยู่เลย จะไม่ สามารถดึงข้อมูลไปใช้งานได้
การประยุกต์ใช้งานตอนที่สร้างโครงสร้างของคิวว่าง ๆ มาใช้งานจะก าหนดให้ตัวแปร Front และ Rear มีค่าเป็นดังนี้
Front = 0
Rear = -1
Front
ส่วน Rear ยังไม่ชี้ในโครงสร้างข้อมูลคิว
If(Front > Rear) หรือ if(Rear == -1) // ใช่ คือ Queue ว่าง ถ้าไม่ใช่ คือ มีข้อมูล
นำค่าไปเก็บใน Queue
1. น าค่า “A” มาเก็บใน Queue
ขยับ Rear ไปยังต าแหน่งถัดไป ดังนี้
Rear = Rear + 1; // Rear = 0 แล้วน าค่า “A” ไปใส่ในตำแหน่งดังกล่าว
2. น าค่า “B” มาเก็บใน Queue
ขยับ Rear ไปยังต าแหน่งถัดไป ดังนี้
Rear = Rear + 1; // Rear = 1 แล้วน าค่า “B” ไปใส่ในต าแหน่งดังกล่าว
3. น าค่า “X” มาเก็บใน Queue
ขยับ Rear ไปยังต าแหน่งถัดไป ดังนี้
Rear = Rear + 1; // Rear = 2 แล้วน าค่า “X” ไปใส่ในต าแหน่งดังกล่าว
4. น าค่า “Y” มาเก็บใน Queue
ขยับ Rear ไปยังต าแหน่งถัดไป ดังนี้
Rear = Rear + 1; // Rear = 3 แล้วน าค่า “Y” ไปใส่ในต าแหน่งดังกล่าว
เรียกใช้ค่าใน Queue
1. เรียกใช้ค่าครั้งที่ 1
ดึงค่าในตำแหน่งที่ Front ชี้อยู่ ซึ่งในขณะนี้ก็คือ “A” ออกมาใช้งาน แล้วขยับ Front ไปยังตำแหน่งถัดไป ดังนี้
Front = Front + 1; // Front = 1
2. เรียกใช้ค่าครั้งที่ 2
ดึงค่าในตำแหน่งที่ Front ชี้อยู่ ซึ่งในขณะนี้ก็คือ “B” ออกมาใช้งาน แล้วขยับ Front ไปยังตำแหน่งถัดไป ดังนี้
Front = Front + 1; // Front = 2
3. เรียกใช้ค่าครั้งที่ 3
ดึงค่าในตำแหน่งที่ Front ชี้อยู่ ซึ่งในขณะนี้ก็คือ “X” ออกมาใช้งาน แล้วขยับ Front ไปยังตำแหน่งถัดไป ดังนี้
Front = Front + 1; // Front = 3
4. เรียกใช้ค่าครั้งที่ 4
ดึงค่าในตำแหน่งที่ Front ชี้อยู่ ซึ่งในขณะนี้ก็คือ “Y” ออกมาใช้งาน แล้วขยับ Front ไปยังตำแหน่งถัดไป ดังนี้
Front = Front + 1; // Front = 4
นำค่าไปเก็บใน Queue
1. น าค่า “F” มาเก็บใน Queue
ขยับ Rear ไปยังตำแหน่งถัดไป ดังนี้
Rear = Rear + 1; // Rear = 4 แล้วน าค่า “F” ไปใส่ในตำแหน่งดังกล่าว
2. น าค่า “G” มาเก็บใน Queue
ขยับ Rear ไปยังตำแหน่งถัดไป ดังนี้
Rear = Rear + 1; // Rear = 5 แล้วน าค่า “G” ไปใส่ในตำแหน่งดังกล่าว
3. นำค่า “H” มาเก็บใน Queue // if(Rear == Size – 1) // ใช่ คือ Queue เต็ม
ขยับ Rear ไปยังตำแหน่งถัดไป ดังนี้ // ส่วนนี้จะไม่ถูกทำงาน เพราะว่า คิวเต็ม Rear = Rear + 1; // ส่วนนี้จะไม่ถูกทำงาน เพราะว่า คิวเต็ม
ในข้อ 3. นี้ก็จะไม่สามารถนำค่า H ใส่เข้าไปในโครงสร้างข้อมูลคิวได้เรียกว่า การ ล้นของคิว (Queue Overflow)
สร้าง Circular Queue จำนวน 7 ค่า และกำหนดให้ Front = 0 และ Rear = -1 กรณี ให้ตัวแปร Pointer อาจจะก าหนดให้ Rear = null ก็ได้
นำค่าไปเก็บใน Queue
1. นำค่า ‘A’ มาเก็บใน Queue เนื่องจากคิวว่างอยู่ สามารถเพิ่มค่าได้ทันที // Front = 0 // Rear = 0 (Rear + 1) % maxSize = (-1 + 1) % 7 = 0
2. นำค่า ‘B’ มาเก็บใน Queue ตรวจสอบว่าเต็มหรือไม่ (0 + 1) % 7 = 1 // Rear = 1 // Front = 0
3. นำค่า ‘X’ มาเก็บใน Queue ตรวจสอบว่าเต็มหรือไม่ (1 + 1) % 7 = 2 // Front = 0
4. นำค่า ‘Y’ มาเก็บใน Queue ตรวจสอบว่าเต็มหรือไม่ (2 + 1) % 7 = 3 // Front = 0
5. นำค่า ‘Z’ มาเก็บใน Queue ตรวจสอบว่าเต็มหรือไม่ (3 + 1) % 7 = 4 // Front = 0
6. นำค่า ‘F’ มาเก็บใน Queue ตรวจสอบว่าเต็มหรือไม่ (4 + 1) % 7 = 5 // Front = 0
7. นำค่า ‘G’ มาเก็บใน Queue ตรวจสอบว่าเต็มหรือไม่ (5 + 1) % 7 = 6 // Front = 0 Rear = Rear + 1; // Rear = 6
8. นำค่า ‘H’ มาเก็บใน Queue
(Rear + 1) % maxSize = Front หรือไม่ (เท่า = คิวเต็ม) (6 + 1) % 7 = 0 // Front = 0
แต่วิธีการนี้ก็นำมาใช้งานไม่ได้ เพราะ หากว่าในระหว่างที่มีการนำข้อมูลเข้า แล้วมีการดึงข้อมูลออกด้วย Front ก็จะไม่ชี้ใน ตำแหน่งที่ 0 ซึ่งทำให้ตำแหน่งที่ 0 เกิดว่างขึ้นมา
สูตรที่ใช้ในการตรวจสอบว่าคิวเต็มหรือไม่ คือ
(Rear + 1) % maxSize = Front
แทนค่า (6 + 1) % 7 = 0 // Front = 0
