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