Data Management

Implementing a FIFO and a LIFO stack in SQL Server

Arthur Fuller discusses why you may want to implement a stack in SQL Server--namely, persistence and the audit trail--and then he shows you how to implement a FIFO (first in, first out) and a LIFO (last in, first out) stack.

Even though you're probably familiar with the basic data structures such as stack, queue, and linked list, you may not have implemented these structures in SQL Server. Before I show you how to implement a stack, I'll discuss why you may want to implement one.

There are two reasons why you might want to implement a stack: 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). Granted, some front-end languages offer persistent objects, but this is a column about SQL.

Reviewing the 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. View the code in Listing A.

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, as in Listing B.

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

Note: Both procedures contain a SELECT statement to show you what happened. This is unnecessary in the 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."

TechRepublic's free SQL Server newsletter, delivered each Tuesday, contains hands-on tips that will help you become more adept with this powerful relational database management system. Automatically subscribe today!

Editor's Picks

Free Newsletters, In your Inbox