数组

在 Java 中本来就有数组对象 , 但是这里我们不用 .

额 , 好吧其实数组就是想这样的 :

String[] strs = ["a","b","c"];

在讲链表的时候就说过 , 数组和链表 , 数组地址连续 , 链表地址可以不连续 . 这就使得数组查询的效率比链表高 , 因为链表只能从第一个元素开始查询 , 而数组只需要知道首地址和索引就可以了快速定位 .

但是有优点必有缺点 , 数组因为地址连续的优势而查询快 , 但也因为这个特性 , 增加删除操作就比链表复杂的多 . 链表只需要设置一下没一个节点的next属性 , 双向链表还要考虑prev这个属性 ( 关于next和prev可以看看前面几篇文章 ) .

而数组呢 ?

拿增加元素的操作举例 , 增加一个元素 , 想想是不是直接在相应的位置插进去就行了 ? 其实没这么简单 , 因为查询的时候 , 我们还会用到索引东西 , 在数组中间插入一个元素 , 这个元素后界面的元素的索引全都要变 . 删除数据的操作也是这样 , 索引也都会变 . 这里就涉及到性能的问题了 , 因为重新设置索引很费时费力的 .

数组实现栈 , 队列 , 背包

好了 , 现在知道数组是什么了 , 前面我们用链表实现了栈 , 队列和背包 , 现在同样用数组来实现一次 .

栈 ( Stack )

突然发现前面有一篇文章已经讲过栈的实现 , 那这里就不说了, 直接放链接:

算法与数据结构:栈的实现及运用

队列 ( Queue )

方法列表

void enqueue(Item item) : 加入新元素节点到队列 .
Item dequeue() : 删除最早进入队列的元素节点 .
boolean isEmpty() : 判断队列是否为空 .
int size() : 返回队列长度 .

public class Queue<Item> implements Iterable<Item> {

    private Item[] items = (Item[]) new Object[1];

    private int length = 0;

    public Queue() {
    }

    public void enqueue(Item item) {
        if (this.length == this.items.length) {
            resize(2 * this.items.length);
        }
        items[length++] = item;
    }

    private void resize(int max) {
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < this.length; i++) {
            temp[i] = items[i];
        }
        items = temp;
    }

    public Item dequeue() {
        Item item = items[this.length - 1];
        items[--this.length] = null;
        if (this.length == this.items.length / 4) {
            resize(this.items.length / 2);
        }
        return item;
    }

    public boolean isEmpty() {
        return this.length == 0;
    }

    public int size() {
        return this.length;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ReverseArrayIterator<Item>();
    }
    
    private class ReverseArrayIterator<Item> implements Iterator<Item>{

        private int i = length;
        
        @Override
        public boolean hasNext() {
            return i>0;
        }

        @Override
        public Item next() {
            return (Item) items[--i];
        }

        @Override
        public void remove() {
            
        }
    }
    
}

这里有一个私有的resize(int max)方法 , 用来实现自动改变容量 .

背包 ( Bag )

方法列表

void add(Item item) : 添加新元素节点到背包 .
boolean isEmpty() : 判断背包是否为空 .
int size() : 返回背包大小 .

public class Bag<Item> implements Iterable<Item> {

    private int length = 0;
    private Item[] items = (Item[]) new Object[1];

    public Bag(){}

    public void add(Item item){
        if(this.length == this.items.length){
            resize(2*this.items.length);
        }
        items[this.length++] = item;
    }

    private void resize(int max){
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0;i<this.length;i++){
            temp[i] = items[i];
        }
        items = temp;
    }
    
    public boolean isEmpty(){
        return this.length==0;
    }

    public int size(){
        return this.length;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ReverseArrayIterator<Item>();
    }

    private class ReverseArrayIterator<Item> implements Iterator<Item>{

        private int i = length;

        @Override
        public boolean hasNext() {
            return i>0;
        }

        @Override
        public Item next() {
            return (Item) items[--i];
        }

        @Override
        public void remove() {

        }
    }
}