DTS 07-11/08/2009

Queue

คิว (Queue) เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือ
ลิเนียร์ลิสต์ซึ่งการเพิ่มข้อมูลจะกระทำที่ปลายข้างหนึ่งซึ่ง
เรียกว่าส่วนท้ายหรือเรียร์ (rear) และการนำข้อมูลออกจะ
กระทำที่ปลายอีกข้างหนึ่งซึ่งเรียกว่า ส่วนหน้า หรือฟรอนต์
(front)
ลักษณะการทำงานของคิวเป็นลักษณะของการเข้าก่อน
ออกก่อนหรือที่เรียกว่า FIFO (First In First Out)
การทำงานของคิว
การใส่สมาชิกตัวใหม่ลงในคิว เรียกว่า Enqueue

ซึ่งมีรูปแบบคือ
enqueue (queue, newElement)
หมายถึง การใส่ข้อมูลnewElement ลงไปที่ส่วนเรียร์ของคิว
การนำสมาชิกออกจากคิว เรียกว่าDequeue
ซึ่งมีรูปแบบคือ
dequeue (queue, element)หมายถึง การนำออกจากส่วนหน้า
ของคิวและให้ ข้อมูลนั้นกับ element
การนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดงจะ
เรียกว่า Queue Front
แต่จะไม่ทำการเอาข้อมูลออกจากคิว
การนำข้อมูลที่อยู่ตอนท้าย
ของคิวมาแสดงจะ เรียกว่า
Queue Rear แต่จะไม่ทำ
การเพิ่มข้อมูลเข้าไปในคิว
การแทนที่ข้อมูลของคิว
สามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของคิวแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
จะประกอบไปด้วย 2 ส่วน คือ
1. Head Node
จะประกอบไปด้วย 3 ส่วนคือ
พอยเตอร์จำนวน 2 ตัว คือ Front และ rear
กับจำนวนสมาชิกในคิว
2. Data Node จะประกอบไปด้วย
ข้อมูล (Data) และพอยเตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป

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

1.Create Queue คือ จัดสรรหน่อยความจำให้แก่ Head Node

และให้ค่า ponter ทั้ง 2 ตัวมีค่าเป็น null และจำนวนสมาชิกเป็น 0

2.Enqueue คือ การเพื่มข้อมูลเข้าไปใน

3.Dequeue คือ การนำข้อมุลออกจากคิว

4.Queue Front คือ เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง

5.Queue Rear คือ เป็นการนำข้อมุลที่อยุ่ส่วนท้ายของคิวมาแสดง

6.Empty Queue คือ เป็นการตรวจสอบว่าคิวว่างหรือไม่

7.Full Queue คือ เป็นการตรวจสอบว่าคิวเต็มหรือไม่

8.Queue Count คือ เป็นการนับจำนวนสมาชิกที่อยู่ในคิว

9.Destroy Queue คือ เป็นการลบข้อมุลทั้งหมดที่อยู่ในคิว
การประยุกต์ใช้คิว
คิวถูกประยุกต์ใช้มากในการจำลองระบบงาน
ธุรกิจ เช่น การให้บริการลูกค้า ต้องวิเคราะห์จำนวน
ลูกค้าในคิวที่เหมาะสม
ว่าควรเป็นจำนวนเท่าใด เพื่อให้ลูกค้าเสียเวลาน้อย
ที่สุด ในด้านคอมพิวเตอร์ ได้นำคิวเข้ามาใช้ คือ
ในระบบปฏิบัติการ (Operation System) ในเรื่อง
ของคิวของงานที่เข้ามาทำงาน (ขอใช้ทรัพยากร
ระบบของ CPU) จะจัดให้งานที่เข้ามาได้ทำงาน
ตามลำดับความสำคัญ