=====Stacks using structures=====

//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:\\ 
<code bb4w>
        DIM node{ item, prev }
</code>
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:\\ 
<code bb4w>
        head = 0
</code>
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:\\ 
<code bb4w>
        SYS "GlobalAlloc", 64, DIM(node{}) TO newNode
        !(^node{}+4) = newNode
        node.prev = head
        head = newNode
</code>
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:\\ 
<code bb4w>
        node.item = item
</code>
\\ 
==== Pull from stack ====
\\  To pull an item off the stack use the following code:\\ 
<code bb4w>
        IF head <> 0 THEN
          temp = head
          !(^node{}+4) = temp
          head = node.prev
          SYS "GlobalFree", temp
          !(^node{}+4) = head
        ENDIF
</code>
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:\\ 
<code bb4w>
        WHILE head
          temp = head
          !(^node{}+4) = temp
          head = node.prev
          SYS "GlobalFree", temp
        ENDWHILE
        !(^node{}+4) = head
</code>
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 [[/Linked%20lists%20using%20structures|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:\\ 
<code bb4w>
        count = 0
        current = head
        WHILE current
          count += 1
          !(^node{}+4) = current
          current = node.prev
        ENDWHILE
        !(^node{}+4) = head
</code>
Here **count** will contain the number of items in the stack.\\ \\ 
==== Example code ====
\\  The following program demonstrates using a stack:\\ 
<code bb4w>
        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
</code>
\\ 
==== Procedures ====
\\  These procedures can be used manage stacks in your program:\\ 
<code bb4w>
        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
</code>