第3章 表、栈和队列
抽象数据类型（abstract data type,ADT）是带有一组操作的对象的集合。
数组实现表的扩容：
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的添加删除总结：
l 迭代器删除remove删除由next()最新返回的项，此后不能再执行remove()直到对next()的再一次调用。
迭代器删除知道确切的位置，比容器类删除具有更高的效率。
使用迭代器或增强for循还，若正在被迭代的集合进行结构上的改变（add/remove/clear），那么迭代器就不再合法抛出CurrentModificationException异常。
基于以上迭代器的两个优点，迭代器使用原则是：迭代器只有在立即使用时才获取，迭代器调用自己的remove方法是合法的。
遍历有3种方法：迭代器、增强for、索引号。
l 空器接口add/remove具为遍历式删除。当集合不允许重复，要删除的元素不在集合中时返回false。
l List接口具有Collections方法、索引式增删改查、listIterator。
静态函数写法：public、static、泛型、返回值、函数名、形参。
容器类Collections接口：判长空置空，添删容迭。Collections接口是Iterable接口的继承类可以使用增强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实现，get/set花费O(1)。add/remove花费昂贵，除非变动在ArrayList的末端执行。
List的双链表LinkedList实现，在变动项位置已知的情况下add/remove花费很小。表的前端add/remove花费常数时间，因而LinkedList提供了addFirst/removeFirst/addLast/removeLast方法。get/set调用花费O(N)，除非调用接近表的端点。
对于搜索ArrayList和LinkedList实现Collections的contains和remove方法均花费O(N)。
ArrayList有容量的概念，添加需要调用ensureCapacity()，添加完调用trimToSize()节约空间。
插入删除的实现选择：
l 末端add/remove用ArrayList,LinkedList均可。
l 首端add/remove用LinkedList，此时ArrayList表现最差。
l 已知索引处add/remove用LinkedList。
未知索引处添加：要比较ArrayList的移动效率和LinkedList的遍历效率
l 遍历情况：ArrayList用索引号、迭代器均可O(N)，LinkedList只能用迭代器O(N)。LinkedList用索引号遍历将花费O(N^2)。
实际表现ArrayList性能优于LinkedList。
程序计时：
long startTime=System.currentTimeMillis();
long endTime=System.currentTimeMillis();
System.out.println("程序运行时间： "+(endTime-startTime)+"ms");
去除数组偶数值，练习LinkedList的remove方法
一种想法是将奇数拷到新表，清空原表，再将奇数拷回原表。
另一种想法使用增强for循还，过程中删除元素将抛异常。
另一种想法是使用索引号遍历，ArrayList花费O(N)，而LinkedList花费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++;
}
}
更好的方法是避免拷贝表，在遇到那些偶数值将其删除。迭代器可以实现边遍历边删除，以O(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扩展了Iterator的功能，增加了向前遍历和迭代器增改。
public interface <AnyType> ListIterator extends Iterator<AnyType>{
boolean hasPrevious();
AnyType previous();
void add(AnyType x);
void set(AnyType x);
}
补充：ArrayList和LinkedList的API
3.4 ArrayList类的实现
泛型数组的创建是非法的。我们的做法是创建泛型类型限界的数组，然后用一个数组进行类型转换。这将产生一个编译警告，然而这在泛型集合的实现中是不可避免的。
扩容函数也用于置空和初始化。
由于一般不在链表中保存位置指针且不适合于多次遍历，因而将写成链表的内部类，位置指针保存在迭代器中。
内部类形成了迭代器与链表之间的隐式信息交流。避免了在迭代器中创建链表对象。
迭代器中名为current，实现指向next()的元素。
（原书中比较的迭代器的3种实现方法：2个类引用对象、嵌套类、内部类。考查对象间通信）
访问域名：类内this.data，外部类内Outer.this.data。
访问权限：public公共、protected同包子访问、private类内访问。
static嵌套类会开放一层，嵌套类被认为是外部类的一部分。private static意味着仅作用在外部类范围之内。
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类的实现
性能：LinkedList中的除了"尾插"以外的增删改查都使用getNode()方法的都是O(N)时间，不推荐使用。LinkedList只擅长迭代器add/remove。
LinkedList用嵌套类实现节点，用索引换链/链前添加/链删除来实现索引式增删改查，迭代器具有被迭代表不修改错误检测、可跳针（next）错误检测、1跳针1删除错误检测。
LinkedList类实现：
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>{//节点声明为嵌套类
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的索引换链、链前添加、链删除：
取索引方法（双向取索引都遵循对位开号的原则）：
l 正向取索引p=array[0],int i=0;i<idx。
l 反向取索引p=array[size-1],int j=size-1;i>idx。
链添改4个指针，链删改2个指针。
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
栈没有表中低效的查找和遍历，只有压栈push/弹栈pop/检栈空top，均花费常数时间。栈又叫LIFO后进先出表。
栈的链表实现：使用单链表，表顶插入实现push，表顶删除实现pop。
栈的数组实现更优：数组theArray，栈帧topOfStack（空栈topOfStack==-1）。进栈先跳帧后赋值theArray[++topOfStack]=x;出栈退针return theArray[topOfStack--];
栈实现不需要theSize
栈以非常快的常数时间运行，在带有自增和自减寻址功能的寄存器上，push和pop可以写成一条机器指令，因而栈成为数组之后最基本的数据结构。
栈意味着挂起。
栈应用1：平衡符号
平衡符号方法：
做空栈，读字符开放符号入栈读到封闭符号，栈空报错；栈非空而弹出符号不对应报错；正常情况弹栈（成对、对应）。读完字符栈非空报错（成对）。
算法复杂度O(N)。
栈应用2：中缀表达式转为后缀表达式（科学计算）
中缀转后缀方法：运算符进栈、字母全输出；遇高则压栈、低同弹至低（并输出）；开括号压栈，闭括弹至开。复杂度O(N)。
处理同级运算符，”低同弹至低”保证了表达式从左往右进行。注意幂运算符（如223=256）”从右往左结合”，应遵循”遇低弹至同”的原则。
注意到逆波兰表达式是从右往左算的。
栈应用3：后缀表达式计算（科学计算）
后缀表达式（postfix）又称逆波兰表达式（reverse Polish）。
逆波兰表达式计算方法：读逆波兰表达式。遇到数字则压栈。遇到运算符弹出两个数运算，运算结果再压栈。复杂度O(N)。
栈应用4：方法调用
方法调用和方法返回类似于开闭括号，平衡符号的检测算法也可用于方法调用。
主方法调用新方法时，将主方法的局部变量以及主方法的当前位置保存起来（挂起），即寄存器值和返回地址，以免被新方法重写。
新方法结束时恢复寄存器并返回转移。
实现递归的挂起方法的栈又称为”活动记录”或”栈帧”。太多的方法可能导致栈溢出，Java会抛出一个异常。
尾递归（最后一行调用递归）会消耗大量的栈空间，是典型的递归使用不当的例子。
尾递归的修复方法为：将代码放到while循还并用方法参数的赋值代替。
非递归程序要快于等价的递归程序，而速度优势的代价是程序的清晰性。
3.7 队列ADT
队列都是表头出队，表尾入队。
队列的单链表实现较简单：头针front（单链表单标记beginMarker），尾针back，数量theSize。表尾入队enqueue、表头出队dequeue。
队列的数组实现使用循还数组：循还数组使用theSize判断队大小、队空更方便。非循还数组使用：队为空back-front=-1，队大小back-front+1（循还数组为theArray.length +back -front+1）%theArray.length）。入队前先容量检查，队列占满要扩容。
有限的资源就需要用到队列。
