BBC BASIC Programmers' Reference

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.

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.

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.

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

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.

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.

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.

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

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