3.10 Implementing a Stack

3.10.1 Problem

You need to implement a stack data structure in SQL. With respect to our example, you need to build an interface to a processing machine that adds and removes containers to and from the production line. The production line should be handled as a stack. Therefore, you must implement the POP, PUSH, and TOP functions.

3.10.2 Solution

Use the ProductionLine table as a stack. The following sections show how to implement the various stack functions using SQL. Notice our use of the ContainerId column to keep stack elements in their proper order. Each new element pushed onto the stack gets a higher ContainerId value than the previous element. The top of the stack is defined as the row with the highest ContainerId value.

3.10.2.1 TOP function in SQL

Implementing the TOP function is very easy. You just use the SELECT statement to retrieve the most recently added row in the stack, which, by definition, will be the row with the highest ContainerId value.

SELECT TOP 1 * FROM ProductionLine ORDER BY ContainerId DESC

If you want to embed the query into a procedure and expand it, use the following framework:

CREATE PROCEDURE TopProduction
AS
SELECT TOP 1 * FROM ProductionLine ORDER BY ContainerId DESC

3.10.2.2 POP function in SQL

The POP function is implemented here as a procedure to give you a framework that you can build on. The first statement is our TOP function, which retrieves the topmost element in the stack. The second select prints that element. The delete statement then removes the element from the stack.

CREATE PROCEDURE Pop 
AS 
DECLARE @id INTEGER

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

3.10.2.3 PUSH function in SQL

The PUSH function adds a new element to the stack. The first SELECT retrieves the top Id. Then the new element is inserted. The last SELECT in the procedure prints the new top element so that you can verify that it was added correctly.

CREATE PROCEDURE Push @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.10.3 Discussion

SQL is very convenient for the implementation of linear data structures. In this recipe, we work with an often encountered problem, in which serialization is required, but for which there is no need for a full-sized transactional system.

The code shown in our solution is a simplified version of a real-world system. If you want to use the concept in a live system, make sure that you make the procedures transactional. In addition, if more than one user is using the POP and PUSH functions, use some increment mechanism other than the plain MAX function used in our solution. For example, you can use SQL server's native solutions, such as Microsoft's IDENITY or UNIQUEIDENTIFIER datatypes to ensure uniqueness of id values. Be careful: such solutions can be costly and are not always applicable.

In order to test the functions, try the sequence in the following example:

PUSH 120


ContainerId Purity      
----------- ----------- 
13          120


PUSH 130


ContainerId Purity      
----------- ----------- 
14          130


POP

ContainerId Purity      
----------- ----------- 
14          130


POP

ContainerId Purity      
----------- ----------- 
13          120

As you can see, the functions work as expected, and they add or remove the elements on the stack.

Our sample functions simply display data retrieved from the stack, but you could easily store the return values in variables for further manipulation.

Following this pattern, you can implement stack mechanisms using any SQL table, as long as there is a column such as ContainerId that you can use to establish an ordering of the stack elements.