A last in first off stack can be implemented using a linked list.  One possible application for this type of stack would be an 'undo' function in a program.  Items are pushed onto the stack from the bottom, and therefore, the last item pushed is always the first item on the linked list.  Normally when users press 'undo' the change that is undone is always the last item changed which would be the item at the very bottom of the LIFO stack.

You can download the source as a text file by clicking here -> LIFO_stack_push_pop.txt

For this example we will create a stack containing only a simple integer in a record.  The linked list consists of a record containing the integer and the pointer to the next item in the linked list.  

        | integer | pointer |

The type declaration would be something like what follows.

type    

   link=^node;  {last on first off undo linked list stack}

   node=record i:integer; nextlink:link end;

In the variable declaration section we will declare a pointer 'head' which will point to the first item on the stack.  A temp pointer will be used to create any new items to be inserted on the stack.

var

 head, temp:link;

The head should be initialized to point to 'nothing' (nil).  If you are using a form then setting the head to nil in the FormCreate procedure would be a good idea.

head:=nil;

To insert an item onto the LIFO stack we simply push it onto the bottom of the stack.  In the first instance we have the head pointer pointing to nil.

| head | ­> nil

To insert an item we first call New to create a new record.  Temp is now pointing at this new record containing a field for an integer (field name i) and a pointer to the next record on the linked list.

New(temp);   temp ­> | i | nextlink |

We insert an integer (in this example) into the 'i' portion of the record.  We will assume that the integer was passed to the function in the variable 'c'.

temp^.i:=c;

What this syntax means is in the 'i' field of the record that temp is pointing to insert the value of the variable c.

Next we set the 'nextlink' pointer of the temp record we just created to be equal to the nextlink pointer of the head of the linked list.  In the case of the first variable inserted into the LIFO stack head is pointing to nil so setting the nextlink pointer of the temp record sets it equal to nil.

temp^.nextlink:=head;

Finally to complete the structure we now point head at the record we just created by making head equal to the value in the pointer temp.

head:=temp;

So the list now has the following form.  Let us suppose the value in 'c' was 12.

head ­> | 12 | nextlink | ­> nil

If we repeat the process and this time push the value '56' onto the LIFO stack the process would look like this...

When we first create the new temp record the '56' is hanging in space.

head ­> | 12 | nextlink | ­> nil

       | 56 | nextlink |

We then set the 'nextlink field' of the record holding the 56 to point to the record holding the 12 by setting the nextlink of the 56 record equal to pointer in the head.  Now both the head and the 56 record are pointing at the 12 record.

             head ­>  

                         12 | nextlink | ­> nil

| 56 | nextlink | ­>

Now that we safely have the 56 record pointing to the 12 record we can attach the 56 record to the head.  To complete the push onto the stack we now set head to point to the 56 record, and this record has now become the 'last in' record pushed onto the bottom of the LIFO stack.

head ­>   | 56 | nextlink | ­>  | 12 | nextlink | ­> nil

You will notice how the end of the list always terminates with nil if we remember to initialize the head pointer to nil before using the stack.  

The code that implements the push is simple and follows below.  The variable 'c' is the item we will be pushing onto the stack.

procedure TForm1.LIFOPush(c:integer);  { new(undohead);  undohead^.unextlink:=nil; }

begin

new(temp);

temp^.i:=c;

temp^.nextlink:=head;

head:=temp;

end;

Note that if you have more than one LIFO stack then you can include a second variable in the procedure call including the value of the head pointer for the stack you want to reference.

procedure TForm1.LIFOPush(c:integer; head:link);

To 'pop' an item off the bottom of the stack we will use a function that returns the value of the integer that was 'popped' as its result.  '56' is the item at the bottom of the stack in this example so we will pop '56' off the stack.  To 'pop' an item we first set result equal to the value of the integer field of the record that the head is pointing to, and then we set temp equal to the value of head (so that temp is pointing to the 56 record.  We then set head equal to the nextlink field of the 56 record that head is pointing to, and then we dispose of the 56 record using the temp pointer.

result:=head^.i;  {head is pointing to the record containing 56 so the function result:=56}

We then set both head and temp to point to the 56 record.

temp:=head;

head ­>

          | 56 | nextlink| ­> | 12 | nextlink | ­> nil

temp ­>

Next we set head equal to the nextlink field of the 56 record.

head:=head^.nextlink { set head equal to the value of the nextlink field pointed to by head}

Head is now pointing to 12 and temp is now pointing to the 56 record.

head ­> | 12 | nextlink | ­> nil

temp ­> | 56 | nextlink |

We have extracted the value 56 as the result of the function, and we have head pointing to '12' and temp pointing to 56 so the item has been 'popped' off the stack and it is now safe to dispose of the 56 record pointed to by temp.

Dispose(temp);

The function to pop an item off the LIFO stack would then take the following form.  You can call the function with the head pointer to the LIFO stack.  In this example the function will return the value of the integer popped off the stack.

function LIFOPop(head:link):integer;

result:=head^.i;

temp:=head;

head:=head^.nextlink;

Dispose(temp);

end;