Chapter 21: Data Structures and java.util

Quiz

1. What's the difference between a stack and a queue?

   The last object added to a stack is the first to be removed from it. That is, it is last-in, first-out. The last object added to a queue is the last to be removed from it. A queue is first-in, first-out.

Exercises

1. As written the StringStack class still allows one to put non-String

   objects on the stack. Fix this by overriding push(Object o) so that it checks for the type of the object. If the object is not an instance of String push the o.toString() on the stack instead. Can you eliminate the check for the type of the object and just always push o.toString()? In other words, given that s is a String is s.toString() equal to s?

   In fact you can skip the test. If s is a String then s.toString() == s. Therefore:

   
   public class StringStack extends java.util.Stack {
   
     public void push(Object o) {
       super.push(o.toString());
     }
   
     public String peek() {
       return (String) super.peek();
     }
   
     public String pop() {
       return (String) super.pop();
     }
   
   }
   

2. As written the StringStack class still allows one to put non-String

   objects on the stack. Fix this by overriding push(Object o) so that it checks for the type of the object. If the object is not an instance of String throw a user defined exception.

   Actually, you can go this one better. By casting o to a String, before pushing it you let the runtime do the work of checking whether o is a String and throwing the RuntimeException ClassCastException if it's not.

   
   public class StringStack extends java.util.Stack {
   
     public void push(Object o) {
       super.push((String) o);
     }
   
     public String peek() {
       return (String) super.peek();
     }
   
     public String pop() {
       return (String) super.pop();
     }
   
   }
   

3. Modify the print method in Program 21.6 so that it prints the

   elements of the tree from largest to smallest.

     public void print() {
     
       if (right != null) right.print();
       System.out.println(data);
       if (left != null) left.print();
     
     }
     

4. Add two methods to the treenode class, one that returns an Enumeration of the elements in the tree sorted from smallest to largest and another that returns an Enumeration sorted from largest to smallest.

   The simplest (though not the most efficient) way to do this is to store the elments in sorted order into a data structure such as Vector which implements the Enumeration interface. It would be more efficient to make treenode implement Enumeration. However it's difficult then to provide methods for Enumerations sorted in both directions.

   This exercise is a little flaky, because you can't store doubles in an Enumeration, only objects. Therefore we'll use Double objects instead.

   
   import java.util.Enumeration;
   import java.util.Vector;
   
   
   public class treenode {
   
     double data;
   
     treenode left;
     treenode right;
     
     public Enumeration largestToSmallest() {
     
       Vector v = new Vector();
       lts(v);
       return v.elements();
     
     }
     
     public Enumeration smallestToLargest() {
   
       Vector v = new Vector();
       stl(v);
       return v.elements();  
     
     }
     
     private void stl(Vector v) {
     
       if (left != null) left.stl(v);
       v.addElement(new Double(data));
       if (right != null) right.stl(v);
     
     }
   
     
     private void lts(Vector v) {
     
       if (right != null) right.lts(v);
       v.addElement(new Double(data));
       if (left != null) left.lts(v);
     
     }
   
     public treenode (double d) {
       data = d;
       left = null;
       right = null;
     }
   
     public void store (double d) {
       if (d <= data) {
         if (left == null) left = new treenode(d);
         else left.store(d);
       }
       else {
         if (right == null) right = new treenode(d);
         else right.store(d);
       }
     }
     
     public void print() {
     
       if (left != null) left.print();
       System.out.println(data);
       if (right != null) right.print();
     
     }
     
   }