java以数组为底层数据结构创建自己的栈
栈可以解决什么问题呢:
1.括号匹配问题
2.递归
3.表达式求值问题
首先明确栈的功能:
1.入栈:给底层数组的尾部插入元素相当于入栈
2.出栈:把底层数组的最后一个元素提出来相当于出栈
3.获取栈长度:获取size
4.判断栈是否为空:底层数组size==0则为空
5.获取栈顶:返回底层数组的最后一个元素
由于底层结构是数组,我们也可以用别的结构来创建这个栈,但是栈的方法总归是这么些个,所以我们需要把这些方法写在接口里,然后用数组栈来实现这个接口的功能
接口:
public interface selfstack <T> {
//入栈
void push(T e);
//出栈
T pop();
//查看栈顶元素
T peak();
//判断是否为空
boolean IsEmpty();
//获取栈中元素的个数
int geiSize();
}
ArrStack:文章来源:https://www.toymoban.com/news/detail-807528.html
public class ArrStack<T> implements selfstack<T> {
//底层用上一篇我们自己写的数组
private MyArrary<T> data; //容器
private int size;
//默认构造方法为创建一个100大小的自己数组
public ArrStack(){
this.data=new MyArrary<T>(100);
this.size=0;
}
public void push(T e) {
//调用自己数组的向尾部添加元素,这样子效率较高,如果向头部添加元素还需要往后推移
this.data.adddata(e);
this.size++;
}
//出栈
public T pop() {
T e=this.data.getindexdata(size-1); //先保存这个元素
this.data.delete(this.size-1); //然后删除
this.size--; //长度减一
return e;
}
//返回栈顶元素
public T peak() {
return this.data.getindexdata(this.size-1);
}
//判断栈是否为空
public boolean IsEmpty() {
return this.size==0;
}
//获取栈实际长度
public int geiSize() {
return this.size;
}
}
测试:文章来源地址https://www.toymoban.com/news/detail-807528.html
public class stacktest<T> {
public void test(selfstack stack, List<T> list){
//开始时间
long startTime=System.nanoTime();
//入栈
for (int i = 0; i < list.size(); i++) {
stack.push(list.get(i));
}
System.out.println("栈中元素个数:"+stack.geiSize());
//出栈
while(!stack.IsEmpty()){
T e= (T) stack.pop();
System.out.print("--->"+e);
}
//结束时间
long endTime=System.nanoTime();
System.out.println("总耗时:"+(endTime-startTime)/1000000000.0+"s");
}
public static void main(String[] args) {
stacktest<Integer> st=new stacktest<Integer>();
selfstack<Integer> stack=new ArrStack<Integer>(); //继承了selftack的ArrStack来实现selfstack
List<Integer> list=new ArrayList<Integer>();
Random r=new Random();
for (int i = 0; i < 100; i++) {
list.add(r.nextInt(100));
}
list.add(100);
st.test(stack,list);
}
}
到了这里,关于用java以数组为底层数据结构创建自己的栈的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!