Java栈——数组实现

  堆栈也有两种基本的存储结构：顺序存储结构和链式存储结构，下面我们将用数组实现栈的顺序存储结构。

当栈中没有数据元素时称为空栈；向一个栈插入元素又称为进栈或入栈；从一个栈中删

除元素又称为出栈或退栈。由于栈的插入和删除操作仅在栈顶进行，后进栈的元素必定先出

栈，所以又把堆栈称为后进先出表（Last In First Out，简称 LIFO）。可以看做现实生活中排队取钱，取号后排了老长一条队伍，等1-2小时才到你，人家VIP直接特殊对待（咳咳，可以这样理解吧！）

客官：小二，上代码！

小二：好嘞！

 

---

1.抽象一个栈接口

public interface Stack {

	//栈大小
	public int size();
	
	//栈是否为空
	public boolean isEmploy();
	
	//入栈
	public void push(Object e);
	
	//出栈
	public Object pop() throws StackEmptyException;
	
	//栈顶元素
	public Object peek() throws StackEmptyException;
}

2.自定义异常类

/*
 * 栈为空时，出栈或者取栈顶元素异常
 */
public class StackEmptyException extends RuntimeException{

	public StackEmptyException(String err){
		super(err);
	}
}

3.实现接口

public class StackArray implements Stack {

	// 栈初始大小
	private final int LEN = 8;

	// 栈元素数组
	private Object[] elements;

	// 栈顶指针
	private int top;

	public StackArray() {
		top = -1;
		elements = new Object[LEN];
	}

	/*
	 * 堆栈大小
	 */
	public int size() {
		return top + 1;
	}

	/*
	 * 判断堆栈是否为空
	 */
	public boolean isEmploy() {

		return top < 0;
	}

	/*
	 * 元素e入栈
	 */
	public void push(Object e) {
		if (size() >= elements.length)
			expandSpace();// 栈满了，扩容
		elements[++top] = e;
	}

	/*
	 * 数组满了就扩容
	 */
	public void expandSpace() {
		Object[] a = new Object[elements.length * 2];
		for (int i = 0; i < a.length; i++)
			a[i] = elements[i];
		elements = a;
	}

	/*
	 * 栈顶元素出栈
	 */
	public Object pop() throws StackEmptyException {
		if (size() < 1)
			throw new StackEmptyException("存钱罐是空的，怎么出钱");
		Object obj = elements[top];
		elements[top--] = null;
		return obj;
	}

	/*
	 * 返回栈顶元素
	 */
	public Object peek() throws StackEmptyException {
		if (size() < 1)
			throw new StackEmptyException("存钱罐是空的，怎么出钱");
		return elements[top];
	}

}