3.11 Implementing Queues

3.11.1 Problem

You need to implement a queue with standard operations, such as TOP, ENQUEUE, and DEQUEUE. With respect to our example, you wish to implement the same sort of functionality as in the previous recipe, but this time you wish to treat the production line as a queue, not as a stack.

3.11.2 Solution

Use the ProductionLine table as a queue. The following sections then show you how to implement the standard queuing functions.

3.11.2.1 TOP function in SQL

SELECT TOP 1 *  FROM ProductionLine ORDER BY ContainerId ASC

3.11.2.2 DEQUEUE function in SQL

CREATE PROCEDURE dequeue 
AS 
DECLARE @id INTEGER

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

3.11.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.11.3 Discussion

As you can see, the queue mechanisms are very similar to the stack mechanisms. In fact, the only difference is in the TOP function. When working with queues, the TOP function always looks for the oldest element in the table, not for the most recently added element. We accomplished this by ordering ASC rather than DESC.

To create the DEQUEUE function, we took the POP function that we used for our stack solution and changed the TOP statement (the first SELECT) so that the function became a DEQUEUE function. The PUSH and ENQUEUE functions actually use the same code, because the process for adding an element to a queue is the same as for adding an element to a stack.

Please note that since we are adding elements to the top and removing them from the bottom, the ContainerId value is always increasing. If, when implementing a queue, you think you might possibly run out of index values, you'll need to code some sort of reset mechanism to wrap the index back around to the beginning once its upper limit is reached.