谈谈对Java 中的栈的理解和实现,迭代器内部类

什么是栈?

首先谈谈自己对栈的理解,第一次听到这个词语感觉很懵,随着后面的学习慢慢知道了什么是栈,栈在Java中是一种数据结构,用来存储数据 ,我们都知道Java自带了一种数据结构数组,可以直接用,而栈不同于数组,它是建立在数组上的一种数据结构(也有可能建立在链表的基础上,这个后面说),它存储数据的方式是先进后出也就是FILO(first in last out)策略的集合类型,废话不多说我们来看图
谈谈对Java 中的栈的理解和实现,迭代器内部类

画的不好凑合看把,我举俩个生活中很好的例子来解释一下,我们把作业交到讲台上的时候大家自觉落在一起,这样第一个同学放好以后,第二个同学的作业本就会压在第一个同学上面以此类推,最后一个作业本交上来老师开始审核作业,老师从上面拿的第一本作业就是最后一个同学交的,当老师查看完作业批阅后拿出去放到一边,这个过程就是出栈,(出栈的重点是查看并删掉内容)
再举一个经典例子,玩具枪大家肯定都玩过,子弹夹就是一个栈,上子弹,第一颗子弹压人栈头,就是压栈(跟入栈一个意思),当射击时候消耗最上面第一颗子弹就是出栈
总结

栈的组成(栈的大小栈头,栈尾,)
栈的行为(入栈,出栈)

栈的代码实现

用数组实现栈(数组比较好理解,大家用的最多)
下面代码用到了泛型,对泛型不理解的同学先看一下泛型的概念

//用数组实现 栈
public class MyStack<T> implements Iterable<T>{   
//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<T> iterator() {
  // TODO Auto-generated method stub
  return new ReverseArrayIterator();
 }
 //实现自己的迭代器通过实现Iterator接口
  private class ReverseArrayIterator implements Iterator<T>{
   
   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<String> collection = new Stack<>();
  for(String s : collection){
   System.out.println(s);
  }
  等价于下面代码
  Iterator<String> i = collection.iterator();
  while(i.hasNext()){
   String s = i.next();
   System.out.println(s);
  }

所以forech 其实底层用调用迭代器实现的不需要知道数据结构的底层是数组还是链表就可以遍历是不是很爽

下一篇博客我会介绍一下链表和给出链表实现栈的细节. 之后会长期更新关于数据结构和算法的内容

最后补充一下:以上代码参考<<算法>>这本书,出栈方法中需要在一开始加一个判断栈是否为空,如果为空需要抛一个异常说明,栈这种策略感觉是不是在现实生活有点不公平,先排队反而最后一个买票,但在代码中 Java虚拟机就用到了栈这种数据结构,用来存储方法中的变量,感兴趣的同学可以去了解一下

谈谈对Java 中的栈的理解和实现,迭代器 内部类