Suppose I have two tasks to perform, a then b. Suppose I know the way to perform a is to perform subtasks c then d, and the way to perform b is to perform subtasks e then f. Now suppose I know the way to perform c is to perform g then h, and I know how to do those directly, I don't have to break them further into subtasks. And suppose also the way to perform d is to do i then j.
I could keep a list of the tasks I have to do in the order I have to do them, and that list would start off as [a,b]. Since doing a involves doing c then d, then I could change my lists of tasks to [c,d,b]. And since I know doing c involves doing g then h, I can change my lists of tasks to [g,h,d,b]. I can now do g directly, since I know how to do that without breaking it into subtasks, so I do it and my list of tasks becomes [h,d,b]. Similarly, I can do h, leaving me with [d,b]. Now to do d, I must do i then j, so my list of tasks becomes [i,j,b], and so on.
My list of tasks works like a stack, and to do all my tasks I obey a simple loop. I take the task off the top of the stack (or the front of the list). If it is a task I can do directly, I do it, otherwise if it is a task I can break down into subtasks, I push the subtasks on top of the stack (put them at the front of the list). I follow this simple loop until my stack or list is empty, then I have finished my work.
I could write what I know about the tasks I have to perform as a set of methods:
myWork()I could also represent the tasks as a tree structure, showing how tasks break into subtasks:
{
a();
b();
}
a()
{
c();
d();
}
b()
{
e();
f();
}
c()
{
g();
h();
}
d()
{
i();
j();
}
The work that is done in executing these tasks is equivalent to
a traversal of this tree. Previously
we suggested
any such traversal would require recursion, but with an explicit
stack of tasks we were able to do it purely with iteration.
Printing a tree using a stack and iteration
The task of printing a tree can be broken into three subtasks,
printing its two branches and printing its node value. The order in
which these subtasks are handled makes the difference as to whether
the tree is printed with pre-order, in-order or post-order traversal.
For ordered trees, printing in-order results in the components of the
tree being printed completed in ascending order.
Rather than using recursion, following what is written above, we can
use a stack to keep a list of printing tasks to be done. The stack
will consist both of trees and of node values. As we have considered
throughout, rather than have a method which actually prints a tree,
we will have a method that returns a string that can be printed.
This gives us the following code for the task of printing a tree of
integers representing a set which could be put in the place of the
toString methods in set classes given
previously:
public String toString()We create a new stack and push the whole tree onto it. Then we call an iterative method which loops through the stack until it is empty, taking items off the front of it, adding them to the string which is finally returned if they represent integers, breaking them down into their subtrees and node value if they represent trees.
{
if(tree.isEmpty())
return "{}";
else
{
Stack stack = new Stack();
stack.push(tree);
return "{"+toString(stack)+"}";
}
}
private static String toString(Stack stack)
{
String str="";
while(!stack.isEmpty())
{
Object next = stack.top();
stack.pop();
if(next instanceof Integer)
{
str+=next;
if(!stack.isEmpty())
str+=',';
}
else
{
Tree t = (Tree)next;
if(!t.right().isEmpty())
stack.push(t.right());
stack.push(new Integer(t.item()));
if(!t.left().isEmpty())
stack.push(t.left());
}
}
return str;
}
The stack is declared as previously
with its component items of type Object. They do not
all have to be of the same actual type, and in this case they are not.
The stack contains a mixture of items, some of type Tree
and some of type Integer. The type Integer
is
the wrapper class for int, so new Integer(t.item())
creates a new Integer object representing the int
given by t.item(). We can tell whether the item that is
taken from the top of the stack is of type Integer rather
than of type Tree by using instanceof. In
Java,
if exp is an expression and T is the name
of a type, exp instanceof T is a boolean
expression which evaluates to true if exp
refers to an
object of type T and false if exp
refers to an object which is not of type T. Obviously, it
is
only of use if exp is of a type more general than T,
which it is in our code, since exp is the variable
next of the most general type, Object.
If the top of the stack is of type Integer, that is
just
joined onto the string giving the overall representation of the tree.
The statement str+=next will automatically use the
toString method from the object referred to by next,
which in the case of Integer is built in as part of the
Java library, and just gives the string corresponding to the value of
the
integer.
If the object from the top of the stack is not an Integer,
it must be a Tree. We need to view it as a Tree
in order to be able to apply the Tree methods to it.
The statement Tree t = (Tree)next sets
t to refer to the same object as next refers
to,
but treating it as a Tree object rather than an
Object object. It is then broken into its three parts
which
are put onto the stack, except that empty trees are ignored.
push) will be the first that is taken
(using top and pop) when one is removed.
Another sort of data structure is referred to as FIFO,
meaning "first in, first out", meaning that when you take an object
out of the structure you will get the first one that was put into it
of all those that are still in it. In other words, it is a
queue: items join a queue at the back and leave it at the front.
A queue could be represented just by a linked list, but this makes adding new items at the end inefficient, since you have to send a pointer down the list to reach the last cell in order to add a new one. A more efficient representation represents a queue as a linked list with an extra pointer in the queue object pointing to the last element of the linked list. So the following structure represents a queue storing the elements [7,3,8,2]:
Then the code for class Queue is:
class Queue
For simplicity, as with our other data structures, there is no
error reporting if an attempt is made to access an item in a
queue which is actually empty (it will cause a
{
private Cell front,back;
public Object first()
{
return front.first;
}
public void leave()
{
front=front.next;
if(front==null)
back=null;
}
public void join(Object obj)
{
if(front==null)
{
front = new Cell(obj,null);
back=front;
}
else
{
back.next = new Cell(obj,null);
back=back.next;
}
}
public boolean isEmpty()
{
return front==null;
}
private static class Cell
{
Object first;
Cell next;
Cell(Object f,Cell n)
{
first=f;
next=n;
}
}
}NullPointerException
to be thrown). If the queue is
empty both the front and back pointer are
set to null and account needs to be taken of this
possibility. Otherwise, the pointer manipulations needed to remove
an item from the front of the queue (in method leave) and
add an item to the back of the queue (in method join)
are simple.
The operations here are destructive. The representation suggested here cannot be easily adapted to give queues that operate on a constructive basis, but in practice there is rarely a need for queues which operate with constructive methods.
Queues are used in computer science for the same sort of uses where queues are used in real life - where there are several entities wanting to use a resource which can only be used by one entity at a time, and the entities are given use of the resource in the order at which they made a request for it. Queue data structures are often used in computer simulations to simulate real life queues.
Queues are also used if we want to traverse a tree in breadth first order. This means looking at the node first, then the items which are the node values of the branches of the tree, then the items which are the node values of their branches and so on. So in the tree representing my work above, after dealing with the node value of the tree, I would deal with it content in alphabetical order.
Breadth-first traversal of a tree cannot be done using simple recursion because it involves looking at part of one branch, then part of another, then going back to the first branch and so on. However, it can be done if we use a queue in a similar way to our use of a stack above to traverse a tree without using recursion. A new queue of trees is created, with the tree to be traversed its only member. Then a loop is set up in which the front item of the queue is taken from it, its node value processed and any non-empty branches added to the queue. This is continued until the queue is empty. If "proessing a node value" means "joining a string equivalent of the node value to a cumulative string", the result will be a string reprsenting the items in the tree in breadth-first order.
The code below could be added to our class which represented sets as ordered trees
with field tree of type Tree
as the representation, in order to give a method breadthFirst
which when called on a set prints the set, but with the items in the
set in the order they are in the tree if traversed breadthfirst:
public String breadthFirst()
{
if(tree.isEmpty())
return "{}";
else
{
Queue q = new Queue();
q.join(tree);
return "{"+breadthFirst(q)+"}";
}
}
private static String breadthFirst(Queue q)
{
String str="";
while(!q.isEmpty())
{
Tree t = (Tree)q.first();
q.leave();
if(!t.left().isEmpty())
q.join(t.left());
if(!t.right().isEmpty())
q.join(t.right());
str+=t.item();
if(!q.isEmpty())
str+=",";
}
return str;
}
Last modified: 5 April 2005