CS101 Quiz 9: Solutions

  1. public abstract class Stack {
    
       abstract public boolean isEmpty();
       abstract public Object  realPop();
       abstract public void    push(Object o);
    
                public Object  pop() {
                   if (isEmpty())
                      throw new Error("Empty stack, cannot pop");
                   else
                      return realPop();
                }
    
    }
    
  2. public class ListBasedStack extends Stack {
    
       protected List list;
    
       public ListBasedStack() {
          list = null;
       }
    
       public boolean isEmpty() {
          return list == null;
       }
    
       public void push(Object o) {
          list = new List(o, list);
       }
    
       public Object realPop() {
          Object ans = list.getThing();
          list       = list.getRest();
          return ans;
       }
    }
       
    
  3. public class QueueBasedStack extends Stack {
    
       protected Queue q;
    
       public QueueBasedStack() {
          q = new Queue();
       }
    
       public boolean isEmpty() {
          return q.isEmpty();
       }
    
       public void push(Object x) {
          q.enqueue(x);
       }
    
       public Object realPop() {
          Queue save = new Queue();
          Object ans = recurpop(save);
          q = save;
          return ans;
       }
    
       /* Recurse until we find the last element on the
        * queue, which is what we want to return.
        * On the way back, save a copy of the queue -- all but the last element
        */
    
       private Object recurpop(Queue save) {
          // Assert:  q not empty here
          Object got = q.dequeue();
          Object ans = null;
          if (q.isEmpty())
             ans = got;
          else {
             save.enqueue(got);
             ans = recurpop(save);
          }
          return ans;
       }
    
       public static void selfTest() {
           QueueBasedStack qbs = new QueueBasedStack();
           for (int i=0; i<10; ++i) qbs.push(new Integer(i));
           for (int i=0; i<5;  ++i) System.out.println(qbs.pop());
           for (int i=0; i<10; ++i) qbs.push(new Integer(100+i));
           while (! qbs.isEmpty()) System.out.println(qbs.pop());
       }
    
       public static void main(String[] args) { selfTest(); }
    
    }
    
  4. abstract public class Shape {
    
       abstract public double area();
       abstract public double circumference();
    
    }
    
  5. public class Rectangle extends Shape {
    
       protected int length, width;
    
       public Rectangle(int l, int w) {
         length = l;
         width  = w;
       }
    
       public double area()          { return length * width;     }
       public double circumference() { return 2*length + 2*width; }
    }
    
  6. public class Square extends Rectangle {
    
      public Square(int s) {
         super(s,s);
      }
    }