栈《数据结构--Java版》

1.基于数组的栈

public class StackClass {
	private int maxStackSize;

	private int stackTop;

	private int[] list;

	/* 默认构造函数 */
	public StackClass() {
		maxStackSize = 100;
		stackTop = 0;
		list = new int[maxStackSize];
	}

	public StackClass(int stackSize) {
		if (stackSize <= 0)
			maxStackSize = 100;
		else
			maxStackSize = stackSize;
		stackTop = 0;
		list = new int[maxStackSize];
	}

	/* 拷贝构造函数 */
	public StackClass(StackClass otherStack) {
		copy(otherStack);
	}

	public void initializeStack() {
		for (int i = 0; i < stackTop; i++) {
			list[i] = 0;
		}
		stackTop = 0;
	}

	/* 判断栈是否为空 */
	public boolean isEmptyStack() {
		return (stackTop == 0);
	}

	public boolean isFullStack() {
		return (stackTop == maxStackSize);
	}

	/* 入栈 先入再++ */
	public void push(int newItem) {
		if (isFullStack())
			throw new StackOverflowException();
		list[stackTop] = newItem;
		stackTop++;
	}

	/* 返回栈顶元素 */
	public int top() {
		if (isEmptyStack())
			throw new StackUnderflowException();
		int temp = list[stackTop - 1];
		return temp;
	}

	/* 出栈 先--后再刪 */
	public void pop() {
		if (isEmptyStack())
			throw new StackUnderflowException();
		stackTop--;
		list[stackTop] = 0;
	}

	private void copy(StackClass otherStack) {
		list = null;
		maxStackSize = otherStack.maxStackSize;
		stackTop = otherStack.stackTop;
		list = new int[maxStackSize];
		for (int i = 0; i < stackTop; i++) {
			list[i] = otherStack.list[i];
		}
	}

	/* 拷贝方法 */
	public void copyStack(StackClass otherStack) {
		if (this != otherStack)
			copy(otherStack);
	}
}

2.基于链表的栈

//栈节点类
class StackNode {
	int info;
	StackNode link;
}
//链表栈类
public class LinkedStackClass {
	private StackNode stackTop;
	public LinkedStackClass() {
		stackTop = null;
	}
	public void initializeStack() {
		stackTop = null;
	}
	/* 栈是否为空 */
	public boolean isEmptyStack() {
		return (stackTop == null);
	}
	/* 链式栈不会满 */
	public boolean isFullStack() {
		return false;
	}
	/* 入栈  如右图：*/
	public void push(int newElement) {
		StackNode newNode;
		newNode = new StackNode();
		newNode.info = newElement;
		newNode.link = stackTop;
		stackTop = newNode;
	}
	/* 返回栈顶元素 */
	public int top() throws StackUnderflowException {
		if (stackTop == null)
			throw new StackUnderflowException();
		return stackTop.info;
	}
	/* 出栈 */
	public void pop()throws StackUnderflowException{
		if(stackTop==null)throw new StackUnderflowException();
		stackTop=stackTop.link;
	}
}