5.1 Fundamentals

Using foo or foobar for a procedure name is something of a tradition.

Applet Code

The resulting tree shows no improvement over a simple linear list in this case.

on this page: [ Terminology | Notations | Stacks | Queues | Trees ]

Terminology

A mathematical expression such as:

                                   y + z

has an operator (+) and two operands (y and z). Such operators are called binary operators because they have two operands. Unary operators are also possible:

                                      -y

Here a unary minus is being used.

Operators and operands are grouped in expressions. Precedence is used to determine which operations are done first in an expression such as:

                                      -y + x * z / g

In the absence of brackets, the usual order is / * - +

In Java methods (and equally in many other High Level Langauges) every method has a signature:

The actual parameters (often called the arguments) are supplied by when the method is called:

 foo(1, 2.65)

or

foo(z, x*y)

The actual parameters must correspond in number and type to the formal parameters.

If some part of the method signature is different, then we have a different method:

                                     public int foo(double x, double y, int z)

is another method that can be called. It has the same name but (presumably) performs a different function - polymorphism.

Back to top

Notations

Normally infix notation is used, requiring brackets to determine a sequence of operations in some expressions:

                    (x + y) / (a + b)

Reverse Polish Notation (RPN) uses postfix notation in which the expression above becomes:

                   xy+ab+/

As far as the IB course is concerned we will only see binary operators used in postfix notation, therefore each operator is preceded by the two operands it needs. that expression can then be expanded term by term to find the infix equivalent:

                   xy+ab+/

                   (x + y)ab+/

                   (x + y)(a + b)/

                    (x + y) / (a + b)

As we shall see further on , such expressions can easily be evaluated using a stack.

As the name suggests, in prefix notation the operator precedes the two corresponding operands, thus the expression becomes

                   /+xy+ab

These expressions can also be represented in binary trees and correspond to the different methods of tree traversal (later) .

Back to top

Stacks

A stack is a very useful data structure used by computers to keep track of data in a set sequence.

A common analogy for a stack is a pile of plates. Imagine washing dishes in a restaurant, waiters come and place dirty plates on a pile (let's assume they do it one plate at a time), you take them off one at a time to wash them.

In this way, the last plate put onto the pile is the first one to be washed. For this reason a stack is known as a LIFO structure ( L ast I n F irst O ut).

If everything gets popped then the stack is empty, no more pops are possible and an attempt to do so causes an underflow error.

By contrast, if we push to the stack limit we have a full stack, no more pushes are possible and an attempt to do this causes a stack overflow error.

Java examples of a stack implemented in Java as a linked list can be found on the stacks page

Back to top

Using a stack to reverse a String
One use of a stack could be to reverse a string of characters: simply push all of the letters on to the stack and then pull them off again:

  L E M O N:

Push the letters one by one:

then Pull them off again:

      N O M E L

See the Stacks page for a Java example.

Using a stack to check brackets
Another use might be to see if a a particular string of characters obeys given grammatical rules. A compiler does this, for example, when checking character strings for quotes or arithmetical expressions for matching brackets:

  (a + b) * ((c - d) / (x - y))

To parse (or check the syntax of) the string in terms of brackets we could use a stack, each occurrence of an opening bracket would be pushed on and each occurrence of a closing bracket would cause it to be popped back.

If there is no error and the stack is empty at the end of the expression then the brackets match.

Back to top

Using a stack to perform postfix calculations
As described above;  infix notation looks like:

                    (x + y) / (a + b)

Reverse Polish Notation (RPN) or postfix notation looks like:

                     xy+ab+/

To evaluate these using a stack; first the numbers are pushed onto the stack:

When an operator is encountered, the expression is then evaluated by popping the operands off the stack; the result is then pushed back on to the top of the stack.

Values a and b are now encountered:

Followed by another add:

The / operator is now encountered so a+b is pulled from the stack and divided by x + y. There are no more operations and the result is pushed to the top of the stack from where it can be retrieved.

Back to top

Using a stack with parameters and return addresses
Consider the following sequence of method calls:

public void main()
{
  int x, y, z;
  x = obtainInt("Please input number 1");
  y = obtainInt("Please input number 2");
  z = x + y;
}
public int obtainInt(String m)
{
  displayMessage( m );
  item = inputInt(); // IBIO method call (method not shown)
  return item;
}
public void displayMessage(String message)
{
  output(message); // IBIO method call (method not shown)
}

When the first call is made to method obtainInt is called from the main program, the address of the next statement - y = obtainInt("Please input number 2"); - is pushed onto the run-time stack to be executed when the end of procedure obtainInt is encountered.

Since obtainInt then calls displayMessage the return address of obtainInt and the values of any local variables (including parameters) are also pushed onto the runtime stack:

After the procedures are executed the return address is pulled from the stack together with the values of any local variables of the calling procedure, which are stored with it.   It is perfectly possible for a method to call itself and for the value of any local variable in any one call to be preserved.  See the page on recursion for further details.

Interrupts
Recall from the machine instruction cycle page that before an instruction is fetched, the interrupt register is checked.

An interrupt is a signal generated by a peripheral or application program to tell the operating system that some type of service is required. For example, a printer is offline or out of paper, or some application has just sent a request to save a file.

To service an interrupt, it may be necessary to halt the currently active process. In this case the state of the process is saved onto a stack. That way multiple processes can be restored in the order that they were pushed onto the stack.

Back to top

Queues

A queue is an ordered set of data items from which items may be deleted (de-queued) at one end (the front) and added (en-queued) at the other (the rear).

In many countries (though not all!) this concept is familiar when waiting for a service such as buying goods in a supermarket, waiting for the bus or trying to get help in a bank.

People join at the rear, make their way to the front where they are served (in the best of worlds, nobody is allowed to push into the middle).

Java examples of a queue implemented in Java as a linked list can be found on the queues page

Queues are used in computer systems to buffer input devices such as the keyboard and mouse. Using a queue endures that the keystrokes are processed in the order in which they were input. As long as the processor can take the items from the buffer faster than you can type them in, no characters get lost.

You can see the operation of a print queue in Windows by opening the printers folder from Start | Settings. In this type of queue, the order of jobs can be changed by an operator with sufficient privileges.

Queues can also be used in modeling and simulation programs (eg predicting traffic flow or emulating a supermarket queue).

Example of a customer service queue:

Back to top

Trees

Trees are non-linear hierarchical data structures where every component may have super-components above and sub-components below.

A tree can also be described as a finite set of one or more linked nodes such that there is a special node with no parent called the root . Each subtree of the node is a child . Nodes at the same level are siblings. In either case a tree is probably a familiar concept already:

Looking at the sub tree we can see that it has all of the features of the main tree (a root, nodes and leaves) so that a tree is a recursive structure.

A binary tree is a collection of nodes, which has, at most, two children. It is relatively simple to implement such a structure using a node with a data field and two pointer fields:

Back to top

Trees can be used to store search keys for fast retrieval. Consider a list of names:

Nguyen, Binh, Linh, Jessie, Jackie, Angel, Minh, Feifei, Tram, Yuwei, Shan, Vanh

To search this list from the beginning can take up to 12 iterations, 6 on average. We can improve this by storing in an ordered binary tree.

The first item becomes the root:

To add the next item we have to move left if the item is less than the root node:

Each node now has to be added by following down until an empty node is encountered; moving left if the node to be placed is less and right if it is greater:

If you can complete this tree you should get something like this. Now the maximum number of search comparisons is the same as the depth of the tree, ie 6, a saving of about half the time.

The tree is not well-balanced and we could improve the search time by re-ordering the nodes.

Consider what can happen if the nodes are added in strict alphabetical order.

Back to top

A binary tree can also be used to represent a decision tree:

The non-leaf nodes are the questions and the leaf nodes are the advice - even if this is "no further advice is available".

You should also be familiar with the use of trees to store a list if files, using folders and sub-folders. This is common on all operating systems.

Back to top

related: [ ADT home | next: static data structures ]

See also the corresponding Java pages for these structures and features.

Questions or problems related to this web site should be addressed to Richard Jones who asserts his right to be identified as the author and owner of these materials - unless otherwise indicated. Please feel free to use the material presented here and to create links to it for non-commercial purposes; an acknowledgement of the source is required by the Creative Commons licence. Use of materials from this site is conditional upon your having read the additional terms of use on the about page and the Creative Commons Licence. View privacy policy.