[Java与数据结构]栈

栈的应用：1.撤销 2.程序调用的系统栈 3.括号匹配

栈的实现:

Stack
void push(E)
E pop()
E peek()
int getSize()
boolean isEmpty()

public class ArrayStack implements Stack {
    Array_E array;
    public ArrayStack(int capacity){
        array = new Array_E<>(capacity);
    }
    public ArrayStack(){
        array=new Array_E<>();
    }

    @Override
    public int getSize(){
        return array.getSize();
    }

    @Override
    public boolean isEmpty(){
        return array.isEmpty();
    }

    public int getCapacity(){
        return array.getCapacity();
    }

    @Override
    public void push(E e){
        array.addLast(e);
    }
    @Override
    public E pop(){
        return array.removeLast();
    }
    public E peek(){
        return array.getLast();
    }
    public String toString(){
        StringBuilder res=new StringBuilder();
        res.append("stack:");
        res.append('[');
        for(int i=0;i stack=new ArrayStack<>();
        for(int i=0;i<5;i++){
            stack.push(i);
            System.out.println(stack);
        }
        stack.pop();
        System.out.println(stack);
    }
    }

public class Array_E {
    private E[] data;
    private int size;

    //构造函数，传入数组的容量capacity构造Array
    public Array_E(int capacity){
        //java中所有类都是object的子类
        data=(E[]) new Object[capacity];
        size=0;
    }
    //无参数的构造函数，默认数组的容量capacity=10
    public Array_E(){
        this(10);
    }
    //获取数组的元素个数
    public int getSize(){
        return size;
    }
    //获取数组的容量
    public int getCapacity(){
        return data.length;
    }
    //返回数组是否为空
    public boolean isEmpty(){
        return size==0;
    }
    //向所有元素后添加一个新元素
    public void addLast(E e){
        if(size==data.length)
            throw new IllegalArgumentException("AddLast failed.Array is full.");
        data[size]=e;
        size++;
    }
    //向指定位置添加元素
    public void add(int index,E e){
        if(index<0||index>size)
            throw new IllegalArgumentException("Add failed.Require index>0||index<=size.");
        if(size==data.length)
            resize(2*data.length);
        for(int i=size-1;i>=index;i--)
            data[i+1]=data[i];
        data[index]=e;
        size++;
    }
    //获取index索引位置的元素
    public E get(int index){
        if(index<0||index>=size)
            throw new IllegalArgumentException("Get failed,Index is illegal.");
        return data[index];
    }

    public void set(int index,E e){
        if(index<0||index>size)
            throw new IllegalArgumentException("Get failed,Index is illegal.");
        data[index]=e;
    }
    //查找数组中是否有e
    public boolean contains(E e){
        for(int i=0;isize)
            throw new IllegalArgumentException("Get failed,Index is illegal.");
        for(int i=index;i arr=new Array_E<>();
        return arr.remove(size);
    }
    public E getLast(){
        return get(size-1);
    }
    public E getFirst(){
        return get(0);
    }
    @Override
    public String toString(){
        StringBuilder res=new StringBuilder();
        res.append(String.format("Array:size= %d ,capacity= %dn",size,data.length));
        res.append('[');
        for(int i=0;i arr=new Array_E(20);
        for(int i=0;i<10;i++)
            arr.addLast(i);
        System.out.println(arr.contains(5));
        System.out.println(arr.find(5));
        arr.remove(5);
        System.out.println(arr);
    }
}