Dynamic data structures, part 1

Welcome! In this tutorial we will be discussing dynamic data structures. We'll take an in-depth look at the theory behind the various data structures, of what use they are to the programmer, and how to implement them in BASIC. Please note that despite the fact that QB Times is a QuickBASIC magazine, the example programs within this tutorial have been written such that they will be able to run on ANY implementation of BASIC! However, please note that indentations have been used with the code, which is not supported by certain older BASIC implementations. This is simple to correct, however.

The most important dynamic data structures are:

(a) The stack.
(b) The queue.
(c) The linked list.
(d) The tree.

The trouble with describing these data structures is that if you've never wanted to use one it is difficult to see how they could be useful. However, if you don't know that they exist then there are some programs that are very difficult to write, unless you re-invent the wheel.

The stack:

The best known and simplest of all the dynamic data types is the stack. A stack is an area of storage that can be accessed through just two operations, push and pull. Push stores an item on the stack and pull retrieves an item from the stack. The more formal name for a stack, 'Last In First Out' of LIFO stack, gives a clue to the order in which a sequence of items pushed on the stack will be recalled by pull operations. The best way to think of a stack is to imagine each item pushed onto the stack being placed on the top of a pile (stack) of all the earlier items pushed onto the stack. A pull operation, therefore, always removes the top-most item. Thus the last item to be pushed onto the stack is the first one to be retrieved.

As an example of a stack and of the sort of thing that a stack can be used for, consider the problem of reversing a sequence of letters. The solution using a stack is: 

1. PUSH the first letter to the top of the stack   ->  A
2. PUSH the second letter to the top of the stack  ->  B
                                                       A
3. PUSH the third letter to the top of the stack   ->  C
                                                       B
                                                       A
then 
4. PULL the stack to get C from the top of the stack  ->  B
                                                          A
5. PULL the stack to get B from the top of the stack  ->  A
6. PULL the stack to get A from the top of the stack  ->  empty
Notice the order that the letters went onto the stack, ABC, and how they came out, CBA. Thus, they have been reversed as required. Also notice that the entire reversal procedure was automatic in that there was no need explicitly to keep track of the order that the items came in.

A stack is easy to implement in BASIC using a one-dimensional array and a single variable. The array is used to hold the items on the stack and the variable is used as a pointer to the current top of the stack. For example, to reverse three numbers in much the same way that the three letters were reversed is easy: 

10  DIM S(10)
20  LET P = 1
30  FOR I = 1 TO 3
40    INPUT N
50    LET S(I) = N
60    LET P = P + 1
70  NEXT I
80  FOR I = 1 TO 3
90    LET P = P - 1
100   LET N = S(P)
110   PRINT N
120 NEXT I
Line 10 sets up the array to be used as the stack. Line 20 sets the variable P to 'point to' the top of the stack. In this case, the top of the stack corresponds to the first free location in the array. Lines 50 and 60 form the push operation. The number is stored in S(P) and then the pointer is incremented to point to the next free location. Lines 90 and 100 form the pull operation and this should be easy to understand as it is much like the push operation.

For the above example, and future examples, please take careful note of the OPTION BASE setting.

There is another way to implement a stack that is very useful when the data to be manipulated consists of single characters. Adding a character to a string. 

S$ = C$ + S$
is very much like pushing a character onto a stack. Think of the 'front' of the string S$ as the front of the stack: then adding the character in C$ to the front of the string is like pushing it onto the top of the stack. You should be able to work out that to pull a character off the stack all you have to do is remove the first character. That is: 
C$ = LEFT$(S$, 1)
S$ = RIGHT$(S$, LEN(S$) - 1)
The first instruction places the first character of the S$ in C$ and the second removes the first character from from S$. Using these two ideas we can write a program that reverses a sequence of letters: 
10 S$ = ""                           'initialise stack
20 INPUT A$
30 FOR I = 1 TO LEN(A$)
40   S$ = MIS$(A$, i, 1) + S$        'push each character
50 NEXT I                            '    onto stack
60 FOR I = 1 TO LEN(A$)
70   PRINT LEFT$(S$, 1)              'pull each character
80   S$ = RIGHT$(S$, LEN(S$) - 1)    '    off stack
90 NEXT I
That's all there is to implementing stacks and apart from worrying about pulling data off the stack when there isn't any more, and pushing more items on the stack than the size of the array allows, there is nothing else to do. The most common application of stacks is in language processing, eg. compilers, etc. However, this probably due to the fact that programmers that write compilers tend to know about stacks! In general, a stack is useful whenever the order in which things have to be treated is different from the order in which they arrive.

Queues:

Once you have understood the idea behind a stack, then a queue is just one step further on. The data structure called a queue mimics exactly the normal behaviour of people queuing. A queue has a first person and a last person. People join the queue at the rear and leave the queue from the front. In the data structure calles a queue the addition of a data item also happens to the rear and retrieving a data item also happens from the front.

The easiest way to implement a queue in BASIC is to use two pointers in place of the stacks's one. The first pointer indicates the front of the queue and the second pointer indicates the end of the queue. In addition to these two pointers we can associate two new operations with every queue - JOIN and LEAVE. If F is the pointer to the front of the queue and R is the rear, then the two operations in BASIC are as follows: 

JOIN
      Q(R) = DATA
      R = R + 1

LEAVE
      DATA = Q(F)
      F = F + 1
Thus the front of the queue moves relentlessly up the array. The trouble is, so does the rear! In order to stop the array having to be enormous you have to employ the extra trick of making the queue circular. If either of the pointers go past the top of the array they are reset to point to the beginning of the array. The two operations now become: 
JOIN
      Q(R) = DATA
      R = R + 1
      IF R > top of array THEN R = 1

LEAVE
      DATA = Q(F)
      F = F + 1
      IF F > top of array THEN F = 1
The queue starts off empty and the two pointers point to the same place. This can be used to detect when the queue is empty. If, after removing an item, the pointers point at the same element of the array, then the queue is empty. However, if this happens after an item has been added this means that the queue is full. The best way to find out how queues work is to try a dry run of a queue on paper.

There is a way of implementing queues using strings that is very similar to the idea os using strings to implement a stack. To join a string queue the character should be added to the left-hand side and characters leaving the queue are taken from the right. So, 

JOIN
  S$ = C$ + S$

LEAVE
  C$ = RIGHT$(S$, 1)
  S$ = LEFT$(S$, LEN(S$) - 1)
The main use of queues is in real time control and operating systems where things happen at a rate that the computer cannot deal with. Each thing is therefore placed in the queue and dealt with later in the same order that it arrived.

And that concludes part one in this series! I hope you enjoyed it! Next month we will be discussing the linked list and the tree.

Happy coding in QB!!! ^_^

This article has been written by Matthew River Knight of Dark Legends Software (http://www.darklegends.com)

© Copyright 1999-2000 The QB Times.
This tutorial was taken from The QB Times with permission from the webmaster(s) of the site. You may not take this article and place it on any other website.