Queue
เป็นโครงสร้างข้อมูลแบบเชิงเส้นหรือลิเนียร์ลิสต์ ซึ่งมีลักษณะที่ว่า ข้อมูลที่นำเข้าไปเก็บก่อนจะถูกนำออกมาทำงานก่อน ส่วนข้อมูลที่เข้าไปเก็บทีหลังก็จะถูกนำออกมาใช้งานทีหลัง ขึ้นอยู่กับลำดับการเก็บข้อมูล จะ
เรียกลักษณะการทำงานแบบนี้ว่า เข้าก่อนออกก่อน หรือ First In First Out (FIFO) มีข้อกำหนดให้ชุดปฏิบัติการสามารถเพิ่มค่าเข้าไปในตอนท้ายของรายการเพียงด้านเดียว เรียกว่า ส่วนหลัง ( Rear ) และลบค่าในตอนต้นของรายการเพียงด้านเดียว เรียกว่า ส่วนหน้า ( Front )
การดำเนินการพื้นฐานของ Queue ได้แก่
- การนำข้อมูลเข้าสู่ Queue เรียกว่า enqueue
- การนำข้อมูลออกจาก Queue เรียกว่า dequeue
- การนำข้อมูลที่อยู่ตอนต้นของ Queue มาแสดง เรียกว่า queue front
- การนำข้อมูลที่อยู่ตอนท้ายของ Queue มาแสดง เรียกว่า queue rear
การนำข้อมูลเข้าสู่โครงสร้างคิว (enqueue)
เป็นกระบวนการอ่านข้อมูลจากภายนอกเข้าสู่โครงสร้างคิวทางด้านปลายที่พอยน์เตอร์ R ชี้อยู่ โดยพอยน์เตอร์ R จะเปลี่ยนตำแหน่ง ชี้ไปยังตำแหน่งที่ว่างตำแหน่งถัดไป ก่อนนำข้อมูลเข้าสู่โครงสร้างคิว
ข้อควรคำนึงถึง คือ ในขณะที่คิวเต็ม (Full Queues) หรือไม่มีช่องว่างเหลืออยู่ จะไม่สามารถนำข้อมูลเข้าไปเก็บในโครงสร้างคิวได้อีก ซึ่งจะทำให้เกิดปัญหา “Overflow” ขึ้น
"ขั้นตอนการนำข้อมูลเข้าสู่โครงสร้างคิว" มีดังนี้
1. เมื่อมีข้อมูลเข้าสู่คิว ให้ตรวจสอบว่าคิวเต็มหรือไม่ ถ้าคิวเต็มไม่ให้มีการรับข้อมูล
2. ถ้าคิวไม่เต็มให้เลื่อนตำแหน่งพอยน์เตอร์ R แล้วนำข้อมูลเข้าสู่คิว
3. ตรวจสอบเงื่อนไขว่าถ้าเป็นข้อมูลตัวแรกในคิว ให้เปลี่ยนพอยน์เตอร์ F ให้ชี้ค่าแรก
การนำข้อมูลออกจากโครงสร้างคิว (dequeue)
เป็นการลบข้อมูลออกจากโครงสร้างคิวทางด้านหน้า ของโครงสร้างคิว โดยมีพอยน์เตอร์ F เป็นพอยน์เตอร์ชี้บอกตำแหน่งที่ข้อมูลอยู่ เมื่อมีการลบข้อมูล ออกจากโครงสร้างคิวเรียบร้อยแล้ว พอยน์เตอร์ F จะเลื่อนตำแหน่ง ไปยังตำแหน่งถัดไป
ข้อควรคำนึงถึง คือ เมื่อคิวว่าง (Empty queue) หรือไม่มีข้อมูลเหลืออยู่ จะไม่สามารถนำข้อมูลออกจากคิวได้อีก ซึ่ง จะทำให้เกิดปัญหา “underflow” ขึ้น
"ขั้นตอนการนำข้อมูลออกจากโครงสร้างคิว" มีดังนี้
1. ตรวจสอบว่าเป็นคิวว่าง (Empty Queues) หรือไม่
2. ถ้าคิวไม่ว่างให้นำข้อข้อมูลออกจากคิว ณ ตำแหน่งที่ F ชี้อยู่ จากนั้นก็ทำการเลื่อนตำแหน่งพอยน์เตอร์ F ไปยังตำแหน่งถัดไป
3. ถ้ามีข้อมูลอยู่เพียงตัวเดียว ให้กำหนดให้พอยน์เตอร์ F และ R เป็นศูนย์ (0)
การแสดงข้อมูลตอนต้นของคิว (Queue Front)
เป็นการนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดง แต่จะไม่มีการเอาข้อมูลออกจากคิว ซึ่งประโยชน์ของมันก็คือ สามารถทำให้เรารู้ว่า คิวถัดไป (next queue) คืออะไร
การแสดงข้อมูลตอนท้ายของคิว (Queue Rear)
เป็นการนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดง แต่จะไม่ทำการเพิ่มข้อมูลเข้าไปในคิว ซึ่งประโยชน์ของมันก็คือ สามารถทหให้เรารู้ว่าลำดับสุดท้ายคืออะไร ลำดับที่เท่าไร
การแทนที่ข้อมูลของคิว สามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์ ประกอบไปด้วย 2 ส่วน คือ Head Node ได้แก่ Front, Rear และจำนวนสมาชิกในคิว และ Data Node ได้แก่ ข้อมูล และพอยน์เตอร์ที่ชี้ไปยังข้อมูลตัวถัดไป
การดำเนินการเกี่ยวกับคิว ได้แก่
1.) Create Queue เป็นการจัดสรรหน่วยความจำให้กับ Head Node และให้ค่า pointer ทั้ง 2 ตัวมีค่าป็น null และจำนวนสมาชิกเป็นศูนย์
2.) Enqueue เป็นการเพิ่มข้อมูลเข้าไปในคิว ซึ่ง pointer rear จะเปลี่ยน
3.) Dequeue เป็นการนำข้อมูลออกจากคิว ซึ่ง pointer front จะเปลี่ยน
4.) Queue Front เป็นการนำข้อมูลที่อยู่ตอนต้นของคิวมาแสดง
5.) Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
6.) Empty Queue เป็นการตรวจสอบว่าคิวว่างหรือไม่
7.) Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่
8.) Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว
9.) Destroy Queue เป็นการลบข้อมูลทั้งหมดที่อยู่ในคิว วิธีการคือ ต้องทำการ Dequeue ทีละตัว แล้วจึงจะ Destroy
2. การแทนที่ข้อมูลของคิวแบบอะเรย์
จากการดำเนินการกับโครงสร้างคิวจะเห็นได้ว่า โครงสร้างคิวยังไม่มีประสิทธิภาพเพียงใดนัก เนื่องจากเมื่อมีการเพิ่มข้อมูลจนเต็ม (Full Queue) และมีการลบข้อมูลออกจากโครงสร้างคิวแล้ว พอยน์เตอร์ F จะยังคงอยู่ที่ตำแหน่งเดิม ไม่สามารถเปลี่ยนไปที่ตำแหน่งเริ่มต้นใหม่ได้จนกว่าจะมีการลบข้อมูลออกจากคิวหมดแล้ว (Empty Queue) จึงจะสามารถกำหนดพอยน์เตอร์ข้อมูล F และ R ให้กลับไปยังตำแหน่งเริ่มต้นใหม่ได้ ทำให้เสียพื้นที่ของโครงสร้างคิวในตำแหน่งที่พอยน์เตอร์ F ผ่านมา ไปเนื่องจากต้องรอให้ตำแหน่งของพอยน์เตอร์ F ไปยังตำแหน่งสุดท้ายก่อน (เมื่อคิวว่าง) จึงจะสามารถใช้พื้นที่ดังกล่าวได้
จากสาเหตุดังกล่าวมาแล้ว จึงได้มีการพัฒนาโครงสร้างคิวให้มีความยืดหยุ่นมากขึ้น สามารถใช้งานพื้นที่โครงสร้างคิวได้อย่างเต็มประสิทธิภาพ โดยการนำปลายทางของโครงสร้าง คือ ด้านหน้าของโครงสร้าง (Front) และด้านหลังของโครงสร้าง (Rear) มาเชื่อมต่อกันในลักษณะวงกลม เรียกว่า คิววงกลม (Circular Queue)
ลักษณะโครงสร้างของคิวแบบวงกลม
ในกรณีที่เป็นคิวแบบวงกลม คิวจะเต็มก็ต่อเมื่อมีการเพิ่มข้อมูลเข้าไปในคิวเรื่อยๆ จนกระทั่ง rear มีค่าน้อยกว่า front อยู่ 1 ค่า คือ rear = front - 1
การประยุกต์ใช้คิว
- ใช้ในระบบปฏิบัติการ เช่น การจัดคิวโปรเซสเข้าใช้ซีพียู การจัดคิวงานพิมพ์
- ใช้ในเราเตอร์ เช่น การจัดคิวให้กับแต่ละ packet ก่อนส่งเข้าสาย
- ใช้ในการให้บีการลูกค้า คืด ต้องวิเคราะห์จำนวนลูกค้าในคิวที่เหมาะสม ว่าควรเป็นเท่าใด เพื่อให้ลูกค้าเสียเวลาน้อยที่สุด
- การเขียนโปรแกรมเพื่อจำลองแบบของสนามบิน จะใช้โครงสร้างข้อมูลแบบคิว แทนคิวของเครื่องบิน ที่จะรอขึ้นหรือรอลง แต่ค่อนข้างเป็นโปรแกรมที่ซับซ้อน ดังสภาพความเป็นจริงที่ว่า " สนามบินมีขนาดเล็กแต่มีเครื่องบินขึ้นลงจนวนมาก มีทางวิ่ง(runway)เพียงทางเดียว ณ เวลาใดๆ เครื่องบิน จะขึ้นหรือจะลงสามารถเป็นไปได้กรณีเดียวเท่านั้น และเพียงครั้งละเครื่องเดียวด้วย เครื่องบินที่มาถึงสนามบิน พร้อมที่จะขึ้นหรือลง ณ เวลาใด ๆ ก็ได้ ดังนั้น ณ เวลาใด ๆ ทางวิ่งอาจจะว่างหรืออาจจะมีเครื่องบินกำลังขึ้น หรือลงอยู่ก็ได้ และอาจจะมีเครื่องบินหลายลำที่รอขึ้นและรอลง จึงมีคิว 2 คิวคือคิวขึ้น(takeoff ) และคิวลง(landing)เครื่องเหล่านั้น หากว่าการรอนั้นบนพื้นดินจะดีกว่าบนอากาศ สนามบินขนาดเล็กจึงต้อง มีการให้เครื่องบินขึ้นต่อเมื่อไม่มีเครื่องบินลง หลังจากได้รับสัญญาณร้องขอจากเครื่องบินลำใหม่เพื่อจะลงหรือขึ้น" โปรแกรมการจำลองแบบจะให้บริการเครื่องบินที่อยู่ในตำแหน่งหัวคิวของคิวรอลงก่อนและถ้าคิวที่รอลงว่าง จึงอนุญาตให้เครื่องบินรอขึ้นขึ้นได้ โปรแกรมจำลองแบบนี้สามารถจะทำงานได้ตลอดเวลา
ไม่มีความคิดเห็น:
แสดงความคิดเห็น