Select a Chapter: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Back to the Main Page | ||
Chapter Fourteen listings: 15 classes and 2 interfaces |
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 } //====================== } |
Layout and Design Copyright © Psumonix, LLC. All Rights Reserved. |