数据结构与算法简述（上）

目录：

• 线性表、栈和队列
• HashMap和LinkedHashMap
• 树、二叉树
• 图
  图的遍历与最小生成树
  图的最短路径与拓扑排序

线性表

ArrayList

ArrayList类提供了List ADT的一种可增长数组的实现

注意
删除 ArrayList 中的元素会产生两个问题：
(1).删除元素后 List 的元素数量会发生变化；
(2).对 List 进行删除操作可能会产生并发问题；

删除 ArrayList 元素的三种正确方法

    /**
     * <p>remove11</p>
     * @param list
     * @param target
     * @Description 倒序比对,长度变化不会影响list前面数据
     */
    public static void remove11(List<String> list, String target) {
         for(int i = list.size() - 1; i >= 0; i--){
                String item = list.get(i);
                if(target.equals(item)){
                    list.remove(item);
                }
            }
    }
    

    /**
     * <p>remove22</p>
     * @param list
     * @param target
     * @Description 使用CopyOnWriteArrayList线程安全类
     */
    public static void remove22(ArrayList<String> list, String target) {
        final CopyOnWriteArrayList<String> cowList = new CopyOnWriteArrayList<String>(list);
        for (String item : cowList) {
            if (item.equals(target)) {
                cowList.remove(item);
            }
        }
    }
    
    /**
     * <p>remove33</p>
     * @param list
     * @param target
     * @Description  list转Iterator
     */
    public static void remove33(List<String> list, String target){
        Iterator<String> iter = list.iterator();
        while (iter.hasNext()) {
            String item = iter.next();
            if (item.equals(target)) {
                iter.remove();
            }
        }
    }

LinkedList

LinkedList类提供了List ADT的双链表实现。

参考文献
Java编程：删除 List 元素的三种正确方法

栈（Stack）

标准四则运算--中缀表达式
9+(3-1)3+10/2=20
计算机采用方式--后缀表达式
931-3+10 2/+

队列（Queue）

BlockingQueue方法的总结

operation	Throws exception	Special value	Blocks	Times out
Insert	add(e)	offer(e)	put(e)	offer(e, time, unit)
Remove	remove()	poll()	take()	poll(time, unit)
Examine	element()	peek()	not applicable	not applicable

BlockingQueue阻塞队列

1. ArrayBlockingQueue
       基于数组的阻塞队列实现，在ArrayBlockingQueue内部，维护了一个定长数组，以便缓存队列中的数据对象，这是一个常用的阻塞队列，除了一个定长数组外，ArrayBlockingQueue内部还保存着两个整形变量，分别标识着队列的头部和尾部在数组中的位置。
       ArrayBlockingQueue在生产者放入数据和消费者获取数据，都是共用同一个锁对象，由此也意味着两者无法真正并行运行，这点尤其不同于LinkedBlockingQueue。ArrayBlockingQueue和LinkedBlockingQueue间还有一个明显的不同之处在于，前者在插入或删除元素时不会产生或销毁任何额外的对象实例，而后者则会生成一个额外的Node对象。
2. LinkedBlockingQueue
       基于链表的阻塞队列，同ArrayListBlockingQueue类似，其内部也维持着一个数据缓冲队列（该队列由一个链表构成），当生产者往队列中放入一个数据时，队列会从生产者手中获取数据，并缓存在队列内部，而生产者立即返回；只有当队列缓冲区达到最大值缓存容量时（LinkedBlockingQueue可以通过构造函数指定该值），才会阻塞生产者队列，直到消费者从队列中消费掉一份数据，生产者线程会被唤醒，反之对于消费者这端的处理也基于同样的原理。而LinkedBlockingQueue之所以能够高效的处理并发数据，还因为其对于生产者端和消费者端分别采用了独立的锁来控制数据同步，这也意味着在高并发的情况下生产者和消费者可以并行地操作队列中的数据，以此来提高整个队列的并发性能。
       作为开发者，我们需要注意的是，如果构造一个LinkedBlockingQueue对象，而没有指定其容量大小，LinkedBlockingQueue会默认一个类似无限大小的容量（Integer.MAX_VALUE），这样的话，如果生产者的速度一旦大于消费者的速度，也许还没有等到队列满阻塞产生，系统内存就有可能已被消耗殆尽了

//阻塞队列FIFO
private static LinkedBlockingQueue<Integer> linkedBlockingQueue = new 
            LinkedBlockingQueue<>();
...
//队列添加数据
try {
     //put(anObject):把anObject加到BlockingQueue里，如果BlockQueue没有空间，则调用此方法的线程被阻断直到BlockingQueue里面有空间再继续。
    linkedBlockingQueue.put(i);
} catch (InterruptedException e) {
    e.printStackTrace();
}

...
//队列中删除数据
try {
    //必须要使用take()方法在获取的时候阻塞
    System.out.println(name + "消费:" + linkedBlockingQueue.take());
    //使用poll()方法 将产生非阻塞效果
    //System.out.println(name+"消费： " +  linkedBlockingQueue.poll()); 
} catch (InterruptedException e) {
    e.printStackTrace();
}
...

ConcurrentLinkedQueue非阻塞队列
    基于链接节点的、无界的、线程安全。此队列按照 FIFO（先进先出）原则对元素进行排序。队列的头部 是队列中时间最长的元素。队列的尾部 是队列中时间最短的元素。新的元素插入到队列的尾部，队列检索操作从队列头部获得元素。当许多线程共享访问一个公共 collection 时，ConcurrentLinkedQueue 是一个恰当的选择。此队列不允许 null 元素。

private static ConcurrentLinkedQueue<Integer> concurrentLinkedQueue = new 
            ConcurrentLinkedQueue<>();
...

//队列添加数据
concurrentLinkedQueue.add(i);  

//队列中删除数据
try {
    System.out.println(name + " Consumer" + concurrentLinkedQueue.poll());
} catch (Exception e) {
    e.printStackTrace();
}

循环队列实现