谈谈对Java 中的栈的理解和实现,迭代器 内部类
谈谈对Java 中的栈的理解和实现,迭代器 内部类什么是栈?首先谈谈自己对栈的理解,第一次听到这个词语感觉很懵,随着后面的学习慢慢知道了什么是栈,栈在Java中是一种数据结构,用来存储数据,我们都知道Java自带了一种数据结构数组,可以直接用,而栈不同于数组,它是建立在数组上的一种数据结构(也有可能建立在链表的基础上,这个后面说),它存储数据的方式是先进后出也就是FILO(first in last out)策略的集合类型,废话不多说我们来看图
画的不好 凑合看把,我举俩个生活中很好的例子来解释一下,我们把作业交到讲台上的时候大家自觉落在一起,这样第一个同学放好以后,第二个同学的作业本就会压在第一个同学上面 以此类推,最后一个作业本交上来 老师开始审核作业,老师从上面拿的第一本作业就是最后一个同学交的,当老师查看完作业批阅后 拿出去放到一边,这个过程就是出栈,(出栈的重点是查看并删掉内容) 再举一个经典例子,玩具枪大家肯定都玩过,子弹夹就是一个栈,上子弹,第一颗子弹压人栈头,就是压栈(跟入栈一个意思),当射击时候消耗最上面第一颗子弹就是出栈 总结 栈的组成(栈的大小 栈头,栈尾,) 栈的行为(入栈,出栈) 栈的代码实现用数组实现栈(数组比较好理解,大家用的最多) 下面代码用到了泛型,对泛型不理解的同学先看一下泛型的概念 //用数组实现 栈 public class MyStack //Java不能创建泛型数组 //object 数组可以存任意类型的数据,是因为object是所有类的父类,了解一下多态 private T [] entries = (T[]) new Object[10]; //栈的大小 private int N; //获取栈的大小方法 public int size(){ return N; } //判断栈是否为空 public boolean isEmpty(){ return N == 0; } public MyStack() { super(); } //默认创建一个大小为10 的栈,也可以通过这个构造器创建一个自己想要的大小栈 public MyStack(int size) { super(); this.entries = (T[]) new Object[size]; } //动态扩容 private void resize(int max){ @SuppressWarnings("unchecked") T [] newEntries = (T []) new Object[max]; for (int i = 0; i < N; i++) { newEntries[i] = entries[i]; } entries = newEntries; } //入栈方法 public void push (T t){ if(N == entries.length){ 当栈的大小不够时,自动扩大当前空间的俩倍 resize(2*entries.length); } entries[N++] = t; } //出栈方法 public T pop(){ T element = entries[--N]; entries[--N] = null; 当栈的空间很大,但存储的内容很少等于空间的四分之时,栈空间更改为原来的二分之一 if(N > 0 && N == (entries.length / 4)){ resize(entries.length / 2); } return element; } //得到一个自己创建的迭代器 @Override public Iterator // TODO Auto-generated method stub return new ReverseArrayIterator(); } //实现自己的迭代器通过实现Iterator接口 private class ReverseArrayIterator implements Iterator private int i = N; //出栈时栈的大小会减一,所以通过判断栈是否大于0 判断是否会有下一个 @Override public boolean hasNext() { return i > 0; } //当判断有下一个元素后 获取元素 @Override public T next() { return entries[--i]; } } } 以上这种代码实现优点是不仅存储任意类型数据,还可以实现栈内存的动态扩容,动态释放空间,出栈方法中当栈存储的数据大小等于栈空间的四分之一,就让栈空间缩减到二分之一 这段代码中涉及到了内部类 和迭代器,迭代器的作用是方便遍历,可以用增强for循环 for (集合存储对象类型 集合存储对象变量 : 集合对象实例名字) { } 等价于 for(int i = 0; i < N; i++){ } 增强for循环的优点是不需要知道集合内部实现的细节,只需要知道集合对象的名字.和集合对象存储的对象类型 就行,代码也比较少 但使用增强for循环的前提是这个数据集合里面有自己的迭代器,也就是实现Iterable接口,具体的迭代器实现可以用内部类实现Iterator接口完成,内部类的优势是不占用继承,我们都知道java 是单继承, 下面给出增强for循环 原理等效代码 Stack for(String s : collection){ System.out.println(s); } 等价于下面代码 Iterator while(i.hasNext()){ String s = i.next(); System.out.println(s); } 所以forech 其实底层用调用迭代器实现的 不需要知道数据结构的底层是数组还是链表 就可以遍历 是不是很爽 下一篇博客我会介绍一下链表 和 给出链表实现栈的细节. 之后会长期更新关于数据结构和算法的内容最后补充一下:以上代码参考<<算法>>这本书,出栈方法中 需要在一开始加一个判断栈是否为空,如果为空需要抛一个异常说明,栈这种策略感觉是不是在现实生活有点不公平,先排队反而最后一个买票,但在代码中 Java虚拟机就用到了栈这种数据结构,用来存储 方法中的变量,感兴趣的同学可以去了解一下 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
