×
文章路径: Java > 数据结构

栈java实现

发表于3年前(Dec 24, 2014 10:23:52 AM)  阅读 459  评论 0

分类: Java 数据结构

标签: lifo stack 后进先出

栈是一种后进先出(LIFO,last in first out)的数据集合。可以把栈看成餐馆中用来放盘子的、里面安装了弹簧的栈,盘子弹出的顺序跟被压入的顺序正好相反,因为在每一时刻,只有最顶上的盘子是可以拿到的。

栈中操作元素的方法通常为两种,压入(push)与弹出(pop)。先下的代码用java数组实现了栈,加入了栈的自动增长,关于自动增长要说的是,有些算法对于自动增长的时机以及自动增长的容量有特殊研究,这里只是简单的采用当数组满后将数组长度翻倍的做法。代码中自定义的异常StackOverFlowException只是简单实现了RuntimeException中的String构造方法,这里就不再给出,读者可以自行使用RuntimeException替代。对于泛型的使用请参考java中关于泛型的用法。

package cangzhitao.com.algorithms.datastructure;

import cangzhitao.com.algorithms.datastructure.exception.StackOverFlowException;

/**
 * 栈的数组实现,允许自动增长
 * @author lihui
 *
 */
public class Stack<T> {

	/**
	 * 对象数组,用来存储值
	 */
	private T[] arrays;

	/**
	 * 栈的容量,默认为10
	 */
	private int capacity = 10;

	/**
	 * 栈的元素个数
	 */
	private int size = 0;

	/**
	 * 栈元素满后,是否自动增长,默认为不增长
	 */
	private boolean autoGrow = false;

	/**
	 * 创建一个栈,使用默认容量
	 */
	public Stack() {
		//java中不允许创建泛型数组,这里用了强转,违背了泛型的初衷
		arrays = initArray(capacity);
	}

	/**
	 * 创建一个容量为capacity的栈
	 * @param capacity 长度
	 */
	public Stack(int capacity) {
		this.capacity = capacity;
		arrays = initArray(capacity);
	}

	/**
	 * 创建一个容量为capacity的栈,自动增长属性为autoGrow
	 * @param capacity
	 * @param autoGrow
	 */
	public Stack(int capacity, boolean autoGrow) {
		this(capacity);
		this.autoGrow = autoGrow;
	}

	/**
	 * 初始化数组
	 * @param capacity
	 * @return 泛型数组
	 */
	@SuppressWarnings("unchecked")
	private T[] initArray(int capacity) {
		return (T[]) new Object[capacity];
	}

	/**
	 * 设置栈capacity是否能自动增长
	 * @param autoGrow
	 */
	public void setAutoGrow(boolean autoGrow) {
		this.autoGrow = autoGrow;
	}

	/**
	 * 获得当前栈的容量
	 * @return
	 */
	public int getCapacity() {
		return capacity;
	}

	/**
	 * 获得当前栈的元素数量
	 * @return
	 */
	public int getSize() {
		return size;
	}

	/**
	 * 栈的容量翻倍
	 */
	private void expand() {
		capacity = capacity*2;
		T[] newArray = initArray(capacity);
		for(int i=0;i<size;i++) {
			newArray[i] = arrays[i];
		}
		arrays = null;
		arrays = newArray;
	}

	/**
	 * 栈是否为空
	 * @return
	 */
	public boolean isEmpty() {
		if(size==0) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 * 栈是否满员
	 * @return
	 */
	public boolean isFull() {
		if(size==capacity) {
			return true;
		} else {
			return false;
		}
	}

	/**
	 * 往栈中压入元素,返回栈本身
	 * @param o
	 * @return
	 */
	public Stack<T> push(T o) {
		//检查是否已满
		boolean isFull = isFull();
		if(isFull) {
			//自动增长
			if(autoGrow) {
				expand();
			//抛出异常
			} else {
				throw new StackOverFlowException("栈只能存储"+size+"个元素,已满");
			}
		}
		//压入元素
		arrays[size] = o;
		size ++;
		return this;
	}

	/**
	 * 弹出栈顶元素
	 * @return
	 */
	public T pop() {
		boolean isEmpty = isEmpty();
		//为空抛出异常
		if(isEmpty) {
			throw new StackOverFlowException("栈已为空");
		}
		size--;
		T o = arrays[size];
		arrays[size] = null;
		return o;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Stack<Integer> a = new Stack<Integer>(2,true);
		a.push(1).push(2).push(3);
		while(!a.isEmpty()) {
			System.out.println(a.pop());
		}

	}

}

发表评论