FIFO and LIFO stacks

from the Artful SQL Server & Access Tips List

You're probably familiar with basic data structures such as stack, queue, and linked list, but you may not have implemented them in SQL Server. Before I show you how to implement a stack, I'll discuss why you may want to do it. There are two reasons: persistence (the front end might crash, taking out the in-memory stack) and the audit trail (if anything goes wrong, we can investigate the log to determine what happened and why). Requirements A stack is a list. There are two kinds of stacks: FIFO (first in, first out) and LIFO (last in, first out). In most cases, you can only perform two operations on a stack: push (add one item) and pop (remove one item). Occasionally, you see a third operation called peek, which allows you to examine the next item to pop, but doesn't actually pop it. Implementing a FIFO stack We'll implement a FIFO stack to emulate an assembly line at an auto factory. First, we need a table that will serve as our stack. We'll call it AssemblyLine. The first car into the assembly line at one end of the line is also the first car to roll off the line at the other end:

-- Listing A.
CREATE TABLE [dbo].[AssemblyLine] (
    [ItemNumber] [int] NOT NULL ,
    [SerialNumber] [char] (10) NOT NULL
)
GO
ALTER TABLE [dbo].[AssemblyLine] WITH NOCHECK ADD
    CONSTRAINT [PK_AssemblyLine] PRIMARY KEY  CLUSTERED
    (
        [ItemNumber]
    ) 
GO

In most cases, my natural instinct would be to make the primary key column an Identity column; but in this situation, our concern is with the absolute number of each car in the assembly line, so we can't risk the vagaries of an identity column (i.e., we have no real control over the next number issued). Now add a few rows to the table:

ItemNumber    SerialNumber
1             ABC
2             DEF
3             GHI
4             JKL
5             MNO

Next, we need two operations, which we'll implement as stored procedures. We'll call them push and pop:

CREATE PROCEDURE dbo.FIFO_Push (@SerialNumber CHAR (10) )
AS 
DECLARE @ItemNumber INTEGER
SELECT TOP 1 @ItemNumber = ItemNumber
FROM AssemblyLine 
ORDER BY ItemNumber DESC
INSERT INTO AssemblyLine( ItemNumber,SerialNumber ) 
VALUES( @ItemNumber + 1, @SerialNumber)
SELECT * FROM AssemblyLine WHERE ItemNumber = @ItemNumber + 1
GO
CREATE PROCEDURE dbo.FIFO_Pop 
AS 
DECLARE @ItemNumber INTEGER
SELECT TOP 1 @ItemNumber = ItemNumber
FROM AssemblyLine 
ORDER BY ItemNumber
SELECT * FROM AssemblyLine 
WHERE @ItemNumber = ItemNumber
DELETE FROM AssemblyLine WHERE @ItemNumber = ItemNumber
GO

Both procedures contain a SELECT statement to show you what happened. You can comment them out in production code. Since we have a few sample rows, now you can push and pop at will. Implementing a LIFO stack Given the code above, the push procedure is identical. We only need to add one word to the pop procedure. Can you see which word we need to add and where? Answer: Add DESC to the line that begins "SELECT TOP 1."

Last updated 22 May 2024

Return to the Artful SQL Server & Access Tips page