stackadt.java

来自「国外的数据结构与算法分析用书」· Java 代码 · 共 52 行

/**	An abstract class to define a Stack ADT. */
public abstract class StackADT
{
	/**	The number of items in the stack. */
	int count;

	/**	Is the stack empty?
		Analysis: Time = O(1) */
	public boolean isEmpty()
	{
		return count == 0;
	}

	/**	Number of items that the stack can hold. */
	abstract int capacity();

	/**	Is the stack full?
		Analysis: Time = O(1) */
	public boolean isFull()
	{
		return count == capacity();
	}

	/**	The top element in the stack.
		PRECONDITION:
			!isEmpty() */
	abstract Object top() throws Exception;

	/**	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)) */
	abstract void push(Object g) throws Exception;

	/**	Remove the top item of the stack.
		PRECONDITION: 
			!isEmpty() 
		POSTCONDITION: 
			count = entry(count) - 1
			!isFull() */
	abstract void pop() throws Exception;

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