by Jon Ripley, May 2006

A stack is a dynamic data structure operating on the principle of LIFO (Last In First Out). Items are added to and removed from the top of the stack. There are three operations that are applied to stacks, namely initialise, add to the stack (push) and remove from the stack (pull). Only the last item pushed to the stack is accessible.

Data structure


To describe the elements in the stack you need to define a data structure. This structure will contain the data pushed to the stack and information about the stack.

To declare the structure to hold items in the stack use code similar to the following:
      DIM node{ item, prev }
Here node.item is the item which is stored on the stack and node.prev is a pointer to the previous item pushed to the stack. Initially the pointer to the previous item (node.prev) is set to zero to indicate that there are no more items in the stack. The node{} structure can contain any data elements required. The structure must have a pointer to the previous item pushed on to the stack. The structure node{} always references the last item pushed to the stack.

Initialise stack


To initialise the stack use code similar to the following:
      head = 0
Every stack requires a pointer to the first item called the head. The head is initially set to zero to indicate an empty stack. When new items are pushed to and pulled from the stack the head pointer will be updated to point to the start of the stack.

Note: Do not access any members of the node{} structure when the head pointer is zero otherwise your program may crash.

Push to stack


To push an item onto the stack use code similar to the following:
      SYS "GlobalAlloc", 64, DIM(node{}) TO newNode
      !(^node{}+4) = newNode
      node.prev = head
      head = newNode
Here we call GlobalAlloc to allocate sufficient memory to store the new node, select the node and link it to the stack updating the head pointer to point to the newly added item. We must use GlobalAlloc to allocate memory instead of using DIM. Memory allocated with DIM cannot be freed when it is no longer required.

Here we can store the information we need in the stack using code similiar to the following:
      node.item = item

Pull from stack


To pull an item off the stack use the following code:
      IF head <> 0 THEN
        temp = head
        !(^node{}+4) = temp
        head = node.prev
        SYS "GlobalFree", temp
        !(^node{}+4) = head
      ENDIF
Here we select the item at the top of the stack (head), set the head pointer to point to the previous item pushed (node.prev) and deallocate the memory occupied by the discarded item. When all items are pulled from the stack the head pointer will again be set to zero to indicate an empty stack.

Note: To avoid memory wastage you should set all strings in the structure to NULL ("") before calling GlobalFree.

Destroy stack


To destroy a stack use the following code:
      WHILE head
        temp = head
        !(^node{}+4) = temp
        head = node.prev
        SYS "GlobalFree", temp
      ENDWHILE
      !(^node{}+4) = head
This operation iterates through the stack pulling items until the stack is empty. The core code is the same as when pulling a single item from the stack.

Counting the number of items in the stack


The layout of a stack in memory is similar to a singly-linked-list and we can use a standard linked list walking algorithm to count the number of items in the stack.

To count the number of items in the stack use the following code:
      count = 0
      current = head
      WHILE current
        count += 1
        !(^node{}+4) = current
        current = node.prev
      ENDWHILE
      !(^node{}+4) = head
Here count will contain the number of items in the stack.

Example code


The following program demonstrates using a stack:
      REM Initialise the stack
      DIM node{ item, prev }
      head = 0
 
      REM Push the numbers 0 to 10 on the stack
      FOR i%=0 TO 10
        PROCpush(node{}, head)
        node.item = i%
      NEXT
 
      REM Pull and display the numbers from the stack
      WHILE head
        PRINT node.item
        PROCpull(node{}, head)
      ENDWHILE

Procedures


These procedures can be used manage stacks in your program:
      DEF PROCpush(RETURN node{}, RETURN head)
      LOCAL newNode
      SYS "GlobalAlloc", 64, DIM(node{}) TO newNode
      !(^node{}+4) = newNode
      node.prev = head
      head = newNode
      ENDPROC
 
      DEF PROCpull(RETURN node{}, RETURN head)
      IF head THEN
        LOCAL temp
        temp = head
        !(^node{}+4) = temp
        head = node.prev
        SYS "GlobalFree", temp
        !(^node{}+4) = head
      ENDIF
      ENDPROC