第3章 表块攒、棧和隊(duì)列
抽象數(shù)據(jù)類型（abstract data type,ADT）是帶有一組操作的對(duì)象的集合陪白。
數(shù)組實(shí)現(xiàn)表的擴(kuò)容：
int[] newArr=new int[arr.length*2];
for(int i=0;i<arr.length;i++)
newArr[i]=arr[i];
arr=newArr;
3.3 Java Collections API中的表
ADT的添加刪除總結(jié)：
l 迭代器刪除remove刪除由next()最新返回的項(xiàng)，此后不能再執(zhí)行remove()直到對(duì)next()的再一次調(diào)用。
迭代器刪除知道確切的位置，比容器類刪除具有更高的效率。
使用迭代器或增強(qiáng)for循還匀归，若正在被迭代的集合進(jìn)行結(jié)構(gòu)上的改變（add/remove/clear），那么迭代器就不再合法拋出CurrentModificationException異常耗帕。
基于以上迭代器的兩個(gè)優(yōu)點(diǎn)穆端，迭代器使用原則是：迭代器只有在立即使用時(shí)才獲取，迭代器調(diào)用自己的remove方法是合法的兴垦。
遍歷有3種方法：迭代器徙赢、增強(qiáng)for、索引號(hào)探越。
l 空器接口add/remove具為遍歷式刪除狡赐。當(dāng)集合不允許重復(fù)，要?jiǎng)h除的元素不在集合中時(shí)返回false钦幔。
l List接口具有Collections方法枕屉、索引式增刪改查、listIterator鲤氢。
靜態(tài)函數(shù)寫法：public搀擂、static、泛型卷玉、返回值哨颂、函數(shù)名、形參相种。
容器類Collections接口：判長(zhǎng)空置空威恼，添刪容迭。Collections接口是Iterable接口的繼承類可以使用增強(qiáng)for循還寝并。
public interface Collection<AnyType> extends Iterable<AnyType>{
int size();
boolean isEmpty();
void clear();
boolean add(AnyType x);
boolean remove(AnyType x);
boolean contains(AnyType x);
java.util.Iterator<AnyType> iterator();
}
迭代器Iterator接口：
public interface <AnyType> Iterator{
boolean hasNext();
AnyType next();
void remove();
}
List接口：list接口添加了索引式的增刪改查方法(add/remove/set/get)和listIterator迭代器箫措。
public interface List<AnyType> extends Collection<AnyType>{
void add(int idx,AnyType x);
void remove(int idx,AnyType x);
AnyType set(int idx,AnyType x);
AnyType get(int idx);
ListIterator<AnyType> listIterator(int pos);
}
List的ArrayList實(shí)現(xiàn)，get/set花費(fèi)O(1)衬潦。add/remove花費(fèi)昂貴斤蔓，除非變動(dòng)在ArrayList的末端執(zhí)行。
List的雙鏈表LinkedList實(shí)現(xiàn)镀岛，在變動(dòng)項(xiàng)位置已知的情況下add/remove花費(fèi)很小弦牡。表的前端add/remove花費(fèi)常數(shù)時(shí)間友驮，因而LinkedList提供了addFirst/removeFirst/addLast/removeLast方法。get/set調(diào)用花費(fèi)O(N)喇伯，除非調(diào)用接近表的端點(diǎn)喊儡。
對(duì)于搜索ArrayList和LinkedList實(shí)現(xiàn)Collections的contains和remove方法均花費(fèi)O(N)拨与。
ArrayList有容量的概念稻据，添加需要調(diào)用ensureCapacity()，添加完調(diào)用trimToSize()節(jié)約空間买喧。
插入刪除的實(shí)現(xiàn)選擇：
l 末端add/remove用ArrayList,LinkedList均可捻悯。
l 首端add/remove用LinkedList，此時(shí)ArrayList表現(xiàn)最差淤毛。
l 已知索引處add/remove用LinkedList今缚。
未知索引處添加：要比較ArrayList的移動(dòng)效率和LinkedList的遍歷效率
l 遍歷情況：ArrayList用索引號(hào)、迭代器均可O(N)低淡，LinkedList只能用迭代器O(N)姓言。LinkedList用索引號(hào)遍歷將花費(fèi)O(N^2)。
實(shí)際表現(xiàn)ArrayList性能優(yōu)于LinkedList蔗蹋。
程序計(jì)時(shí)：
long startTime=System.currentTimeMillis();
long endTime=System.currentTimeMillis();
System.out.println("程序運(yùn)行時(shí)間： "+(endTime-startTime)+"ms");
去除數(shù)組偶數(shù)值何荚，練習(xí)LinkedList的remove方法
一種想法是將奇數(shù)拷到新表，清空原表猪杭，再將奇數(shù)拷回原表餐塘。
另一種想法使用增強(qiáng)for循還，過(guò)程中刪除元素將拋異常皂吮。
另一種想法是使用索引號(hào)遍歷戒傻，ArrayList花費(fèi)O(N)，而LinkedList花費(fèi)O(N^2)更糟糕：
public static void removeEvensVer1(List<Integer> lst){
for(int i=0;i<lst.size();){
if(lst.get(i)%2==0)
lst.remove(i);
else
i++;
}
}
更好的方法是避免拷貝表蜂筹，在遇到那些偶數(shù)值將其刪除需纳。迭代器可以實(shí)現(xiàn)邊遍歷邊刪除，以O(shè)(N)實(shí)現(xiàn)效率很高艺挪。至此驗(yàn)證了LinkedList的迭代器刪除是最高效的方法不翩。
public static void removeEvensVer2(List<Integer> lst){
Iterator<Integer> iter=lst.iterator();
while(iter.hasNext()){
if(iter.next()%2==0)
iter.remove();
}
}
ListIterator接口
ListIterator擴(kuò)展了Iterator的功能，增加了向前遍歷和迭代器增改闺属。
public interface <AnyType> ListIterator extends Iterator<AnyType>{
boolean hasPrevious();
AnyType previous();
void add(AnyType x);
void set(AnyType x);
}
補(bǔ)充：ArrayList和LinkedList的API
3.4 ArrayList類的實(shí)現(xiàn)
泛型數(shù)組的創(chuàng)建是非法的慌盯。我們的做法是創(chuàng)建泛型類型限界的數(shù)組，然后用一個(gè)數(shù)組進(jìn)行類型轉(zhuǎn)換掂器。這將產(chǎn)生一個(gè)編譯警告亚皂，然而這在泛型集合的實(shí)現(xiàn)中是不可避免的。
擴(kuò)容函數(shù)也用于置空和初始化国瓮。
由于一般不在鏈表中保存位置指針且不適合于多次遍歷灭必，因而將寫成鏈表的內(nèi)部類狞谱，位置指針保存在迭代器中。
內(nèi)部類形成了迭代器與鏈表之間的隱式信息交流禁漓。避免了在迭代器中創(chuàng)建鏈表對(duì)象跟衅。
迭代器中名為current，實(shí)現(xiàn)指向next()的元素播歼。
（原書中比較的迭代器的3種實(shí)現(xiàn)方法：2個(gè)類引用對(duì)象伶跷、嵌套類、內(nèi)部類秘狞“饶考查對(duì)象間通信）
訪問(wèn)域名：類內(nèi)this.data，外部類內(nèi)Outer.this.data烁试。
訪問(wèn)權(quán)限：public公共雇初、protected同包子訪問(wèn)、private類內(nèi)訪問(wèn)减响。
static嵌套類會(huì)開(kāi)放一層靖诗，嵌套類被認(rèn)為是外部類的一部分。private static意味著僅作用在外部類范圍之內(nèi)支示。
pulic class MyArrayList<AnyType> implements Iterable<AnyType>{
private static final int DEFAULT_CAPACITY=10;
private int theSize;
private AnyType[] theItems;
public int size(){
return theSize;
}
public boolean isEmpty(){
return size()==0;
}
public void trimToSize(){
ensureCapacity(size());
}
public void ensureCapacity(int newCapacity){
if(newCapacity<size())
return;
AnyType[] newItems=(AnyType[])new Object[newCapacity];
for(int i=0;i<size();i++){
newItems[i]=theItems[i];
}
theItems=newItems;
}
public void clear(){
theSize=0;
ensureCapacity(DEFAULT_CAPACITY);
}
public MyArrayList(){
clear();
}
public void add(int idx,AnyType x){
if(theItems.length==size())
ensureCapacity(size()*2+1);
for(int i=size();i>idx;i--)
theItems[i]=theItems[i--];
theItems[idx]=x;
theSize++;
}
public boolean add(AnyType x){//注意到元素式添加是有返回值的
add(size(),x);
}
public AnyType delete(int idx){
AnyType removedItem=theItems[idx];
for(int i=idx+1;i<size();i++)
theItems[i-1]=theItems[i];
theSize--;
return removedItem;
}
public AnyType set(int idx,AnyType x){
if(idx<0||idx>=size())
throw new ArrayIndexOutOfBoundsException();
AnyType oldItem=theItems[idx];
theItems[idx]=x;
return oldItem;
}
public AnyType get(int idx){
if(idx<0||idx>=size())
throw new ArrayIndexOutOfBoundsException();
return theItems[idx];
}
}
3.5 LinkedList類的實(shí)現(xiàn)
性能：LinkedList中的除了"尾插"以外的增刪改查都使用getNode()方法的都是O(N)時(shí)間刊橘，不推薦使用。LinkedList只擅長(zhǎng)迭代器add/remove悼院。
LinkedList用嵌套類實(shí)現(xiàn)節(jié)點(diǎn)伤为，用索引換鏈/鏈前添加/鏈刪除來(lái)實(shí)現(xiàn)索引式增刪改查，迭代器具有被迭代表不修改錯(cuò)誤檢測(cè)据途、可跳針（next）錯(cuò)誤檢測(cè)绞愚、1跳針1刪除錯(cuò)誤檢測(cè)。
LinkedList類實(shí)現(xiàn)：
public class MyLinkedList<AnyType> implements Iterable<AnyType>{
private Node<AnyType> beginMarker;
private Node<AnyType> EndMarker;
private int theSize;
private int modCount=0;
private static Node<AnyType>{//節(jié)點(diǎn)聲明為嵌套類
private AnyType data;
private Node<AnyType> prev;
private Node<AnyType> next;
public Node(AnyType d,Node<AnyType> p,Node<AnyType> n){
data=d;prev=p;next=n;
}
}
private Node<AnyType> getNode(int idx){}
private void addBefore(Node<AnyType> p,AnyType x){}
private AnyType remove(Node<AnyType> p){}
public int size(){return theSize;}
public boolean isEmpty(){return theSize==0;}
public void clear(){}
public void add(int idx,AnyType x){addBefore(getNode(idx),x);}
public boolean add(AnyType x);
public AnyType remove(int idx){return remove(getNode idx);}
public AnyType set(int idx,AnyType newVal){
Node<AnyType> p=getNode(idx);
AnyType oldVal=p.data;
p.data=newVal;
return oldVal;
}
public AnyType get(int idx){return getNode(idx).data;}
}
LinkedList的"置空"方法：
public void clear(){
beginMarker=Node<AnyType>(null,null,null);
endMarker=Node<AnyType>(null,beginMarker,null);
beginMarker.next=endMarker;
theSize=0;
modCount++;
}
LinkedList的索引換鏈颖医、鏈前添加位衩、鏈刪除：
取索引方法（雙向取索引都遵循對(duì)位開(kāi)號(hào)的原則）：
l 正向取索引p=array[0],int i=0;i<idx。
l 反向取索引p=array[size-1],int j=size-1;i>idx熔萧。
鏈添改4個(gè)指針糖驴，鏈刪改2個(gè)指針。
public Node<AnyType> getNode(int idx){
if(idx<0||idx>=size())
throw new IndexOutOfBoundsException();
Node<AnyType> p=null;
if(idx<size()/2){
p=beginMarker.next;
for(int i=0;i<idx;i++)
p=p.next;
}else{
p=endMarker.prev;
for(int i=size()-1;i>idx;i--)
p=p.prev;
}
return p;
}
public void addBefore(int idx,AnyType x){
Node<AnyType> p=getNode(idx);
Node<AnyType> newNode=new Node<AnyType>(x,p.prev,p);
p.prev.next=newNode;
p.prev=newNode;
theSize++;
modCount++;
}
public AnyType remove(int idx){
Node<Anytype> p=getNode(idx);
p.prev.next=p.next;
p.next.prev=p.prev;
theSize--;
modCount++;
return p.data;
}
LinkedList的迭代器：
迭代器的current指針指到next()的返回元素佛致。
public java.util.Iterator<AnyType> iterator(){
return new LinkedListIterator<AnyType>();
}
private class LinkedListIterator<AnyType> implements java.util.Iterator<AnyType>{
Node<AnyType> current=beginMarker.next;
private int exceptedModCount=modCount;
private boolean okToRemove=false;
public boolean hasNext(){
return current!=endMarker;
}
public AnyType next(){
if(modCount!=exceptedModCount)
throw new java.util.ConcurrentModificationException();
if(!hasNext())
throw new java.util.NoSuchElementException();
okToRemove=true;
AnyType nextData=current.data;
current=current.next;
return nextData;
}
public void remove(){
if(modCount!=exceptedModCount)
throw new java.util.ConcurrentModificationException();
if(!okToRemove)
throw new IllegalStateException();
MyLinkedList.this.remove(current.prev);
okToRemove=false;
expectModCount++;
}
}
3.6 棧ADT
棧沒(méi)有表中低效的查找和遍歷贮缕，只有壓棧push/彈棧pop/檢棧空top俺榆，均花費(fèi)常數(shù)時(shí)間感昼。棧又叫LIFO后進(jìn)先出表。
棧的鏈表實(shí)現(xiàn)：使用單鏈表罐脊，表頂插入實(shí)現(xiàn)push定嗓，表頂刪除實(shí)現(xiàn)pop蜕琴。
棧的數(shù)組實(shí)現(xiàn)更優(yōu)：數(shù)組theArray，棧幀topOfStack（空棧topOfStack==-1）宵溅。進(jìn)棧先跳幀后賦值theArray[++topOfStack]=x;出棧退針return theArray[topOfStack--];
棧實(shí)現(xiàn)不需要theSize
棧以非沉杓颍快的常數(shù)時(shí)間運(yùn)行，在帶有自增和自減尋址功能的寄存器上恃逻，push和pop可以寫成一條機(jī)器指令雏搂，因而棧成為數(shù)組之后最基本的數(shù)據(jù)結(jié)構(gòu)。
棧意味著掛起辛块。
棧應(yīng)用1：平衡符號(hào)
平衡符號(hào)方法：
做空棧畔派，讀字符開(kāi)放符號(hào)入棧讀到封閉符號(hào)铅碍，椚竺啵空?qǐng)?bào)錯(cuò)；棧非空而彈出符號(hào)不對(duì)應(yīng)報(bào)錯(cuò)胞谈；正常情況彈棧（成對(duì)尘盼、對(duì)應(yīng)）。讀完字符棧非空?qǐng)?bào)錯(cuò)（成對(duì)）烦绳。
算法復(fù)雜度O(N)卿捎。
棧應(yīng)用2：中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式（科學(xué)計(jì)算）
中綴轉(zhuǎn)后綴方法：運(yùn)算符進(jìn)棧、字母全輸出径密；遇高則壓棧午阵、低同彈至低（并輸出）；開(kāi)括號(hào)壓棧享扔，閉括彈至開(kāi)底桂。復(fù)雜度O(N)。
處理同級(jí)運(yùn)算符惧眠，”低同彈至低”保證了表達(dá)式從左往右進(jìn)行籽懦。注意冪運(yùn)算符（如223=256）”從右往左結(jié)合”，應(yīng)遵循”遇低彈至同”的原則氛魁。
注意到逆波蘭表達(dá)式是從右往左算的暮顺。
棧應(yīng)用3：后綴表達(dá)式計(jì)算（科學(xué)計(jì)算）
后綴表達(dá)式（postfix）又稱逆波蘭表達(dá)式（reverse Polish）。
逆波蘭表達(dá)式計(jì)算方法：讀逆波蘭表達(dá)式秀存。遇到數(shù)字則壓棧捶码。遇到運(yùn)算符彈出兩個(gè)數(shù)運(yùn)算，運(yùn)算結(jié)果再壓棧或链。復(fù)雜度O(N)惫恼。
棧應(yīng)用4：方法調(diào)用
方法調(diào)用和方法返回類似于開(kāi)閉括號(hào)，平衡符號(hào)的檢測(cè)算法也可用于方法調(diào)用株扛。
主方法調(diào)用新方法時(shí)尤筐，將主方法的局部變量以及主方法的當(dāng)前位置保存起來(lái)（掛起）汇荐，即寄存器值和返回地址，以免被新方法重寫盆繁。
新方法結(jié)束時(shí)恢復(fù)寄存器并返回轉(zhuǎn)移掀淘。
實(shí)現(xiàn)遞歸的掛起方法的棧又稱為”活動(dòng)記錄”或”棧幀”。太多的方法可能導(dǎo)致棧溢出油昂，Java會(huì)拋出一個(gè)異常革娄。
尾遞歸（最后一行調(diào)用遞歸）會(huì)消耗大量的棧空間冕碟，是典型的遞歸使用不當(dāng)?shù)睦印?/p>
尾遞歸的修復(fù)方法為：將代碼放到while循還并用方法參數(shù)的賦值代替拦惋。
非遞歸程序要快于等價(jià)的遞歸程序，而速度優(yōu)勢(shì)的代價(jià)是程序的清晰性安寺。
3.7 隊(duì)列ADT
隊(duì)列都是表頭出隊(duì)厕妖，表尾入隊(duì)。
隊(duì)列的單鏈表實(shí)現(xiàn)較簡(jiǎn)單：頭針front（單鏈表單標(biāo)記beginMarker）挑庶，尾針back言秸，數(shù)量theSize。表尾入隊(duì)enqueue迎捺、表頭出隊(duì)dequeue举畸。
隊(duì)列的數(shù)組實(shí)現(xiàn)使用循還數(shù)組：循還數(shù)組使用theSize判斷隊(duì)大小、隊(duì)空更方便凳枝。非循還數(shù)組使用：隊(duì)為空back-front=-1抄沮，隊(duì)大小back-front+1（循還數(shù)組為theArray.length +back -front+1）%theArray.length）。入隊(duì)前先容量檢查岖瑰，隊(duì)列占滿要擴(kuò)容叛买。
有限的資源就需要用到隊(duì)列。
