public interface StackADT // not in the Sun library
{
/** Tell whether the stack has no more elements. */
public boolean isEmpty();
/** Return the value that pop would give, without modifying
* the stack. Throw an Exception if the stack is empty. */
public Object peekTop();
/** Remove and return the value that has been in the stack the
* least time. Throw an Exception if the stack is empty. */
public Object pop();
/** Add the given value to the stack. */
public void push (Object ob);
}
public interface QueueADT // not in the Sun library
{
/** Tell whether the queue has no more elements. */
public boolean isEmpty();
/** Return the value that dequeue would give without modifying
* the queue. Throw an Exception if the queue is empty. */
public Object peekFront();
/** Remove and return the value that has been in the queue the
* most time. Throw an Exception if the queue is empty. */
public Object dequeue();
/** Add the given value to the queue. */
public void enqueue (Object ob);
}
public class StackAndQueueTester
{
/** For test purposes: Create a stack of 5 values,
* print it, reverse the order, then print the result. */
public static void main (String[] args)
{ ArrayStack stack = new ArrayStack();
for (int k = 0; k < 5; k++)
stack.push (new Double (Math.random()));
System.out.println ("Before reversing the stack: \n"
+ stack.toString());
QuackOp.reverse (stack);
System.out.println ("\nAfter reversing the stack: \n"
+ stack.toString());
} //======================
}
public class QuackOp // independent methods for queues and stacks
{
/** Precondition for these methods:
* The stack and queue parameters are not null. */
/** Return the numeric value of the given postfix expression. */
public static int evaluatePostfix (QueueADT queue)
{ StackADT stack = new ArrayStack();
while ( ! queue.isEmpty())
{ Object data = queue.dequeue();
if (data instanceof Integer)
stack.push (data);
else
{ char operator = ((Character) data).charValue();
int second = ((Integer) stack.pop()).intValue();
int first = ((Integer) stack.pop()).intValue();
if (operator == '+')
stack.push (new Integer (first + second));
else if (operator == '-')
stack.push (new Integer (first - second));
//etc.
}
}
int valueToReturn = ((Integer) stack.pop()).intValue();
if ( ! stack.isEmpty())
throw new RuntimeException ("too many values");
return valueToReturn;
} //======================
/** Return a new queue containing the postfix equivalent of
* the infix expression in the parameter. */
public static QueueADT fromInfixToPostfix (QueueADT queue)
{ QueueADT postfix = new ArrayQueue();
StackADT stack = new ArrayStack();
while ( ! queue.isEmpty())
{ Object data = queue.dequeue();
if (data instanceof Integer)
postfix.enqueue (data);
else
{ char nonNumber = ((Character) data).charValue();
if (nonNumber == ')')
postfix.enqueue (stack.pop());
else if (nonNumber != '(') // ignore left paren
stack.push (data);
}
}
return postfix;
} //======================
/** Reverse the order of the elements on the given stack. */
public static void reverse (StackADT stack)
{ QueueADT queue = new ArrayQueue();
while ( ! stack.isEmpty())
queue.enqueue (stack.pop());
while ( ! queue.isEmpty())
stack.push (queue.dequeue());
} //======================
/** Remove and return the second value on the stack. If the
* stack has less than 2 elements, simply return null. */
public static Object removeSecond (StackADT stack)
{ if (stack.isEmpty())
return null;
Object first = stack.pop();
Object valueToReturn = stack.isEmpty() ? null : stack.pop();
stack.push (first);
return valueToReturn;
} //======================
/** Remove all elements on the stack down to but not including
* the given object. */
public static void removeDownTo (StackADT stack, Object ob)
{ if (ob == null)
{ while ( ! stack.isEmpty() && stack.peekTop() != null)
stack.pop();
}
else
{ while ( ! stack.isEmpty() && ! ob.equals (stack.peekTop()))
stack.pop();
}
} //======================
/** Remove and return the second value on the queue. If the
* queue has less than 2 elements, simply return null. */
public static Object removeSecond (QueueADT queue)
{ if (queue.isEmpty())
return null;
Object first = queue.dequeue();
Object valueToReturn = queue.isEmpty() ? null : queue.dequeue();
Object endMarker = new Double (0.0); // anything brand-new works
queue.enqueue (endMarker);
queue.enqueue (first);
while (queue.peekFront() != endMarker)
queue.enqueue (queue.dequeue());
queue.dequeue(); // remove endMarker, so first is now at front
return valueToReturn;
} //======================
}
public class ArrayStack implements StackADT
{
private Object[] itsItem = new Object [10];
private int itsSize = 0;
public boolean isEmpty()
{ return itsSize == 0;
} //======================
public Object peekTop()
{ if (isEmpty())
throw new IllegalStateException ("stack is empty");
return itsItem[itsSize - 1];
} //======================
public Object pop()
{ if (isEmpty())
throw new IllegalStateException ("stack is empty");
itsSize--;
return itsItem[itsSize];
} //======================
public void push (Object ob)
{ if (itsSize == itsItem.length)
{ Object[] toDiscard = itsItem;
itsItem = new Object [2 * itsSize];
for (int k = 0; k < itsSize; k++)
itsItem[k] = toDiscard[k];
}
itsItem[itsSize] = ob;
itsSize++;
} //======================
/** Exercise: Remove all elements in the stack that are below
* the parameter. No effect if it is not in the stack. */
public void removeBelow (Object ob)
{ int spot = itsSize - 1;
if (ob == null)
{ while (spot > 0 && itsItem[spot] != null)
spot--;
}
else
{ while (spot > 0 && ! ob.equals (itsItem[spot]))
spot--;
}
if (spot > 0)
{ for (int k = spot; k < itsSize; k++)
itsItem[k - spot] = itsItem[k];
itsSize -= spot;
}
} //======================
public boolean equals (Object ob)
{ if ( ! (ob instanceof ArrayStack)
|| ((ArrayStack) ob).itsSize != this.itsSize)
return false;
ArrayStack given = (ArrayStack) ob; // for efficiency
for (int k = 0; k < this.itsSize; k++)
{ if ( ! this.itsItem[k].equals (given.itsItem[k]))
return false;
}
return true;
} //======================
public String toString()
{ String valueToReturn = "";
for (int k = 0; k < itsSize; k++)
valueToReturn += '\t' + itsItem[k].toString();
return valueToReturn;
} //======================
}
public class ArrayQueue implements QueueADT
{
private Object[] itsItem = new Object [10];
private int itsFront = 0; // location of front element, if any
private int itsRear = -1; // location of rear element, if any
public boolean isEmpty()
{ return itsRear == itsFront - 1;
} //======================
public Object peekFront()
{ if (isEmpty())
throw new IllegalStateException ("queue is empty");
return itsItem[itsFront];
} //======================
public Object dequeue()
{ if (isEmpty())
throw new IllegalStateException ("queue is empty");
itsFront++;
return itsItem[itsFront - 1];
} //======================
public void enqueue (Object ob)
{ if (itsRear == itsItem.length - 1)
adjustTheArray();
itsRear++;
itsItem[itsRear] = ob;
} //======================
/** Shift elements to the front if the array is less than
* three-quarters full, otherwise transfer to a bigger array.
* Precondition: itsRear is the last index in the array. */
private void adjustTheArray()
{ if (itsFront > itsRear / 4)
{ itsRear -= itsFront;
for (int k = 0; k <= itsRear; k++)
itsItem[k] = itsItem[k + itsFront];
itsFront = 0;
}
else
{ Object[] toDiscard = itsItem;
itsItem = new Object [2 * itsRear];
for (int k = 0; k <= itsRear; k++)
itsItem[k] = toDiscard[k];
} // automatic garbage collection gets rid of toDiscard
} //======================
public int size()
{ return itsRear - itsFront + 1;
} //======================
public String toString()
{ String valueToReturn = "";
for (int k = itsFront; k <= itsRear; k++)
valueToReturn += '\t' + itsItem[k].toString();
return valueToReturn;
} //======================
}
public class Node
{
private Object itsData;
private Node itsNext;
public Node (Object data, Node next)
{ itsData = data;
itsNext = next;
} //======================
/** Return the data attribute of the Node. */
public Object getValue()
{ return itsData;
} //======================
/** Return the next attribute of the Node. */
public Node getNext()
{ return itsNext;
} //======================
/** Replace the data attribute. */
public void setValue (Object data)
{ itsData = data;
} //======================
/** Replace the next attribute. */
public void setNext (Node next)
{ itsNext = next;
} //======================
}
public class NodeStack implements StackADT
{
private Node itsTop = null;
public boolean isEmpty()
{ return itsTop == null;
} //======================
public Object peekTop()
{ if (isEmpty())
throw new IllegalStateException ("stack is empty");
return itsTop.getValue();
} //======================
public Object pop()
{ if (isEmpty())
throw new IllegalStateException ("stack is empty");
Node toDiscard = itsTop;
itsTop = itsTop.getNext();
return toDiscard.getValue();
} //======================
public void push (Object ob)
{ itsTop = new Node (ob, itsTop);
} //======================
}
public class NodeQueue implements QueueADT
{
private Node itsFront = null;
private Node itsRear;
/** Tell whether the queue has no more elements. */
public boolean isEmpty()
{ return itsFront == null;
} //======================
/** Return the value that dequeue would give without modifying
* the queue. Throw an Exception if the queue is empty. */
public Object peekFront()
{ if (isEmpty())
throw new IllegalStateException ("queue is empty");
return itsFront.getValue();
} //======================
/** Remove and return the value that has been in the queue the
* most time. Throw an Exception if the queue is empty. */
public Object dequeue()
{ if (isEmpty())
throw new IllegalStateException ("queue is empty");
Node toDiscard = itsFront;
itsFront = itsFront.getNext();
return toDiscard.getValue();
} //======================
/** Add the given value to the queue. */
public void enqueue (Object ob)
{ Node toBeAdded = new Node (ob, null);
if (isEmpty())
itsFront = toBeAdded;
else
itsRear.setNext (toBeAdded);
itsRear = toBeAdded;
} //======================
/** Return the number of elements in the queue. */
public int size()
{ int count = 0;
for (Node p = itsFront; p != null; p = p.getNext())
count++;
return count;
}
/** Add all the values in the queue parameter to the rear of
* the executor. Precondition: queue is not null. */
public void append (NodeQueue queue)
{ if ( ! queue.isEmpty())
{ if (this.isEmpty())
this.itsFront = queue.itsFront;
else
this.itsRear.setNext (queue.itsFront);
this.itsRear = queue.itsRear;
queue.itsFront = null;
}
} //======================
}
public abstract class ListADT implements StackADT
{
/** Return the portion of this list that contains all values
after the first value. Return null if this list is empty.*/
public abstract ListADT theRest();
/** Replace the data value at the front of the list by ob.
No effect if this list is empty. */
public abstract void setTop (Object ob);
// The four StackADT methods (descriptions are in Listing 14.1)
public final boolean isEmpty()
{ return theRest() == null;
} //======================
public abstract Object peekTop();
public abstract Object pop();
public abstract void push (Object ob);
/** Add the given data value at the end of this list. */
public void addLast (Object ob)
{ if (this.isEmpty())
this.push (ob);
else
theRest().addLast (ob);
} //======================
/** Return the number of data values in this list. */
public int size()
{ return this.isEmpty() ? 0 : 1 + theRest().size();
} //======================
/** Remove and return the data value at the given index (zero-
based). Throw an Exception if no data is at that index. */
public Object remove (int index)
{ return index == 0 ? pop() : theRest().remove (index-1); //1
} //======================
/** Insert the data value at the given index (zero-based).
Throw an Exception if index < 0 or index > size(). */
public void add (int index, Object ob)
{ if (index == 0) //2
push (ob); //3
else //4
theRest().add (index - 1, ob); //5
} //======================
/** Return the last data value in this ListADT.
Throw an Exception if the ListADT is empty. */
public Object getLast()
{ return theRest().isEmpty() ? peekTop() //6
: theRest().getLast(); //7
} //======================
/** Return the lowest index where ob occurs.
Return -1 if ob does not occur anywhere in the list. */
public int indexOf (Object ob)
{ return ob == null ? indexOfNull (0) : indexOf (0, ob); //1
} //======================
private int indexOfNull (int index)
{ if (isEmpty()) //2
return -1; //3
else if (null == peekTop()) //4
return index; //5
else //6
return theRest().indexOfNull (index + 1); //7
} //======================
// Precondition: ob is not null.
private int indexOf (int index, Object ob)
{ if (isEmpty()) //8
return -1; //9
else if (ob.equals (peekTop())) //10
return index; //11
else //12
return theRest().indexOf (index + 1, ob); //13
} //======================
/** Tell whether the parameter is one of the data values
in the list. */
public boolean contains (Object ob)
{ return indexOf (ob) != -1; //14
} //======================
/* These ListADT methods are described and coded in the exercises */
public void clear() // remove all data, leave it empty
{ while ( ! isEmpty())
pop();
} //======================
public void copyTo (ListADT par) // insert all at the front of par
{ if ( ! this.isEmpty())
{ par.push (this.peekTop ());
this.theRest().copyTo (par.theRest());
}
} //======================
public Object get (int index) // return the data there
{ return (index == 0) ? peekTop() : theRest().get (index - 1);
} //======================
public void setLast (Object ob)
{ if (theRest().isEmpty())
setTop (ob);
else
theRest().setLast (ob);
} //======================
public boolean equals (ListADT that)
{ if (this.isEmpty())
return that.isEmpty(); // i.e., both are empty
else if (that.isEmpty())
return false;
else
return this.peekTop().equals (that.peekTop())
&& this.theRest().equals (that.theRest());
} //======================
/* These ListADT methods are only described in the exercises
public void addAll (ListADT par) // append all at its end
public Object[] toArray (Object[] par) // copy it to an array
public void set (int index, Object ob) // replace that data
public Object removeLast() // remove the last and return it
public boolean remove (Object ob) // remove it if you can
public int lastIndexOf (Object ob)
public String toString() // return the String equivalent
public boolean containsAll (ListADT that) */
/** Add the given value to the list before the first data
value that is greater-equal to it, using compareTo.
Add it at the end of the list if there is no such value.
Precondition: ob is non-null and Comparable to all
data values currently in the list. */
public void insertInOrder (Comparable ob)
{ if (this.isEmpty() || ob.compareTo (peekTop()) <= 0)
this.push (ob);
else
theRest().insertInOrder (ob);
} //======================
/** Rearrange the data values to be in ascending order. Throw
an Exception unless all values are mutually Comparable. */
public void insertionSort()
{ if ( ! this.isEmpty())
{ theRest().insertionSort();
this.insertInOrder ((Comparable) this.pop());
}
} //======================
public Object removeSmallest()
{ Comparable smallestSoFar = (Comparable) this.peekTop();
ListADT spot = this;
for (ListADT p = this.theRest(); ! p.isEmpty(); p = p.theRest())
{ if (smallestSoFar.compareTo (p.peekTop()) > 0)
{ smallestSoFar = (Comparable) p.peekTop();
spot = p;
}
}
return spot.pop(); // which is in fact smallestSoFar
} //======================
}
public class NodeList extends ListADT
{
private Object itsData = null;
private NodeList itsNext = null;
public ListADT theRest()
{ return itsNext; //1
} //======================
public void setTop (Object ob)
{ itsData = ob; //2
} //======================
public Object peekTop()
{ if (itsNext == null) // so it represents an empty list//3
throw new IllegalStateException ("nothing there");//4
return itsData; //5
} //======================
public void push (Object ob)
{ NodeList toAdd = new NodeList(); //6
toAdd.itsData = this.itsData; //7
toAdd.itsNext = this.itsNext; //8
this.itsData = ob; //9
this.itsNext = toAdd; //10
} //======================
public Object pop()
{ Object valueToReturn = this.itsData; //11
NodeList toDiscard = this.itsNext; //12
this.itsData = toDiscard.itsData; //13
this.itsNext = toDiscard.itsNext; //14
toDiscard.itsNext = null; // make this list empty //15
return valueToReturn; //16
} //======================
}
public class CardList extends NodeList
{
private java.util.Random randy = new java.util.Random();
/** Put the numToDo data values in a random order.
Throw an Exception if numToDo > this.size(). */
public void shuffleAllCards (int numToDo)
{ ListADT list = this;
for ( ; numToDo >= 2; numToDo--)
{ list.push (list.remove (randy.nextInt (numToDo)));
list = list.theRest();
}
} //======================
/** Repeatedly remove the first legally-removable pair of
cards. Return true if this leaves the list empty, false
if not. Precondition: All data values are Card objects. */
public boolean removeAllSucceeds()
{ return this.isEmpty() || (removeTheFirstSucceeds (this)
&& this.removeAllSucceeds());
} //======================
/** Remove the first legally-removable pair of cards from list
if you can. Return false if there is no legal move. */
private boolean removeTheFirstSucceeds (ListADT list)
{ if (list.theRest().isEmpty()) //positioned at the last card
return false;
Card first = (Card) list.peekTop();
Card second = (Card) list.theRest().peekTop();
if (first.getRank() == second.getRank()
|| first.getSuit() == second.getSuit())
{ list.pop();
list.pop();
return true;
}
return removeTheFirstSucceeds (list.theRest());
} //======================
}
public class DoublyLinked extends ListADT
{
private Object itsData = null;
private DoublyLinked itsNext = null;
private DoublyLinked itsPrevious = null;
/** Return the DoublyLinked object for which theRest is this
list, if any. But return null if there is no such list. */
public DoublyLinked theOneBefore()
{ return itsPrevious; //1
} //======================
public void push (Object ob)
{ DoublyLinked toAdd = new DoublyLinked(); //2
toAdd.itsData = this.itsData; //3
toAdd.itsNext = this.itsNext; //4
this.itsData = ob; //5
this.itsNext = toAdd; //6
toAdd.itsPrevious = this; //7
if (toAdd.theRest() != null) //8
((DoublyLinked)toAdd.theRest()).itsPrevious = toAdd;//9
} //======================
public Object pop()
{ Object valueToReturn = this.itsData; //10
DoublyLinked toDiscard = this.itsNext; //11
this.itsData = toDiscard.itsData; //12
this.itsNext = toDiscard.itsNext; //13
toDiscard.itsNext = null; // make this list empty //14
toDiscard.itsPrevious = null; //15
if (this.theRest() != null) //16
((DoublyLinked) this.theRest()).itsPrevious = this; //17
return valueToReturn; //18
} //======================
public ListADT theRest()
{ return itsNext; //1
} //======================
public Object peekTop()
{ if (itsNext == null) // so it represents an empty list //2
throw new IllegalStateException ("nothing there"); //3
return itsData; //4
} //======================
public void setTop (Object ob)
{ itsData = ob; //5
} //======================
}
public class HeaderList extends ListADT
{
private Object itsData = null;
private HeaderList itsNext = null;
public ListADT theRest()
{ return itsNext; //1
} //======================
public Object peekTop() // Throws Exception if empty
{ return itsNext.itsData; //2
} //======================
public void setTop (Object ob)
{ if (itsNext != null) //3
itsNext.itsData = ob; //4
} //======================
public void push (Object ob)
{ HeaderList toAdd = new HeaderList(); //5
toAdd.itsData = ob; //6
toAdd.itsNext = this.itsNext; //7
this.itsNext = toAdd; //8
} //======================
public Object pop()
{ HeaderList toDiscard = this.itsNext; //9
this.itsNext = toDiscard.itsNext; //10
toDiscard.itsNext = null; // make this list empty //11
return toDiscard.itsData; //12
} //======================
}
public class JosephusList extends NodeList
{
/** Remove every nth one circularly until only one is left.
Return that one. Precondition: The list is not empty. */
public Object josephus (int numToCount)
{ ListADT circle = this;
while ( ! this.theRest().isEmpty()) // more than 1 left
circle = popAfterGoingForward (circle, numToCount);
return this.peekTop();
} //======================
private ListADT popAfterGoingForward (ListADT circle, int num)
{ for (int k = 0; k < num; k++)
{ circle = circle.theRest();
if (circle.isEmpty())
circle = this;
}
circle.pop();
return circle;
} //======================
}
public class WebData
{
public final int MAX;
private WebList[] itsItem;
public WebData (int numCategories)
{ MAX = (numCategories > 0) ? numCategories : 1;
itsItem = new WebList [MAX];
for (int k = 0; k < MAX; k++)
itsItem[k] = new WebList();
} //======================
/** Add the given page/link association of the given category.
* Ignore any category outside of the range 0..MAX-1. */
public void addLink (int category, Object page, Object link)
{ if (page != null && category >= 0 && category < MAX)
itsItem[category].addLink (page, link);
} //======================
public void listAll (int category)
{ if (category >= 0 && category < itsItem.length)
itsItem[category].listAll();
} //======================
}
/** A WebList contains zero or more non-empty NodeList objects.
* itsPrior is a reference to one of them if not null. Each of
* those NodeLists contains 1 web page followed by its links. */
public class WebList extends NodeList
{
private ListADT itsPrior = null;
public void addLink (Object page, Object link)
{ if (itsPrior == null || ! itsPrior.peekTop().equals (page))
itsPrior = findMatchEvenIfYouHaveToMakeIt (page);
itsPrior.theRest().push (link); // push after the page
} //======================
private ListADT findMatchEvenIfYouHaveToMakeIt (Object page)
{ ListADT pos = this;
for ( ; ! pos.isEmpty(); pos = pos.theRest())
{ if (((ListADT) pos.peekTop()).peekTop().equals (page))
return (ListADT) pos.peekTop();
}
ListADT toAdd = new NodeList();
toAdd.push (page);
pos.push (toAdd); // putting it at the end of this WebList
return toAdd;
} //======================
public void listAll()
{ // left as an exercise
} //======================
}
|
2