วันอังคารที่ 11 เมษายน พ.ศ. 2560
บทที่ 5
Queues Structure
การทำงานแบบคิวคือการมีการจัดลำดับการเข้าและออกข้อมูลอย่างเป็นลำดับ
ข้อมูลใดเข้ามาก่อนก็จะดำเนินการก่อน
หากข้อมูลใดเข้ามาทีหลังก็จะดำเนินการทีหลัง
เรียกลักษณะของการดำเนินการแบบนี้ว่า First In First Out (FIFO) หรือเข้าก่อนออกก่อน
ลักษณะของคิว
• โครงสร้างข้อมูลแบบคิวเป็นโครงสร้างเชิงเส้นและไม่เชิงเส้น• มีทางเข้าและออก 2 ทาง•มีการทำงานแบบลำดับ•สามารถนำข้อมูลเข้าและนำข้อมูลออกสลับกันได้
มีลำดับการทำงานแบบเข้าก่อนออกก่อน
(FIFO)
ประเภทของคิว
มี 3
ประเภท
•คิวธรรมดา (Queue)
•คิววงกลม (Circular Queue)•คิวที่เรียงลำดับตามความสำคัญ (Priority Queue)
การดำเนินการของคิว
•คิวธรรมดา หมายถึง
คิวที่มีการนำข้อมูลเข้าทางท้ายคิว (Rear) และนำข้อมูลออกหางคิว (Front)
โดยถ้าท้ายคิวไปอยู่ที่ตำแหน่งท้ายสุดของคิวแล้ว
ถึงแม้จะมีช่องว่างเหลือที่หัวคิวก็ไม่สามารถนำข้อมูลใหม่ไปเก็บได้
จนกว่าจะนำข้อมูลในคิวออกให้หมดก่อนจึงเริ่มนำข้อมูลใหม่ไปเก็บได้
การนำข้อมูลเข้า Enqueue
žก่อนนำสมาชิกเข้าคิว
ต้องตรวจสอบว่าคิวเต็มหรือไม่ โดยที่ ถ้า rear = maxQ แสดงว่าคิวเต็ม (เมื่อ maxQ คือขนาดของคิว)
•การนำข้อมูลใหม่เข้ามาแถวคอย จะเพิ่มเข้ามาด้านหลัง•และจะนำเข้ามาเรื่อย ๆ จนเต็ม หรือเรียกว่า แถวคอยเต็ม (Queue Overflow)•ดังนั้นการนำสมาชิกเข้าคิว จึง เป็นการเพิ่มค่าพอยน์เตอร์ rear•หากมีสมาชิกในคิวเพียงค่าเดียวพอยน์เตอร์ rear และ front จะเท่ากัน
•การนำข้อมูลใหม่เข้ามาแถวคอย จะเพิ่มเข้ามาด้านหลัง•และจะนำเข้ามาเรื่อย ๆ จนเต็ม หรือเรียกว่า แถวคอยเต็ม (Queue Overflow)•ดังนั้นการนำสมาชิกเข้าคิว จึง เป็นการเพิ่มค่าพอยน์เตอร์ rear•หากมีสมาชิกในคิวเพียงค่าเดียวพอยน์เตอร์ rear และ front จะเท่ากัน
คิวลำดับความสำคัญ
หรือ แถวคอยเชิงบุริมภาพ (Priority
Queue)
•ใน คิวธรรมดา ข้อมูลที่เข้ามาก่อนจะมีสิทธิ์ออกก่อน
(First
In First Out:FIFO) อย่างไรก็ตาม
มีบางครั้งที่เราต้องยกให้สมาชิกบางประเภทได้ทำงานก่อนทั้งที่มาทีหลัง เช่น
การให้คิวงานที่เล็กกว่าได้ทำก่อน หรือ การให้สิทธิพิเศษแก่การทำงานบางประเภท
คิวลำดับความสำคัญทำให้เราสามารถประยุกต์ใช้คิวได้ดีขึ้น
เนื่องจากเพิ่มการให้ความสำคัญของสมาชิกที่แตกต่างกัน
ส่งผลให้เราสามารถจัดเรียงคิวได้ใหม่ให้เหมาะสมกับการทำงานได้
เราใช้คิวลำดับความสำคัญในการจัดการทำงานการตรวจนับ
การประยุกต์ใช้
Queue
ตัวอย่างการประยุกต์คิวมาใช้งานบนคอมพิวเตอร์
-การเข้าคิวของโปรเซสหรืองานต่าง
ๆ เพื่อรอการประมวลผลจากซีพียูตามลำดับ
-การแบ่งเวลา
(Time
Sharing) ด้วยการจำกัดตารางเวลาการประมวลผลของแต่ละโปรเซส
ส่งผลให้สามารถหมุนเวียนการประมวลผลในแต่ละโปรเซสสลับไปมาได้
ทำให้ดูเหมือนกับการประมวลผลงานหลาย ๆ อย่างได้ในเวลาเดียวกัน (Multitasking)
-การเข้าคิวเพื่อรอผลลัพธ์จากเครื่องพิมพ์
