List

list(表)继承Collection(集合)接口,主要有Arraylist,LinkedList和Vector;

• ArrayList

ArrayList相当于是动态数组,对get和set的调用花费常熟时间,遍历时候一般随记访问即可,缺点是新项的插入和现有项的删除代价昂贵.

 package com.fredal.structure;
public class MyArrayList<T> {
   private static final int DEFAULT_CAPACITY=5;
   private int size;
   private T[] items;
   
   public MyArrayList(){
       size=0;
       ensureCapacity(DEFAULT_CAPACITY);
   }
   
   //扩容
   private void ensureCapacity(int newCapacity){
       if(newCapacity<size) return;
       T[] old=items;//搬运到新数组去
       items=(T[])new Object[newCapacity];
       for(int i=0;i<size;i++){
           items[i]=old[i];
       }
   }
   //增加
   public void add(int idx,T x){
       if(items.length==size) ensureCapacity(size*2+1);
       for(int i=size;i>idx;i--) items[i]=items[i-1];
       items[idx]=x;
       size++;
   }
   
   public void add(T x){
       add(size, x);
   }
   
   //移除
   public T remove(int idx){
       T item=items[idx];
       for(int i=idx;i<size-1;i++) items[i]=items[i+1];
       size--;
       return item;
   }
   //查找
   public T get(int idx){
       if(idx<0||idx>=size) throw new ArrayIndexOutOfBoundsException();
       return items[idx];
   }
   //设置
   public T set(int idx,T newVal){
       if(idx<0||idx>=size) throw new ArrayIndexOutOfBoundsException();
       T old=items[idx];
       items[idx]=newVal;
       return old;
   }
}

• LinkedList

LinkedList采用双链表实现,LinkedList同时实现了Deque接口,具有队列的特点.随记访问慢,插入删除快,遍历时候一般采用迭代器吧.这个类我们在之前实现过,接不实现了,参考数据结构学习笔记_2中双向链表代码.
值得一提的例子:
如果我们要删除表中的所有偶数,对于ArrayList来说,remove的效率不高.对于linkedList来说,对get调用的效率不高,其次对remove的调用同样低效,因为要达到位置i的代价是昂贵的.

 public static void remove(List<Integer> list){
 int i=0;
 while(i<list.size()){
  if(list.get(i)%2==0){
    list.remove();
  }else
    i++;
 }
 }

这样的算法对两者显然都是二次的.换一种思路

 public static void remove(List<Integer> list){
  for(Integer x:list){
   if(x%2==0){
    list.remove();
   }
  }
 }

这样是采用迭代器一步步遍历,显然是高效的,但是当用Collection的remove的时候,对于Linkedlist来说,它仍然需要搜索该项(可以看看前面的代码).当然最糟糕的是,仔细观察一下,这个程序会报异常.恩就是传说中的fail-fast,在多线程时考虑较多,这儿不谈.

  public static void remove(List<Integer> list){
  Iterator<Integer> itr=list.iterator();
  while(itr.hasNext()){
    if(itr.next()%2==0){
      itr.remove();
    }
  }
 }

这个程序就是比较成功的,先迭代器迭代过去,对于LinkedList来说,remove也非常容易,不用重新再调用getNode()方法了,因为迭代器就在删除节点的附近,所以对于LinkedList来说是线性的.当然对于ArrayList仍然是二次的.

• Vector&Stack

Vector基本上是个线程安全的ArrayList,方法也差不多,本质上还是数组.
而Stack是个栈,特点是先进后出,主要方法有push和pop,之前用链表模拟过栈,代码也不贴了,参考数据结构学习笔记_2 .
问题是呢,Stack是继承Vector的,也就是说java中的Stack本质上是一个动态数组,我真是不理解这个!
不过呢Api里说了,想要用Stack的时候就去用Deque吧!Deque<Integer> stack = new ArrayDeque<Integer>();.

• List总结

先看一下整个框架

1

ArrayList, LinkedList, Vector, Stack是List的4个实现类。
ArrayList 是一个数组队列，相当于动态数组。它由数组实现，随机访问效率高，随机插入、随机删除效率低。
LinkedList 是一个双向链表。它也可以被当作堆栈、队列或双端队列进行操作。LinkedList随机访问效率低，但随机插入、随机删除效率高。
Vector 是矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现。但是ArrayList是非线程安全的，而Vector是线程安全的。
Stack 是栈，它继承于Vector。它的特性是：先进后出(FILO, First In Last Out)。

分析一下使用场景:
如果涉及到“栈”、“队列”、“链表”等操作，应该考虑用List，具体的选择哪个List，根据下面的标准来取舍。

1. 对于需要快速插入，删除元素，应该使用LinkedList。
2. 对于需要快速随机访问元素，应该使用ArrayList。
3. 对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。
4. 对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。

Set&Map

Set接口代表不允许重复的Collection,主要有HashSet和TreeSet.
Map接口是由关键字以及它们的值组成的一些项的集合,值不一定是唯一的,而键必须是唯一的.对于map进行遍历相对复杂,因为没有提供迭代器,而提供三种方法得到对应的set.keySet,values,entrySet.
看一看map类的图先:

2

还有set的图:

3

• HashMap

HashSet和hashmap中的项必须提供equals方法和hashCode方法,HashSet和HashMap都主要是通过之前写过的分离链散列的代码实现的,而HashSet又是在HashMap的基础上实现的.
首先看看HashMap的源码

 public HashMap(int initialCapacity, float loadFactor) {
       //初始容量不能<0
       if (initialCapacity < 0)
           throw new IllegalArgumentException("Illegal initial capacity: "
                   + initialCapacity);
       //初始容量不能 > 最大容量值，HashMap的最大容量值为2^30
       if (initialCapacity > MAXIMUM_CAPACITY)
           initialCapacity = MAXIMUM_CAPACITY;
       //负载因子不能 < 0
       if (loadFactor <= 0 || Float.isNaN(loadFactor))
           throw new IllegalArgumentException("Illegal load factor: "
                   + loadFactor);

       // 计算出大于 initialCapacity 的最小的 2 的 n 次方值。
       int capacity = 1;
       while (capacity < initialCapacity)
           capacity <<= 1;
       
       this.loadFactor = loadFactor;
       //设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行扩容操作
       threshold = (int) (capacity * loadFactor);
       //初始化table数组
       table = new Entry[capacity];
       init();
   }

从源码中可以看出，每次新建一个HashMap时，都会初始化一个table数组。table数组的元素为Entry节点。

 static class Entry<K,V> implements Map.Entry<K,V> {
       final K key;
       V value;
       Entry<K,V> next;
       final int hash;

       /**
        * Creates new entry.
        */
       Entry(int h, K k, V v, Entry<K,V> n) {
           value = v;
           next = n;
           key = k;
           hash = h;
       }
       .......
   }

来看存储实现：put(key,vlaue)

 public V put(K key, V value) {
      //当key为null，调用putForNullKey方法，保存null与table第一个位置中，这是HashMap允许为null的原因
      if (key == null)
          return putForNullKey(value);
      //计算key的hash值
      int hash = hash(key.hashCode());                  ------(1)
      //计算key hash 值在 table 数组中的位置
      int i = indexFor(hash, table.length);             ------(2)
      //从i出开始迭代 e,找到 key 保存的位置
      for (Entry<K, V> e = table[i]; e != null; e = e.next) {
          Object k;
          //判断该条链上是否有hash值相同的(key相同)
          //若存在相同，则直接覆盖value，返回旧value
          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
              V oldValue = e.value;    //旧值 = 新值
              e.value = value;
              e.recordAccess(this);
              return oldValue;     //返回旧值
          }
      }
      //修改次数增加1
      modCount++;
      //将key、value添加至i位置处
      addEntry(hash, key, value, i);
      return null;
  }

读取实现：get(key)

 public V get(Object key) {
      // 若为null，调用getForNullKey方法返回相对应的value
      if (key == null)
          return getForNullKey();
      // 根据该 key 的 hashCode 值计算它的 hash 码  
      int hash = hash(key.hashCode());
      // 取出 table 数组中指定索引处的值
      for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
          Object k;
          //若搜索的key与查找的key相同，则返回相对应的value
          if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
              return e.value;
      }
      return null;
  }

其余的不贴了,底层就是分离链散列嘛...

• HashSet

看看HashSet吧,底层就是HashMap...

  /**
       * 默认构造函数
       * 初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。
       */
      public HashSet() {
          map = new HashMap<>();
      }
      
      /**
       * 构造一个包含指定 collection 中的元素的新 set。
       */
      public HashSet(Collection<? extends E> c) {
          map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
          addAll(c);
      }
      
      /**
       * 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和指定的加载因子
       */
      public HashSet(int initialCapacity, float loadFactor) {
          map = new HashMap<>(initialCapacity, loadFactor);
      }
         
      /**
       * 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和默认的加载因子（0.75）。
       */
      public HashSet(int initialCapacity) {
         map = new HashMap<>(initialCapacity);
      }
         
      /**
       * 在API中我没有看到这个构造函数，今天看源码才发现（原来访问权限为包权限，不对外公开的）
       * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
       * dummy 为标识 该构造函数主要作用是对LinkedHashSet起到一个支持作用
       */
      HashSet(int initialCapacity, float loadFactor, boolean dummy) {
         map = new LinkedHashMap<>(initialCapacity, loadFactor);
      }

HashSet的方法一般都去调用HashMap的方法,没啥好帖的.

• HashTable

来说说HashTable
HashTable继承Dictionary类,实现Map接口.主要特点是它是线程安全的!方法基本用synchronized锁住了,其他构造模式和HashMap基本一样.
总结一下区别吧:

1. HashMap是非线程安全的，HashTable是线程安全的。
2. HashMap的键和值都允许有null值存在，而HashTable则不行。
3. 因为线程安全的问题，HashMap效率比HashTable的要高。
4. 另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException

问题来了,HashTable效率低下,而HashMap其实提供了访问其同步map的静态方法:synchronizedMap().但是这个同步map仍然有这样那样的问题.于是ConcurrentHashMap出现了,这是更好的选择.(由于本文是根据数据结构视频写的学习笔记,细的暂时不在这儿说了).

• equals和hashcode

值得一提的自然是它们的equals()和hashcode().
在往HashSet或者HashMap中插入数据的时候是不能重复的,那么程序如何判断是否重复呢?自然是先调用hashcode方法,如果重复了接着调用equals方法看看是否真的重复了.
如果你需要笔记自定义的类的话就需要自己去实现equals()和hashcode().
这里特别讲一个闪存散列,由于hashcode方法往往是费时最多的,在String类中的hashcode方法包含了一个非常重要的优化:

  public final class String{
    public int hashcode(){
      if(hash!=0)
       return hash;
      for(int i=0;i<length();i++)
       hash=hash*31+(int) charAt(i);
      return hash;
    }
    private int hash=0;
  }

每个String对象内部都存储它的hashCode,该值初始值为0,但若hashCode被调用,那么这个值就会被记住.因此,如果hashcode对同一个String对象两次计算,我们可以避免昂贵的重新计算.
至于怎么重写hashcode其实是可以深究,上面的代码根据Horner法则计算一个多项式函数,这样比较均匀...不细说...
这里想说两个好用的,apache Commons和Google Guava的equals和hashcode
Equals:
Apache Commons

  public boolean equals(Object obj) {
    if (obj == null) { return false; }
    if (obj == this) { return true; }
    if (obj.getClass() != getClass()) {
       return false;
    }
  MyClass rhs = (MyClass) obj;
  return new EqualsBuilder()
               .appendSuper(super.equals(obj))
               .append(field1, rhs.field1)
               .append(field2, rhs.field2)
               .isEquals();
}

Google Guava

  public boolean equals(final Object obj) {
  if (obj == null) {
      return false;
  }
  if (obj == this) {
      return true;
  }
  if (this.getClass() != obj.getClass()) {
      return false;
  }
  final ThisObject other = (ThisObject) obj;
  return Objects.equal(this.field1, other.field1)
          && Objects.equal(this.field2, other.field2);
}

HashCode:
Apache Commons

  public int hashCode() {
   return new HashCodeBuilder(17, 37).
     append(field1).
     append(field2).
     toHashCode();
 }

Google Guava

  public int hashCode() {
   return Objects.hashCode(this.field1, this.field2);
}

• TreeSet&TreeMap

TreeSet同样是TreeMap的一个马甲,先来看部分代码

 TreeSet(NavigableMap<E,Object> m) {  
   this.m = m;  
}    
public TreeSet() {   // 无参数构造函数  
   this(new TreeMap<E,Object>());  
}    
public TreeSet(Comparator<? super E> comparator) { // 包含比较器的构造函数  
   this(new TreeMap<>(comparator));  
}    
public TreeSet(Collection<? extends E> c) {  
   this();  
   addAll(c);  
}    
public TreeSet(SortedSet<E> s) {  
   this(s.comparator());  
   addAll(s);  
}   
public  boolean addAll(Collection<? extends E> c) {  
   // Use linear-time version if applicable  
   if (m.size()==0 && c.size() > 0 &&  
       c instanceof SortedSet &&  
       m instanceof TreeMap) {  
       SortedSet<? extends E> set = (SortedSet<? extends E>) c;  
       TreeMap<E,Object> map = (TreeMap<E, Object>) m;  
       Comparator<? super E> cc = (Comparator<? super E>) set.comparator();  
       Comparator<? super E> mc = map.comparator();  
       if (cc==mc || (cc != null && cc.equals(mc))) {  
           map.addAllForTreeSet(set, PRESENT);  
           return true;  
       }  
   }  
   return super.addAll(c);  
} 

这里构造函数相关部分的代码看起来比较多，实际上主要的构造函数就两个，一个是默认的无参数构造函数和一个比较器构造函数，他们内部的实现都是使用的TreeMap，而其他相关的构造函数都是通过调用这两个来实现的，故其底层使用的就是TreeMap。
TreeMap的底层则是由红黑树实现的,红黑树本质上是一棵一定程度上相对平衡的二叉搜索树,算是比较高级的数据结构,留空以后再讲.

• Comparable&Comparator

都知道TreeSet和TreeMap是会排序的,那排序的时候自然要比较大小,如果是自定义的类,需要实现排序功能,一般可以继承Comparable并重写compareTo()方法,或者外部写一个比较器继承Comparator并重写compare方法.
还是举几个例子吧:

  import java.util.HashSet;  
import java.util.Set;   
public class Customer implements Comparable {  
   private String name;  
 
   private int age;  
 
   public Customer(String name, int age) {  
       this.age = age;  
       this.name = name;  
   }  
 
   public int getAge() {  
       return age;  
   }  
 
   public void setAge(int age) {  
       this.age = age;  
   }  
 
   public String getName() {  
       return name;  
   }  
 
   public void setName(String name) {  
       this.name = name;  
   }  
 
   @Override  
   public boolean equals(Object obj) {  
       if (this == obj)  
           return true;  
       if (!(obj instanceof Customer))  
           return false;  
       final Customer other = (Customer) obj;  
 
       if (this.name.equals(other.getName()) && this.age == other.getAge())  
           return true;  
       else  
           return false;  
   }  
 
   public static void main(String[] args) {  
       Set<Customer> set = new HashSet<Customer>();  
       Customer customer1 = new Customer("Tom", 15);  
       Customer customer2 = new Customer("Tom", 15);  
       set.add(customer1);  
       set.add(customer2);  
       System.out.println(set.size());  
   }  
 
   public int compareTo(Object o) {  
       Customer other = (Customer) o;  
 
       // 先按照name属性排序  
       if (this.name.compareTo(other.getName()) > 0)  
           return 1;  
       if (this.name.compareTo(other.getName()) < 0)  
           return -1;  
 
       // 在按照age属性排序  
       if (this.age > other.getAge())  
           return 1;  
       if (this.age < other.getAge())  
           return -1;  
       return 0;  
   }  
 
   @Override  
   public int hashCode() {  
       int result;  
       result = (name == null ? 0 : name.hashCode());  
       result = 29 * result + age;  
       return result;  
   }  
}  

main方法类

public class CustomerTester {
   public static void main(String[] args) {
       Set<Customer> set = new TreeSet<Customer>();
       set.add(new Customer("Tom",15));
       set.add(new Customer("Tom",20));
       set.add(new Customer("Tom",15));
       set.add(new Customer("Mike",15));
       Iterator<Customer> it = set.iterator();
       while(it.hasNext()){
           Customer customer = it.next();
           System.out.println(customer.getName()+" "+customer.getAge());
       }
   }
}

需要注意的是,已经存在的对象如果修改了后,TreeSet不会对其进行重新排序.所有TreeSet还是更适合存Integer,Double,String等所谓不可变类.

  public class CustomerComparator implements Comparator<Customer>{   
   public int compare(Customer c1, Customer c2) {         if(c1.getName().compareTo(c2.getName())>0)return -1;   if(c1.getName().compareTo(c2.getName())<0)return 1;           
       return 0;  
   }       
   public static void main(String args[]){  
       Set<Customer> set = new TreeSet<Customer>(new CustomerComparator());           
       Customer customer1= new Customer("Tom",15);  
       Customer customer3= new Customer("Jack",16);  
       Customer customer2= new Customer("Mike",26);  
       set.add(customer1);  
       set.add(customer2);  
       set.add(customer3);  
         
       Iterator<Customer> it = set.iterator();  
       while(it.hasNext()){  
           Customer customer = it.next();    System.out.println(customer.getName()+" "+customer.getAge());  
       }  
   }    
}  

这是用外部比较器进行比较的,属于策略模式.值得注意的是,Comparator是有equals()和compare()两个方法,但是没有写equals()方法是因为比较的Object类本身实现了equals().

• 关于拼音排序

想想还是写一下关于汉字根据拼音排序的例子,拼音排序是关于Comparable,Comparator的经典应用.
首先排序有宽松和严格之分,关于宽松排序,java提供了标准方法,由于汉字最早是GB2312编码，收录了六千多个汉字，是按拼音排序的，编码是连续的,所以直接使用Collator类就可以实现.

class K1 implements Comparator<String>{
 //GB2312的编码顺序 是宽松的排序
 public int compare(String o1, String o2) {
   Collator col=Collator.getInstance(java.util.Locale.CHINA);
   return col.compare(o1, o2);
 }
}
public class PinYinSort {
  public static void main(String[] args) {   
   List<String> lst=new ArrayList<String>();
   lst.add("张三");
   lst.add("李四");
   lst.add("王五");
   lst.add("赵六");
   lst.add("齐大傻");
   List<String> list = PinYinSort.ComparePY(lst);
   for(String str:list){
     System.out.println(str);
   }
  }    
  public static List<String> ComparePY(List<String> lst){
   Set<String> t=new TreeSet<String>(new K1());
   while(lst.size()>0){
     t.add(lst.remove(0));
   }   
   Iterator<String> iterator = t.iterator();
   while(iterator.hasNext()){
     lst.add(iterator.next());
   }   
   return lst;
  }
}

接下来,如果有多个关键字比较,例如地名和人名,先比较地名再比较人名的话,需要使用map来排序.

class K2 implements Comparator<Entry<String, String>>{
 public int compare(Entry<String, String> o1, Entry<String, String> o2) {
   Collator col=Collator.getInstance(java.util.Locale.CHINA);
   //第一关键字
   int p1=col.compare(o1.getValue(), o2.getValue());
   if(p1!=0){
     return p1;
   }   
   //第二关键字
   int p2=col.compare(o1.getKey(), o2.getKey());
   if(p2!=0){
     return p2;
   }   
   return 0;
 } 
}
public class PinYinSort {
 public static void main(String[] args) {
   
   Map<String,String> map=new HashMap<String, String>();
   map.put("张三", "北京");
   map.put("李四", "北京");
   map.put("王五", "河北");
   map.put("赵六", "河北");
   map.put("高小三", "上海");
   map.put("齐大傻", "四川");
   
   Map<String, String> nmap = PinYinSort.ComparePYM(map);
   Set<String> keys = nmap.keySet();
   Iterator<String> it = keys.iterator();
   while(it.hasNext()){
     String key=it.next();
     System.out.println(nmap.get(key)+" "+key);
   }
 }
 public static Map<String, String> ComparePYM(Map<String, String> map){
   Set<Entry<String, String>> t=new TreeSet<Entry<String,String>>(new K2());
   Map<String,String> m=new TreeMap<String, String>();
   Iterator<Entry<String, String>> ite = map.entrySet().iterator();
   while(ite.hasNext()){
     Entry<String, String> item = ite.next();
     m.put(item.getKey(), item.getValue());
   }
   
   return m;
 }
}

这种宽松排序对于某些汉字是会出现问题的,比如说"怡",因为后来出现了GBK编码，对GB2312进行了扩展，到了两万多汉字,新增加的汉字不可能再按照拼音顺序插入到已有的gb2312编码中，所以新增加的汉字不是按拼音顺序排的.
这时候采取另外的方法,使用pinyin4j 开源项目 具体可以查看 (http://pinyin4j.sourceforge.net)
我们导入jar包后再进行比较封装成比较器的代码如下:

class K3 implements Comparator<String>{
  int index=0;  
  public int compare(String o1, String o2) {    
    char c1=o1.charAt(index);
    char c2=o2.charAt(index);
    return concatPYArray(PinyinHelper.toHanyuPinyinStringArray(c1))   .compareTo(concatPYArray(PinyinHelper.toHanyuPinyinStringArray(c2))); 
  } 
  private String concatPYArray(String[] array){
    StringBuffer sbf=new StringBuffer();
    if((array!=null)&&(array.length>0)){
      for(int i=0;i<array.length;i++){
        sbf.append(array[i]);
      }
    }
    return sbf.toString();
  } 
}
public class PinYinSort{
  public static void main(String[] args) {
    List<String> lst=new ArrayList<String>();
    lst.add("张三");
    lst.add("李四");
    lst.add("王五");
    lst.add("赵六");
    lst.add("怡情");
    lst.add("齐大傻");
    List<String> list = PinYinSort.ComparePY(lst);
    for(String str:list){
      System.out.println(str);
    }
  }   
  public static List<String> ComparePY(List<String> lst){
    Set<String> t=new TreeSet<String>(new K3());
    while(lst.size()>0){
      t.add(lst.remove(0));
    }    
    Iterator<String> iterator = t.iterator();
    while(iterator.hasNext()){
      lst.add(iterator.next());
    }    
    return lst;
  }
}

Queue

Queue是一种很常见的数据结构类型,特点是先入先出，在java里面Queue是一个接口,与List和Set一样是继承自Collection接口的.
Deque是一个双向队列,继承自Queue,不仅具有FIFO的Queue实现，也有FILO的实现，也就是不仅可以实现队列，也可以实现一个堆栈.而LinkedList呢也实现了Deque.这些之前队列的实现代码都写过,类似.
写几个例子来丰富一下好了:
Queue队列:

  import java.util.LinkedList;  
import java.util.Queue;  
  
/** 
 * Queue队列接口 是常用数据结构 
 * Queue遵循先进先出 进入offer 出去poll 两个方法 
 * 先添加先删除 
 * LinkedList实现了List和Queue两个接口 
 */  
public class TestQueue {  
  
    public static void main(String[] args) {  
        //用Queue引用 只能是两个方法 注意与List引用的区别  
        Queue<String> q = new LinkedList<String>();  
        q.offer("one");//添加  
        q.offer("two");  
        q.offer("three");  
          
        System.out.println("peek :"+q.peek());//查看使用poll方法会取出的对象  
        System.out.println(q.poll());//取出后就没有了  
        System.out.println(q);  
        System.out.println(q.poll());//删除  
        System.out.println(q);  
    }  
}  

Deque:

 import java.util.Deque;  
import java.util.LinkedList;  
  
/** 
 * 两头队列 
 * 可以作为队列用，也可以作为栈用 
 * 栈后进先出 
 */  
public class TestDeque {  
  
    public static void main(String[] args) {  
        Deque<String> stack = new LinkedList<String>();  
        //单队列  
//      stack.offer(str);  
//      String stack.poll();  
          
        //两头队列  
//      stack.offerFirst(str);  
//      stack.offerLast(str);  
//      stack.pollFirst();  
//      stack.pollLast()；  
          
        //栈  
        stack.push("one");  
        stack.push("two");  
        stack.push("three");  
        System.out.println(stack.pop());  
    }  
}  

看一下各种类接口的联系:

4

fail-fast,iterator,enumeration

之前提到了fail-fast,简单的来说, 当多个线程对同一个集合进行操作的时候，某线程访问集合的过程中，该集合的内容被其他线程所改变(即其它线程通过add、remove、clear等方法，改变了modCount的值)；这时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。
关于如何解决fail-fast,以ArrayList为例,我们可以采用 CopyOnWriterArrayList来代替.它解决问题的核心在于:

  Object[] arrayOfObject2 = Arrays.copyOf(arrayOfObject1, i + 1); 
  arrayOfObject2[i] = paramE; 
  setArray(arrayOfObject2);  

任何对array在结构上有所改变的操作（add、remove、clear等），CopyOnWriterArrayList都会copy现有的数据，再在copy的数据上修改，这样就不会影响COWIterator中的数据了，修改完成之后改变原有数据的引用即可。同时这样造成的代价就是产生大量的对象，同时数组的copy也是相当有损耗的。
说说另一个话题, 在Java集合中，我们通常都通过 “Iterator(迭代器)” 或 “Enumeration(枚举类)” 去遍历集合。
Enumeration是一个接口，它的源码如下：

  package java.util;


public interface Enumeration<E> {


    boolean hasMoreElements();


    E nextElement();
}

Iterato也是一个接口,源码如下:

  package java.util;


public interface Iterator<E> {
    boolean hasNext();


    E next();


    void remove();
}

可以看到Iterator更多地提供了remove().
其次最重要的不同是,Iterator支持fail-fast机制，而Enumeration不支持。
Enumeration 是JDK 1.0添加的接口。使用到它的函数包括Vector、Hashtable等类，这些类都是JDK 1.0中加入的，Enumeration存在的目的就是为它们提供遍历接口。Enumeration本身并没有支持同步，而在Vector、Hashtable实现Enumeration时，添加了同步。
而Iterator 是JDK 1.2才添加的接口，它也是为了HashMap、ArrayList等集合提供遍历接口。Iterator是支持fail-fast机制的：当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。
更多文章与相关下载请看扩展阅读