算法系列笔记（一）栈的实现

今天我们先来学习一下栈的完整实现方式

首先先上代码

public class Stack<T> {
    private int n=0;
    private T[]a;
    public Stack(int c) {
        a=(T[])new Object[c];
    }
    public void push(T d){
        if(n==a.length)resize(3*a.length);
        a[n++]=d;
    }
    public T top(){
        return a[--n];
    }
    public void resize(int size){
        T[] temp=(T[])new Object[size];
        for(int i=0;i<n;i++){
            temp[i]=a[i];
        }
        a=temp;
    }   
}

这是实现了泛型和不定容的栈，内部实现的思路很简单，其实就是用一个数组的操作来模拟实现而已。唯一有趣的就是就是resize实现方式，是重新new一个数组然后将内容原有内容复制过去，然后再将a指针的指向新的数组中

迭代器

然而完整的stack实现是需要迭代器的，迭代器可以为遍历栈元素提供优雅而高效的解决方案。
有了它你就可以类似这样使用

Iterator<xx>i=cc.iterator();           //cc是实现迭代器的类的一个对象
while(i.hasNext()){
    xx s=i.next();
    System.out.println(s);
}
或者
for(xx s:cc){
  #coding...
}

要要让类拥有迭代器就很有趣了，因为它要涉及两个接口 Iterable<> 和Iterator<>
Iterable是可迭代化的意思，Iterator是迭代器的意思。
是的，如果你想要集合A实现迭代器操作，你的A实现Iterable接口以外，A中必须要有一个内部类B实现Iterator接口，为A提供确实的迭代器操作

下面分别介绍两个接口

Iterable<T>方法：

public Iterator<T>iterator(){
return   B;                                   //B是实现Iterator接口的迭代器
}

Iterator<T>

• boolean hasNext() 判断是否下一个元素
• T next() 返回下一个元素
• void remove() 删除元素

最后用一个实现迭代器的完整代码结束这篇文章，（remove操作有点麻烦，就没写了，不过思路大概是删除元素要将之后的所有元素往前移动一格）
这是一个顺序迭代器

import java.util.Iterator;

public class Stack<T>implements Iterable<T> {
    private int n=0;
    private T[]a;
    public Stack(int c) {
        a=(T[])new Object[c];
    }
    public int size(){
        return n;
    }
    public boolean isempty(){
        return n==0;
    }
    public void push(T d){
        if(n==a.length)resize(3*a.length);
        a[n++]=d;
    }
    public T top(){
        return a[--n];
    }
    public void resize(int size){
        T[] temp=(T[])new Object[size];
        for(int i=0;i<n;i++){
            temp[i]=a[i];
        }
        a=temp;
    }
    public Iterator<T>iterator(){
        return new Itr();
    }
    private class Itr implements Iterator<T>{
        private int i=n;
        private int j=-1;
        public boolean hasNext(){
            return j<(i-1);
        }
        public T next(){
            return a[++j];
        }
        public void remove(){
            
        }
    }
}