java数据结构之java实现栈
* @author skip ...
import java.util.arrays;
/**
* 栈的实现<br>
* @author skip
* @version 1.0
*/
public class stack<t> {
private int size; //栈中元素的个数
private object[] arr; //底层数组
private final int defaultlength = 200; //默认长度
/**
* 无参构造,使用默认长度初始化数组
*/
public stack(){
arr = new object[defaultlength];
size = 0;
}
/**
* 使用长度参数初始化数组
* @param length 长度
*/
public stack(int length){
arr = new object[length];
size = 0;
}
/**
* 入栈
* @param element 数据
*/
public void push(t element){
//是否需要扩容
if(size >= arr.length){
//数组扩容
extendcapacity(size+1);
}
arr[size++] = element;
}
/**
* 出栈
* @return 数据
*/
@suppresswarnings("unchecked")
public t pop(){
//元素个数为0,无法执行出栈操作
if(size==0){
return null;
}
t t = (t)arr[size-1];
arr[--size] = null; //数据已出栈,还原为null
return t;
}
/**
* 清空栈
*/
public void clear(){
for(int i=0;i<size;i++){
arr[i]=null;
}
size = 0;
}
/**
* 获得当前栈中元素的个数
* @return 元素的个数
*/
public int getsize(){
return size;
}
/**
* 判断是否为空栈
* @return 空为true,非空为false
*/
public boolean isempty(){
return size == 0;
}
/**
* 打印栈中所有的元素
*/
@suppresswarnings("unchecked")
public void printstack(){
for(int i=0;i<size;i++){
system.out.print(((t)arr[i]).tostring());
}
system.out.println();
}
/**
* 扩容
* @param length 需要的长度
*/
private void extendcapacity(int length){
//当前数组长度和需要的长度取最大
int mincapacity = math.max(arr.length, length);
//判断是否需要扩容
if(mincapacity - arr.length>0){
//数组长度增加一半
int newlength = arr.length + arr.length/2;
//如果新的长度还比需求要小,将需求的长度作为数组长度
if(newlength < mincapacity){
newlength=mincapacity;
}
//数组长度不能超过integer.max_value
if(newlength > integer.max_value - 8){
newlength = integer.max_value;
}
//数组扩容
arr = arrays.copyof(arr, newlength);
}
}
}