arrayedstack.java

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

/**	A concrete extension of StackADT using an array for storage of the items. */
public class ArrayedStack extends StackADT
{
	/**	The items are stored in locations 0 through count - 1 of array rep. */
	private Object[ ] rep;

	/**	Allocate and initialize the array, and initialize instance variable count.
		Analysis: Time = O(1)
		PRECONDITION:
			size >= 0 
		POSTCONDITION:
			isEmpty()
			count = 0
			capacity() = size */
	public ArrayedStack(int size) throws Exception
	{
		if (size < 0)
			throw new NegativeStackSizeException("Cannot create a stack with a negative size ("
					+ size + ").");
				
		rep = new Object[size];
		count = 0;
	
		if (!isEmpty())
			throw new Exception("Newly created stack must be empty.");
		if (count != 0)
			throw new Exception("Newly created stack must have no items.");
		if (capacity() != size)
			throw new Exception("Newly created stack must have capacity equal "
					+ "to the value of the argument.");
	}

	/**	Number of items that the stack can hold.
		Analysis: Time = O(1) */
	public int capacity()
	{
		return rep.length;
	}

	/**	The top element in the stack.
		Analysis: Time = O(1) 
		PRECONDITION:
			!isEmpty() */
	public Object top() throws Exception
	{
		if (isEmpty())
			throw new Exception("Cannot call top() on an empty stack.");

		return rep[count - 1];
	}

	/**	Place g on the top of the stack.
		PRECONDITION:
			!isFull() 
		POSTCONDITION:
			!isEmpty()
			top() = g
			capacity() == entry(capacity())
			count = entry(count) + 1
			this.pop().equals(entry(this)) */
	public void push(Object g) throws Exception
	{
		if (isFull())
			throw new Exception("Cannot call push() on a full stack.");
		int entryCapacity = capacity();
		int entryCount = count;
	
		rep[count] = g;
		count++;
	
		if (isEmpty())
			throw new Exception("After a push(), a stack cannot be empty.");
		if (top() != g)
			throw new Exception("After a push(), the top item must be the "
					+ "same as the pushed item.");
		if (capacity() != entryCapacity)
			throw new Exception("After a push(), the capacity cannot change.");
		if (count != entryCount + 1)
			throw new Exception("After a push(), count must be 1 larger.");
		if (!(count >= 0 & count <= capacity()))
			throw new Exception("Count less than zero or greater than capacity().");
	}

	/**	Remove the top item of the stack.
		PRECONDITION:
			!isEmpty() 
		POSTCONDITION:
			count = entry(count) - 1 
			!isFull() */
	public void pop() throws Exception
	{
		if (isEmpty())
			throw new Exception("Cannot call pop() on an empty stack.");
		int entryCount = count;
	
		count--;
	
		if (count != entryCount - 1)
			throw new Exception("After a pop(), count must be 1 smaller.");
		if (isFull())
			throw new Exception("After a pop(), a stack cannot be full.");
		if (!(count >= 0 & count <= capacity()))
			throw new Exception("Count less than zero or greater than capacity().");
	}

/** INVARIANT:
	(count >= 0) & (count <= capacity())
	isEmpty() == (count == 0) */
}