queue.java

< java软件开发>>的源代码.这是一本不错的书,尤其在java数据结构方面讲的不错.这是他的源码,很好

/*
 *  This code is from the book:
 *
 *    Winder, R and Roberts, G (2000) Developing Java
 *    Software, second edition, John Wiley & Sons.
 *
 *  It is copyright (c) 2000 Russel Winder and Graham Roberts.
 */

package ADS ;
/**
 *  A <CODE>Queue</CODE>.  The default storage mechanism is using a
 *  <CODE>SLList</CODE> but any <CODE>Sequence</CODE> may be used.
 *  The choice is made a creation time.
 *
 *  @see Sequence
 *  @version 1.4 2001.04.23
 *  @author Russel Winder
 */
public class Queue implements Container {
  /**
   *  The place to store some data.
   */
  //  Cannot be final due the implementation of clone.
  protected /*final*/ Sequence storage ;
  /**
   *  Default constructor.
   */
  public Queue() {
    this(new SLList ()) ;
  }
  /**
   *  Constructor allowing a choice of storage representation.
   *
   *  @param sequence The <CODE>Sequence</CODE> object to be used to
   *  store data.
   */
  public Queue(final Sequence sequence) {
    storage = sequence ;
  }
  /**
   *  Peek at the head of the <CODE>Queue</CODE>.
   *
   *  @exception AccessEmptyContainerException if we attempt to
   *  remove from an empty <CODE>Queue</CODE>.
   */
  Object peek() {
    if (isEmpty())
      throw new AccessEmptyContainerException() ;
    return storage.get(0) ;
  }
   /**
   *  Remove a datum from ourself.
   *
   *  @exception AccessEmptyContainerException if we attempt to
   *  remove from an empty <CODE>Queue</CODE>.
   */    
  public Object remove() {
    if (isEmpty())
      throw new AccessEmptyContainerException() ;
    Object o = storage.get(0) ;
    storage.remove(0) ;
    return o ;
  }
  /**
   *  Cause ourself to be emptied.
   */
  public void makeEmpty() {
    storage.makeEmpty() ;
  }
  /**
   *  Check to see whether we are empty or not.
   */
  public boolean isEmpty() {
    return storage.isEmpty() ;
  }
  /**
   *  Tell the world what size we are, i.e. how many
   *  <CODE>Object</CODE>s we have stored in ourself.
   */
  public int size() {
    return storage.size() ;
  }
  /**
   *  Test something against ourself for equality.
   */
  public boolean equals(final Object o) {
    if (this == o)
      return true ;
    if ((o == null) ||
        ! (o instanceof Queue) ||
        size() != ((Queue)o).size())
      return false ;
    return storage.equals(((Queue)o).storage) ;
  }
  /**
   *  Determine whether we have the value represented by the
   *  parameter <CODE>Object</CODE> in us.
   *
   *  @exception AccessEmptyContainerException if there are no
   *  items in the <CODE>Container</CODE>.
   */
  public boolean contains(Object o) {
    return storage.contains(o) ;
  }
  /**
   *  Add an element to the <CODE>Container</CODE>.
   */
  public void add(Object o) {
    storage.add(o) ;
  }
  /**
   *  Remove an element of a given value from the
   *  <CODE>Container</CODE> if it is in the <CODE>Container</CODE>.
   *
   *  @exception InvlaidOperationException is always thrown since this
   *  is an invalid operation, <CODE>Queue</CODE>s are closed
   *  containers.
   */
  public boolean remove(Object o) {
    throw new InvalidOperationException () ;
  }
  /**
   *  We have to clone ourself properly as a <CODE>Queue</CODE>.
   */    
  public Object clone() {
    try {
      Queue q = (Queue)super.clone() ;
      q.storage = (Sequence)storage.clone() ;
      return q ;
    } catch (CloneNotSupportedException e) {
      throw new InternalError () ;
    }
  }
  /**
   *  It is always useful to be able to print out the
   *  <CODE>Queue</CODE>, mostly to make debugging easy.
   */
  public String toString() {
    return storage.toString() ;
  }
  /**
   *  Even though we are a closed container, conforming to
   *  <CODE>Container</CODE> requires that we provide a public
   *  iterator.  However, we do ensure that there is no possibility of
   *  updates.
   */
  public ADS.Iterator iterator() {
    return new Iterator () ;
  }
  /**
   *  An iterator over <CODE>ArrayQueue</code>s.
   *
   *  This is just a proxy for an iterator from the underlying
   *  representation so as to stop the ability to write.  Implement
   *  only a forward iterator.
   */
  public class Iterator implements ADS.Iterator {
    /**
     *  We just need to act as a proxy for an iterator from the
     *  underlying representation.
     */
    private ADS.Iterator cursor = storage.iterator() ;
    /**
     *  Deliver the value we are currently referring to.
     */
    public final Object get() {
      return cursor.get() ;
    }
    /**
     *  Move on to the next item in the container.
     */
    public final void advance() {
      cursor.advance() ;
    }
    /**
     *  Move on n items in the container.
     */
    public final void advance(final int increment) {
      cursor.advance(increment) ;
    }
    /**
     *  Are we positioned at the beginning of the iteration?
     */
    public final boolean atBegin() {
      return cursor.atBegin() ;
    }
    /**
     *  Have we reached the end of the iteration?
     */
    public final boolean atEnd() {
      return cursor.atEnd() ;
    }
    /**
     *  Are two iterators equal, i.e. do two iterators refer to the
     *  same item in the same data structure.
     */
    public boolean equals(final ADS.Iterator i) {
      if (! (i instanceof Iterator))
        return false ;
      return (getContainer() == i.getContainer()) &&
       cursor.equals(((Iterator)i).cursor) ;
    }
    /**
     *  Return a reference to the <CODE>Container</CODE> of this
     *  <CODE>Iterator</CODE>.
     */
    public final Container getContainer() {
      return Queue.this ;
    }
    /**
     *  Clone this <CODE>Iterator</CODE>.
     */
    public final Object clone() {
      try {
        Iterator i = (Iterator)super.clone() ;
        i.cursor = (Iterator)cursor.clone() ;
        return i ;
      } catch (CloneNotSupportedException e) {
        throw new InternalError () ;
      }
    }
  }
  /**
   *  The class that provides a synchronized interface for use in
   *  multi-threaded applications.
   */
  public static class Synchronized extends Queue {
    /**
     *  The <CODE>Object</CODE> on which to do all locking.
     */
    private final Object theLock;
    /**
     *  The default constructor.  Gives an <CODE>Queue</CODE> with
     *  default initial size and increment.
     */
    public Synchronized() {
      theLock = this ;
    }
    /**
     *  The constructor that supplies an object to synchronize on.
     */
    public Synchronized(final Object o) {
      theLock = o ;
    }
    /**
     *  Remove an item from the <CODE>Queue</CODE>.
     */
    public final Object remove() {
      synchronized (theLock) { return super.remove() ; }
    }
    /**
     *  Remove the entire contents of the <CODE>Queue</CODE>.
     *
     *  This does not affect the size of the underlying array, it only
     *  removes the elements.
     */
    public final void makeEmpty() {
      synchronized (theLock) { super.makeEmpty() ; }
    }
    /**
     *  Determine whether the <CODE>Queue</CODE> is an empty one.
     */
    public final boolean isEmpty() {
      synchronized (theLock) { return super.isEmpty() ; }
    }
    /**
     *  Return the number of items in the <CODE>Queue</CODE>.
     */
    public final int size() {
      synchronized (theLock) { return super.size() ; }
    }
    /**
     *  Compare this <CODE>Queue</CODE> with another and determine
     *  whether they represent the same value, i.e. have the same item
     *  values in the same order in the <CODE>Queue</CODE>.
     */
    public final boolean equals(final Object o) {
      synchronized (theLock) { return super.equals(o) ; }
    }
    /**
     *  Determine whether we have the value represented by the
     *  parameter <CODE>Object</CODE> in us.
     *
     *  @exception AccessEmptyContainerException if there are no
     *  items in the <CODE>Queue</CODE>.
     */
    public final boolean contains(final Object o) {
      synchronized (theLock) { return super.contains(o) ; }
    }
    /**
     *  Append an element to the end of the <CODE>Queue</CODE>.
     *
     *  @exception AccessEmptyContainerException if there are no
     *  items in the <CODE>Queue</CODE>.
     */
    public final void add(final Object o) {
      synchronized (theLock) { super.add(o) ; }
    }
    /**
     *  Remove an element of a given value from the
     *  <CODE>Queue</CODE> if it is in the <CODE>Queue</CODE>.
     *
     *  @return whether the item was actually in the
     *  <CODE>Queue</CODE>.
     *
     *  @exception AccessEmptyContainerException if there are no
     *  items in the <CODE>Queue</CODE>.
     */
    public final boolean remove(final Object o) {
      synchronized (theLock) { return super.remove(o) ; }
    }
    /**
     *  Deliver up a complete shallow copy of the
     *  <CODE>Queue</CODE>.
     */
    public final Object clone() {
      synchronized (theLock) { return super.clone() ; }
    }
    /**
     *  Deliver up a <CODE>String</CODE> representation the
     *  <CODE>Queue</CODE>.
     */
    public final String toString() {
      synchronized (theLock) { return super.toString() ; }
    }
  }
}