Java数据结构--栈的实现

Java中是没有栈这种数据结构的，如果想利用栈的先进后出（FILO），就必须自己动手实现。栈的底层可以使用数组，也可以使用Java中的容器类，如ArrayList、LinkList等。栈最常用的操作主要是压栈（push）、出栈（pop）、查看栈顶元素（peek）、判断栈是否为空（isEmpty）、返回栈的当前大小。原则上栈中有一个指针指向栈顶元素。

1、底层基于数组的栈实现：

import java.util.EmptyStackException;

public class MyStack {

	private int[] arr;  //底层数组
	private int top;  //相当于栈顶指针
	/**
	 * 无参构造方法，默认初始容量为10个整形数据大小
	 */
	public MyStack(){
		arr = new int[10];
		top = -1;
	}
	/**
	 * 含参构造方法，构造指定大小的底层数组
	 * @param size
	 */
	public MyStack(int size){
		arr = new int[size];
		top =-1;
	}
	
	/**
	 * 判断栈是否为空
	 * @return
	 */
	public boolean isEmpty(){
		return top == -1;
	}
	
	/**
	 * 压栈操作
	 * @param element
	 */
	public void push(int element){
		if(top == arr.length-1)throw new StackOverflowError();
		else arr[++top] = element;
	}
	
	/**
	 * 出栈操作
	 * @return
	 */
	public int pop(){
		if(top == -1)throw new EmptyStackException();
		else return arr[top--];
	}
	
	/**
	 * 查看栈顶元素
	 * @return
	 */
	public int peek(){
		if(top == -1)throw new EmptyStackException();
		else return arr[top];
	}
		
}

2、底层基于容器的栈的实现：

注：使用ArrayList容器作为底层来实现栈，就必须知道ArrayList的一些特性，ArrayList是基于数组实现的，默认初始容量是10，当容量不足的时候，是会自动以1.5倍扩容,所以无需担心越界的问题，ArrayList提供的一些方法会对我们实现栈有帮助。因此，下面就无需再使用栈顶指针，ArrayList中有一个随内容数量变化的size可作为指针。

import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;

public class MyCollectionStack<E extends Object>{

	private List<E> list = new ArrayList<E>();  //底层基于ArrayList的容器
	
	public MyCollectionStack(){
		
	}
	
	public boolean isEmpty(){
		return list.isEmpty();
	}
	
	public void push(E e){
		list.add(e);
	}
	
	public E pop(){
		if(list.isEmpty()) throw new EmptyStackException();
		else return list.remove(list.size()-1);
	}
	
	public E peek(){
		if(list.isEmpty()) throw new EmptyStackException();
		else return list.get(list.size()-1);
	}
	
}