stackuos.java

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

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

package dslib.dispenser;

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

/**	A dispenser for items of Object type.  It has the last in, first out structure
	typical of a stack.  Item refers to the top item of the stack and it can be
	deleted.  There are also methods to insert items and check for empty.
	Implementation to be based on a SimpleListUos. */
public abstract class StackUos implements DispenserUos
{
	/**	The internal representation of the stack. */
	protected SimpleListUos rep;

	/**	Return the item on top of the stack. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public Object item() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Must be a current item");

		return rep.firstItem();
	}

	/**	Is there an item in the stack?. <br> 
		Analysis: Time = O(1) */
	public boolean itemExists()
	{
		return !isEmpty();
	}

	/**	Is the stack empty?. <br>
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return rep.isEmpty();
	}

	/**	Is the stack full?. <br>
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return rep.isFull();
	}

	/**	Insert x at the top of the stack. <br>
		Analysis: Time = O(1) 
		@param x new item to be inserted */
	public void insert(Object x) 
	{
		rep.insertFirst(x);
	}

	/**	Delete the item on top of the stack. <br>
		Analysis: Time = O(1) <br>
		PRECONDITION: <br>
		<ul>
			itemExists() 
		</ul> */
	public void deleteItem() throws NoCurrentItemUosException
	{
		if (!itemExists())
			throw new NoCurrentItemUosException("Cannot delete an item that does not exist.");

		rep.deleteFirst();
	}

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

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

	/**	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 that implements Cloneable. */ 
			e.printStackTrace();
			return null;
		}
	}
}