3.12 Implementing Priority Queues

3.12.1 Problem

You need to implement priority-based queues. In our example, the higher the purity index, the higher the priority. For these queues, you want to implement standard operations such as TOP, ENQUEUE, or DEQUEUE.

3.12.2 Solution

As with stacks and regular queues, we can implement the priority queue in the ProductionLine table.

3.12.2.1 TOP function in SQL

SELECT TOP 1 *  FROM ProductionLine ORDER BY Purity DESC

3.12.2.2 DEQUEUE function in SQL

CREATE PROCEDURE dequeue 
AS 
DECLARE @id INTEGER

SELECT TOP 1 @id=ContainerId FROM ProductionLine ORDER BY Purity DESC
SELECT * FROM ProductionLine WHERE @id=ContainerId
DELETE FROM ProductionLine WHERE @id=ContainerId

3.12.2.3 ENQUEUE function in SQL

CREATE PROCEDURE enqueue @Purity INTEGER 
AS 
DECLARE @id INTEGER

SELECT TOP 1 @id=ContainerId FROM ProductionLine ORDER BY ContainerId DESC
INSERT INTO ProductionLine(ContainerId,Purity) VALUES(@id+1, @Purity)
SELECT * FROM ProductionLine WHERE ContainerId=@id+1

3.12.3 Discussion

Priority queues use a framework almost identical to that used for stacks and regular queues. The difference, again, is only in how the TOP function is implemented. When you adjust TOP to look at the queue in terms of priority, in our case at the Purity column, all the other pieces fall into place. The ENQUEUE function is the same as for regular queues. Except for the use of a priority-based TOP function, the DEQUEUE function is also the same as that for regular queues.

When you use a table as a priority queue, the ENQUEUE function can no longer ensure a monotonically increasing index (as is the case with stacks and queues). That's because the DEQUEUE function takes elements out of the queue based on their priority and not their index. For example, if you have 10 elements identified with index values 1 through 10 and the fifth element is removed because it has the highest priority, there will be a gap in the index. But when you add a new element, the ENQUEUE function will not fill that gap, but rather add the new element with an index value of 11. It's easy to overlook this behavior, which can cause some confusion, so keep it in mind as you work with priority queues.