queueuos.java

国外的数据结构与算法分析用书

/* QueueUos.java
 * ---------------------------------------------
 * Copyright (c) 2001 University of Saskatchewan
 * All Rights Reserved
 * --------------------------------------------- */

package dslib.dispenser;

import dslib.exception.*;
import dslib.list.LastListUos;
import dslib.base.DispenserUos;

/**	A dispenser which stores items of Object type.  It has the 'first 
	in, first out' behavior typical of a queue.  Item refers to the 
	item at the front of the queue, which can be deleted.  There 
	are also routines to insert items and check for empty.
	Implementation based on a LastListUos. */
public abstract class QueueUos implements DispenserUos
{
	/**	The internal representation for the queue. */
	protected LastListUos rep;

	/**	Return the item at the front of the queue. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			!itemExists()
		</ul> */
	public Object item() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot return an item since no current item exists.");
		
		return rep.firstItem();
	}
  
	/**	Is there an item in the queue?. <br>   
		Analysis: Time = O(1) */
	public boolean itemExists()
	{
		return !rep.isEmpty();
	}
  
	/**	Is the queue empty?. <br>  
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return rep.isEmpty();
	}
  
	/**	Is the queue full?. <br>   
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return rep.isFull();
	}
 
	/**	Insert x at the end of the queue. <br>  
		Analysis: Time = O(1) <br>
		@param x item to be inserted */
	public void insert(Object x) 
	{
		rep.insertLast(x);
	}

	/**	Delete the item at the front of the queue. <br>
 		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists()
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot delete item since no current item exists.");
		
		rep.deleteFirst();
	}

	/**	Remove all items from the queue. <br> 
		Analysis: Time = O(1) */
	public void wipeOut()
	{
		rep.wipeOut();
	}

	/**	String representation of the contents of the queue. <br>  
		Analysis: Time = O(n), where n = number of items in the queue */
	public String toString()
	{
		return "Queue contents starting with" + " current item:  " + rep.toString();
	}

	/**	A shallow clone of this object. <br> 
		Analysis: Time = O(1) */
	public Object clone()
	{
		try
		{
			return super.clone();
		} catch (CloneNotSupportedException e)
		{
			// Should not occur: this is a ContainerUos, which implements Cloneable 
			e.printStackTrace();
 			return null;
		}
	}
}