DTS06/20/08/2009

สรุป เรื่อง Queues

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

ลักษณะของคิวนั้นจะมีปลายสองข้าง ซึ่งข้างหนึ่งจะเป็นช่องทางสำหรับข้อมูลเข้าที่เรียกว่า Rear และอีกข้างหนึ่งซึ่งเป็นช่องทางสำหรับข้อมูลออก เรียกว่า Front ในการทำงานกับคิวที่ต้องมีการนำข้อมูลเข้าและออกนั้นจะต้องมีการตรวจสอบว่าคิวว่างหรือไม่เมื่อต้องการนำข้อมูลเข้า เพราะหากว่าคิวเต็มก็จะไม่สามารถทำการนำข้อมูลเข้าได้ เช่นเดียวกันเมื่อต้องการนำข้อมูลออกก็ต้องตรวจสอบอีกด้วยเช่นกันว่า ในคิวนั้นมีข้อมูลอยู่หรือไม่ หากคิวไม่มีข้อมูลก็จะไม่สามารถนำข้อมูลออกได้ เช่นเดียวกัน

การกระทำกับคิว การเพิ่มข้อมูลเข้าไปในคิวจะกระทำที่ตำแหน่ง Rrar หรือท้ายคิวและก่อนที่จะเพิ่มข้อมูลจะต้องตรวจสอบก่อนว่าคิวเต็มหรือไม่ โดยการเปรียบเทียบค่า Rear ว่าเท่ากับค่า Max queue หรือไม่ หากว่าค่า Rear=Max queue แสดงว่าคิวเต็มไม่สามารถเพิ่มข้อมูลเข้าไปได้ แต่หากไม่เท่า แสดงว่าคิวยังมีที่ว่างสามารถเพิ่มข้อมูลได้ เมื่อเพิ่มข้อมูลเข้าไปแล้ว ค่า Rear ก็จะเป็นค่าตำแหน่งท้ายคิวใหม่
ส่วนในการนำข้อมูลออกจากคิวจะกระทำที่ตำแหน่ง Front หรือส่วนที่เป็นหัวของคิว โดยก่อนที่จะนำข้อมูลออกจากคิวจะต้องมีการตรวจสอบก่อนว่ามีข้อมูลอยู่ในคิวหรือไม่ หากไม่มีข้อมูลในคิวหรือคิวว่างก็จะไม่สามารถนำข้อมูลออกจากคิวได้

คิวแบบวงกลม (Circular Queue) จะมีลักษณะเหมือนคิวธรรมดา คือ จะมีตัวชี้ Front และ Rear ที่แสดงตำแหน่งหัวคิวและท้ายคิวตามลำดับ โดยมี Front และ Rear จะมีการเลื่อนลำดับทุกครั้งเมื่อมีการนำข้อมูลเข้าและออกจากคิว แต่จะแตกต่างจากคิวธรรมดาตรงที่ว่า คิวธรรมดาเมื่อ Rear ชี้ตำแหน่งสุดท้ายของคิว จะทำให้เพิ่มข้อมูลเข้าไปในคิวอีกไม่ได้ เนื่องจากเนื่องจาก ค่า Rear=Max queue ซึ่งแสดงว่าคิวนั้นเต็มไม่สามารถเพิ่มข้อมูลเข้าไปได้อีก ทั้งๆ ที่ยังมีเนื้อที่ของคิวเหลืออยู่ก็ตาม ทำให้การใช้เนื้อที่ของคิวไม่มีประสิทธิภาพ
สำหรับคิวแบบวงกลม จะมีวิธีการจัดการกับปัญหานี้ คือ เมื่อมีข้อมูลเพิ่มเข้ามาในคิว ในลักษณะดังกล่าว คือ ขณะที่ Rear ชี้ตำแหน่งสุดท้ายของคิว ถ้าหากมีการเพิ่มค่าของ Rear จะสามารถวนกลับมาชี้ตำแหน่งแรกสุดของคิวได้ ซึ่งจะทำให้คิวมีลักษณะเป็นแบบวงกลมแสดงคิวแบบวงกลมที่ Rear สามารถวนกลับมาชี้ที่ตำแหน่งแรกสุดของคิว