BBC BASIC Programmers' Reference

User Tools

Site Tools

Trace: • fast_variables
stacks_20using_20structures

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Next revision		Previous revision
stacks_20using_20structures [2018/03/31 13:19] – external edit 127.0.0.1stacks_20using_20structures [2024/01/05 00:21] (current) – external edit 127.0.0.1
Line 4: Line 4:
 ==== Data structure ==== ==== 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:\\  \\  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 }         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.\\ \\  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 ==== ==== Initialise stack ====
 \\  To initialise the stack use code similar to the following:\\  \\  To initialise the stack use code similar to the following:\\ 
 +<code bb4w>
         head = 0         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.\\ \\  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 ==== ==== Push to stack ====
 \\  To push an item onto the stack use code similar to the following:\\  \\  To push an item onto the stack use code similar to the following:\\ 
 +<code bb4w>
         SYS "GlobalAlloc", 64, DIM(node{}) TO newNode         SYS "GlobalAlloc", 64, DIM(node{}) TO newNode
         !(^node{}+4) = newNode         !(^node{}+4) = newNode
         node.prev = head         node.prev = head
         head = newNode         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:\\  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         node.item = item
 +</code>
 \\  \\ 
 ==== Pull from stack ==== ==== Pull from stack ====
 \\  To pull an item off the stack use the following code:\\  \\  To pull an item off the stack use the following code:\\ 
 +<code bb4w>
         IF head <> 0 THEN         IF head <> 0 THEN
           temp = head           temp = head
Line 28: Line 37:
           !(^node{}+4) = head           !(^node{}+4) = head
         ENDIF         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.\\ \\  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 ==== ==== Destroy stack ====
 \\  To destroy a stack use the following code:\\  \\  To destroy a stack use the following code:\\ 
 +<code bb4w>
         WHILE head         WHILE head
           temp = head           temp = head
Line 38: Line 49:
         ENDWHILE         ENDWHILE
         !(^node{}+4) = head         !(^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.\\ \\  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 ==== ==== 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:\\  \\  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         count = 0
         current = head         current = head
Line 49: Line 62:
         ENDWHILE         ENDWHILE
         !(^node{}+4) = head         !(^node{}+4) = head
 +</code>
 Here **count** will contain the number of items in the stack.\\ \\  Here **count** will contain the number of items in the stack.\\ \\ 
 ==== Example code ==== ==== Example code ====
 \\  The following program demonstrates using a stack:\\  \\  The following program demonstrates using a stack:\\ 
 +<code bb4w>
         REM Initialise the stack         REM Initialise the stack
         DIM node{ item, prev }         DIM node{ item, prev }
Line 67: Line 82:
           PROCpull(node{}, head)           PROCpull(node{}, head)
         ENDWHILE         ENDWHILE
 +</code>
 \\  \\ 
 ==== Procedures ==== ==== Procedures ====
 \\  These procedures can be used manage stacks in your program:\\  \\  These procedures can be used manage stacks in your program:\\ 
 +<code bb4w>
         DEF PROCpush(RETURN node{}, RETURN head)         DEF PROCpush(RETURN node{}, RETURN head)
         LOCAL newNode         LOCAL newNode
Line 88: Line 105:
         ENDIF         ENDIF
         ENDPROC         ENDPROC
 +</code>
stacks_20using_20structures.1522502384.txt.gz · Last modified: 2024/01/05 00:16 (external edit)