C# · 12月 20, 2021

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

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

什么是栈?

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

画的不好 凑合看把,我举俩个生活中很好的例子来解释一下,我们把作业交到讲台上的时候大家自觉落在一起,这样第一个同学放好以后,第二个同学的作业本就会压在第一个同学上面 以此类推,最后一个作业本交上来 老师开始审核作业,老师从上面拿的第一本作业就是最后一个同学交的,当老师查看完作业批阅后 拿出去放到一边,这个过程就是出栈,(出栈的重点是查看并删掉内容)

再举一个经典例子,玩具枪大家肯定都玩过,子弹夹就是一个栈,上子弹,第一颗子弹压人栈头,就是压栈(跟入栈一个意思),当射击时候消耗最上面第一颗子弹就是出栈

总结

栈的组成(栈的大小 栈头,栈尾,)

栈的行为(入栈,出栈)

栈的代码实现

用数组实现栈(数组比较好理解,大家用的最多)

下面代码用到了泛型,对泛型不理解的同学先看一下泛型的概念

//用数组实现 栈

public class MyStack implements Iterable{

//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 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 collection = new Stack();

for(String s : collection){

System.out.println(s);

}

等价于下面代码

Iterator i = collection.iterator();

while(i.hasNext()){

String s = i.next();

System.out.println(s);

}

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

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

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