class Stack {
private int[] array;
private int contents; // stack pointer
private int capacity; // array.length;
public Stack () { this (10); } // default size
public Stack (int size) {
array = new int[size];
contents = 0;
capacity = size;
}
public void push (int new_value) {
if (capacity==contents) resize ();
array[contents] = new_value;
contents++;
}
public int pop () {
if (contents==0) throw IllegalArgumentException ("Stack Underflow");
contents--;
return array[contents];
}
private int resize () {
// you can do this one!
}
For a Queue you need two pointers: one to write and one to read.
The array is used in a "circular" fashion, which means some if
statements.
This is a good programming exercise. I recommend that you do it.
for node #i, children[i] is an array, which lists (as its values) the numbers of the nodes that are the children of node #i.Using this, here is a depth-first search that says whether there is a path from source to dest.
boolean exists_path (int source, int dest) {
if (source==dest) return true;
int[] list = children [source];
for (int i=0; i<list.length; i++) {
int child = list[i];
if (exists_path (child, dest)) return true;
}
return false;
}
Modify this so that it returns a Vector containing the numbers
of the successive nodes in the path.
Better: make this an array,
if you can think of a way of finding out the length of the path before
you need to allocate it.
This is www.PaulTaylor.EU/algorithms/graph.html and it was derived from algorithms/graph.tex which was last modified on 21 July 2007.