表,栈队列

1.抽象数据类型(ADT)

　　带有一组操作的几何对象,在集合ADT中，可以包含add,remove,contain等操作,也可以只有find和union

2.表ADT

　　在表中,简单分为单链表和双链表,链表有一系列节点组成,不必与内存相连,每一个节点均包含表元素和包含到该元素的链(link),也称为next链,最后一个next链引用null。

3.Java中Collections API

　　我们可以将Collections作为一个数据结构存在,存在于java.util包中,下图是collections的基本结构

在Collection接口中扩展了Iterator接口，Iterator作为增强的for循环,在实现Iterator接口的集合时需要提供iterfator的方法,该方法返回一个Iterator类的对象,存在于java.util

public interface Iterator<AnyType>
{
  boolean hasNext();
  AnyType next();
  void remove();
}

Iterator的实现思路是通过iterator方法，每个集合均可创建并返回给客户一个实现Iterator接口的对象，对next的引用都给出集合下一项,利用hasnext来判断是否存在下一项,但由于Iterator接口中的方法有限,很难使用Iterator做简单遍历Collection以外的工作。

public static <AnyType>void print(Collection<AnyType>coll)
{
 Iterator<AnyType> itr=coil.iterator();
//Compare exist
while(itr.hasnext())
{
//Next
  AnyType item=item.next();
System.out.Println(item);
}
}

5.List接口,ArrayList类和LinkedList

　　表由java.util包中的List接口指定,List接口继承了Collection接口,包含了Collection接口的所有方法

1 public interface List<AnyType> extends Collection<AnyType>
2 {
3    AnyType get(int idx);
4     AnyType set(int idx,AnyTpe newVal);
5    void add(int idx,AnyType x);
6   void remove(int idx);
7 
8   ListIterator<AnyType> listIterator(int pos);  
9 }

get和set使用户可以访问或改变通过由位置索引idx给定的表中指定位置的项,索引0位于表的前端,索引size()-1代表最后一项。

　在ListADT实现方式中,ArrayList提供了List ADT 一种可增长数组的实现

　　再利用ArrayList时,对get和set花费常数时间，但存在新项的插入和删除代价昂贵,除非在尾端之行,运行时间为O(N)

　　而LinkedList作为双链表优势在于插入和删除开销小,LinkedList提供了addFirst(),addLast()等双向操作，但是存在不容易做索引,对get的调用昂贵,除非调用非常接近表的端点,运行时间为O(N*N)

5.1ListIterator接口

　　ListIterator扩展了List的Iterator功能,通过previous和hasPrevious对表向从后向前遍历完成

1 public interface ListIterator<AnyType> extends Iterator<AnyType>{
2     boolean hasPrevious();
3     AnyType previous();
4    
5    void add(AnyType x);
6    void set(AnyType newVal);  
7 }

6.栈ADT

　　栈是限制插入和删除只能在一个位置上的表，位于表的末端,对栈的操作有push和pop,前者相当于插入,后着删除最后插入元素,栈也被称为LIFO表。

　　可以通过链表和数组实现