數(shù)組
在 Java 中本來(lái)就有數(shù)組對(duì)象 , 但是這里我們不用 .
額 , 好吧其實(shí)數(shù)組就是想這樣的 :
String[] strs = ["a","b","c"];
在講鏈表的時(shí)候就說(shuō)過 , 數(shù)組和鏈表 , 數(shù)組地址連續(xù) , 鏈表地址可以不連續(xù) . 這就使得數(shù)組查詢的效率比鏈表高 , 因?yàn)殒湵碇荒軓牡谝粋€(gè)元素開始查詢 , 而數(shù)組只需要知道首地址和索引就可以了快速定位 .
但是有優(yōu)點(diǎn)必有缺點(diǎn) , 數(shù)組因?yàn)榈刂愤B續(xù)的優(yōu)勢(shì)而查詢快 , 但也因?yàn)檫@個(gè)特性 , 增加刪除操作就比鏈表復(fù)雜的多 . 鏈表只需要設(shè)置一下沒一個(gè)節(jié)點(diǎn)的next屬性 , 雙向鏈表還要考慮prev這個(gè)屬性 ( 關(guān)于next和prev可以看看前面幾篇文章 ) .
而數(shù)組呢 ?
拿增加元素的操作舉例 , 增加一個(gè)元素 , 想想是不是直接在相應(yīng)的位置插進(jìn)去就行了 ? 其實(shí)沒這么簡(jiǎn)單 , 因?yàn)椴樵兊臅r(shí)候 , 我們還會(huì)用到索引東西 , 在數(shù)組中間插入一個(gè)元素 , 這個(gè)元素后界面的元素的索引全都要變 . 刪除數(shù)據(jù)的操作也是這樣 , 索引也都會(huì)變 . 這里就涉及到性能的問題了 , 因?yàn)橹匦略O(shè)置索引很費(fèi)時(shí)費(fèi)力的 .
數(shù)組實(shí)現(xiàn)棧 , 隊(duì)列 , 背包
好了 , 現(xiàn)在知道數(shù)組是什么了 , 前面我們用鏈表實(shí)現(xiàn)了棧 , 隊(duì)列和背包 , 現(xiàn)在同樣用數(shù)組來(lái)實(shí)現(xiàn)一次 .
棧 ( Stack )
突然發(fā)現(xiàn)前面有一篇文章已經(jīng)講過棧的實(shí)現(xiàn) , 那這里就不說(shuō)了, 直接放鏈接:
算法與數(shù)據(jù)結(jié)構(gòu):棧的實(shí)現(xiàn)及運(yùn)用
隊(duì)列 ( Queue )
方法列表
-
void enqueue(Item item): 加入新元素節(jié)點(diǎn)到隊(duì)列 . -
Item dequeue(): 刪除最早進(jìn)入隊(duì)列的元素節(jié)點(diǎn) . -
boolean isEmpty(): 判斷隊(duì)列是否為空 . -
int size(): 返回隊(duì)列長(zhǎng)度 .
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() {
}
}
}
這里有一個(gè)私有的resize(int max)方法 , 用來(lái)實(shí)現(xiàn)自動(dòng)改變?nèi)萘?.
背包 ( Bag )
方法列表
-
void add(Item item): 添加新元素節(jié)點(diǎn)到背包 . -
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() {
}
}
}
