คิวลำดับความสำคัญเป็นประเภทของคิวที่องค์ประกอบจะถูกแทรกหรือลบตามลำดับความสำคัญที่กำหนดให้กับองค์ประกอบเหล่านั้น โดยที่ระดับความสำคัญเป็นค่าจำนวนเต็มที่อยู่ในช่วง 0-10 โดยที่ 0 แสดงองค์ประกอบที่มีลำดับความสำคัญสูงสุด และ 10 แสดงองค์ประกอบด้วย ลำดับความสำคัญต่ำสุด มีกฎสองข้อที่ปฏิบัติตามสำหรับการนำคิวลำดับความสำคัญไปใช้ -
- ข้อมูลหรือองค์ประกอบที่มีลำดับความสำคัญสูงสุดจะถูกดำเนินการก่อนข้อมูลหรือองค์ประกอบที่มีลำดับความสำคัญต่ำสุด
- หากองค์ประกอบสองรายการมีลำดับความสำคัญเท่ากันกว่าองค์ประกอบนั้นจะถูกดำเนินการตามลำดับ องค์ประกอบนั้นจะถูกเพิ่มในรายการ
มีโครงสร้างข้อมูลหลายแบบที่สามารถใช้เพื่อนำลำดับความสำคัญไปใช้ เช่น กอง คิว และรายการที่เชื่อมโยง ในบทความนี้ เราจะอธิบายโครงสร้างข้อมูลคิว มีสองวิธีที่สามารถใช้เพื่อนำลำดับความสำคัญไปใช้เช่น −
- รักษาคิวสำหรับหลายลำดับความสำคัญในอาร์เรย์เดียว
วิธีหนึ่งในการใช้คิวลำดับความสำคัญคือการรักษาคิวสำหรับลำดับความสำคัญแต่ละรายการ เราสามารถเก็บหลายคิวเหล่านี้ไว้ในอาร์เรย์เดียว โดยที่แต่ละคิวจะมีพอยน์เตอร์สองตัวคือด้านหน้าและด้านหลัง ในคิว ตัวชี้ด้านหน้าใช้เพื่อแทรกองค์ประกอบในคิวและจะเพิ่มขึ้น 1 เมื่อใดก็ตามที่องค์ประกอบถูกแทรกและตัวชี้อีกตัวอยู่ด้านหลังซึ่งใช้เพื่อลบหรือลบองค์ประกอบออกจากคิวซึ่งจะลดลง 1 เมื่อใดก็ตามที่องค์ประกอบ จะถูกลบออกจากคิว ในท้ายที่สุด เราสามารถกำหนดจำนวนขององค์ประกอบในคิวผ่านตำแหน่งของพอยน์เตอร์สองตัวได้
- ในการนำเสนอประเภทนี้ เราจำเป็นต้องเลื่อนพอยน์เตอร์เพื่อให้มีที่ว่างสำหรับการแทรกองค์ประกอบใหม่ ซึ่งจะทำให้ซับซ้อนทั้งในแง่ของเวลาและพื้นที่
- รักษาคิวสำหรับลำดับความสำคัญแต่ละรายการในอาร์เรย์เดียว
ในวิธีการประเภทนี้ เราสร้างลูกศรแยกสำหรับแต่ละองค์ประกอบ ทุกคิวจะถูกนำไปใช้เป็นอาร์เรย์แบบวงกลมและมีตัวแปรพอยน์เตอร์สองตัว นั่นคือ ด้านหน้าและด้านหลัง. องค์ประกอบที่มีหมายเลขลำดับความสำคัญจะถูกแทรกในคิวที่เกี่ยวข้องเช่นเดียวกัน หากเราต้องการลบองค์ประกอบออกจากคิว องค์ประกอบนั้นจะต้องเป็นองค์ประกอบจากคิวที่มีลำดับความสำคัญสูงสุด จำนวนเต็มที่มีลำดับความสำคัญต่ำสุดระบุลำดับความสำคัญสูงสุด (0)
หมายเหตุ - หากแต่ละคิวมีขนาดเท่ากัน เราก็สามารถสร้างอาร์เรย์สองมิติเดียวแทนที่จะสร้างอาร์เรย์หนึ่งมิติหลายรายการ
อัลกอริธึมสำหรับการดำเนินการแทรกในคิวลำดับความสำคัญ
insert(queue, data, priority) If(queue->Rear[priority] = MAX-1 AND queue->Front[priority] = 0) OR (queue->Rear[priority] +1 =queue->Front[priority]) Print Overflow End IF queue->Rear[priority - 1] = MAX-1 Set queue->Rear[priority - 1] = 0 Else Set queue->Rear[priority] = queue->Rear[priority - 1] +1 End Set queue->CQueue[priority - 1] [queue->Rear[priority - 1] = data IF queue->Front[priority - 1] = -1 Set queue->Front[priority - 1] = 0 End
อัลกอริธึมสำหรับการดำเนินการแทรกในคิวลำดับความสำคัญ
delete(queue) Set flag = 0, priority = 0 While priority <= MAX-1 IF NOT queue->Front[priority] = -1 Set flag = 1 Set value = queue->CQueue[priority][queue->Front[priority]] IF queue->Front[priority] = queue->Rear[priority] Set queue->Front[priority] = queue->Rear[priority] = -1 Else IF queue->Front[priority] = MAX-1 Set queue->Front[priority] = 0 Else Set queue->Front[priority] = queue->Front[priority] + 1 End End Break End Set priority = priority + End If flag = 0 Print underflow Else Return value End
