图片来自 unsplash
数组
在 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() {
}
}
}
