1. 栈与递归刷题顺序

2. 栈与队列知识总结

2.1. 栈的基本概念

关于“栈”，有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。后进者先出，先进者后出，这就是典型的“栈”结构。

从栈的操作特性上来看，栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。

栈在函数中的应用：栈在函数中的应用、栈在表达式中应用(括号匹配)、栈实现浏览器的前进与后退功能等

2.2. 栈的实现

栈的实现主要有两种，一种是数组的实现，叫做顺序栈，另外一种是链表的实现，叫做链式栈

2.2.1. 顺序栈

使用数组实现栈

// 功能:基于数组的顺序栈
public class ArrayStack {
    private String[] items;  // 数组
    private int count;       // 栈中元素个数
    private int n;           // 栈的大小

    // 初始化数组，申请一个大小为 n 的数组空间
    public ArrayStack(int n) {
        this.items = new String[n];
        this.n = n;
        this.count = 0;
    }

    //功能:入栈
    public boolean push(String item) {
        // 数组空间不够了，直接返回 false，入栈失败。
        if (count == n) return false;
        // 将 item 放到下标为 count 的位置
        items[count] = item;
        //数组长度+1
        ++count;
        //入栈成功
        return true;
    }

    // 功能:出栈
    public String pop() {
        // 栈为空，则直接返回 null
        if (count == 0) return null;
        // 返回下标为 count-1 的数组元素
        String tmp = items[count - 1];
        //数组长度-1
        --count;
        //返回出栈数据元素
        return tmp;
    }
}

2.2.2. 链式栈

//功能:基本链表实现栈，入栈、出栈、输出栈
public class StackBasedLinkedList {
    //定义栈顶指针
    private Node top = null;

    //定义栈结点
    private static class Node {
        //栈结点数据域
        private int data;
        //栈结点指针域
        private Node next;

        //构造函数
        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        //get 获取数据域方法
        public int getData() {
            return data;
        }
    }

    public void push(int value) {
        //创建一个栈结点
        Node newNode = new Node(value, null);
        // 判断栈是否为空
        if (top == null) {
            //如果栈为空，就将入栈的值作为栈的第一个元素
            top = newNode;
        } else {
            //否则插入到top栈结点前（所谓的就是单链表的头插法）
            newNode.next = top;
            top = newNode;
        }
    }

    //功能 : 出栈
    public int pop() {
        // 如果栈的最顶层栈结点为null,栈为空
        if (top == null) return -1;

        //否则执行出栈操作，现将栈顶结点的数据元素赋值给 Value
        int value = top.data;
        //将 top 指针向下移动
        top = top.next;
        //返回出栈的值
        return value;
    }

    //功能:输出栈中所有元素
    public void printAll() {
        //将栈顶指针赋值给p
        Node p = top;
        //循环遍历栈(遍历单链表)
        while (p != null) {
            System.out.print(p.data + " ");
            //指向下一个结点
            p = p.next;
        }

    }
}

3. 队列(Queue)

队列(Queue)是一种先进先出(FIFO)的数据结构，Java中定义了java.util.Queue接口用来表示队列。Java中的Queue与List、Set属于同一个级别接口，它们都是继承于Collection接口。 Java中还定义了一种双端队列java.util.Deque，我们常用的LinkedList就是实现了Deque接口。

3.1. 队列的实现

Java中对于队列的实现分为非阻塞队列与阻塞队列两种

阻塞队列与普通(非阻塞)队列的区别在于，当队列是空的时，从队列中获取元素的操作将会被阻塞，或者当队列是满时，往队列里添加元素的操作会被阻塞。试图从空的阻塞队列中获取元素的线程将会被阻塞，直到其他的线程往空的队列插入新的元素。同样，试图往已满的阻塞队列中添加新元素的线程同样也会被阻塞，直到其他的线程使队列重新变得空闲起来，如从队列中移除一个或者多个元素，或者完全清空队列.

3.2. 非阻塞队列

1、LinkedList

LinkedList是双相链表结构，在添加和删除元素的时具有比ArrayList更好的性能。但在Get和Set方面弱于ArrayList.当然，这些对比都是指数据量很大或者操作很频繁的情况下的对比。

当LinkedList作为队列使用时，尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。

2、PriorityQueue

PriorityQueue维护一个有序列表，存储到队列中的元素会按照自然顺序排列。当然，我们也可以给它指定一个实现了 java.util.Comparator 接口的排序类来指定元素排列的顺序。

3、ConcurrentLinkedQueue

ConcurrentLinkedQueue看名思义，ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列，它采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部，当我们获取一个元素时，它会返回队列头部的元素并删除。

注:PriorityQueue 和 ConcurrentLinkedQueue 类在 Collection Framework中加入两个具体集合实现。

3.3. 阻塞队列

阻塞队列定义在了java.util.concurrent包中，java.util.concurrent.BlockingQueue 继承了Queue接口，它有 5 个实现类，分别是

1、ArrayBlockingQueue

ArrayBlockingQueue一个内部由数组支持的有界队列。初始化时必须指定队列的容量，还可以设置内部的ReentrantLock是否使用公平锁。但是公平性会使你在性能上付出代价，只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队列，此队列按FIFO（先进先出）原则对元素进行排序。

它的思想就是如果BlockingQueue是空的，那么从BlockingQueue取东西的操作将会被阻断进入等待状态，直到BlockingQueue进了东西才会被唤醒。同样,如果BlockingQueue是满的，任何试图往里存东西的操作也会被阻断进入等待状态，直到BlockingQueue里有空间才会被唤醒继续操作。

2、LinkedBlockingQueue

LinkedBlockingQueue一个内部由链接节点支持的可选有界队列。初始化时不需要指定队列的容量，默认是Integer.MAX_VALUE，也可以看成容量无限大。此队列按 FIFO（先进先出）排序元素 。

3、PriorityBlockingQueue

PriorityBlockingQueue一个内部由优先级堆支持的无界优先级队列。队列中的元素按优先级顺序被移除。PriorityBlockingQueue就是PriorityQueue的加锁线程安全版。

4、DelayQueue

DelayQueue一个内部由优先级堆支持的、基于时间的调度队列。队列中存放Delayed元素，只有在延迟期满后才能从队列中提取元素。当一个元素的getDelay()方法返回值小于等于0时才能从队列中poll出元素，否则poll()方法会返回null。

DelayQueue是一个无界阻塞队列，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的Delayed 元素。

缓存系统的设计，缓存中的对象，超过了空闲时间，需要从缓存中移出；任务调度系统，能够准确的把握任务的执行时间。我们可能需要通过线程处理很多时间上要求很严格的数据。可以考虑DelayQueue。

5、SynchronousQueue

SynchronousQueue它模拟的功能类似于生活中一手交钱一手交货这种情形，像那种货到付款或者先付款后发货模型不适合使用SynchronousQueue。

SynchronousQueue 也是一个队列来的，但它的特别之处在于它内部没有容器，一个生产线程，当它生产产品（即put的时候），如果当前没有人想要消费产品(即当前没有线程执行take)，此生产线程必须阻塞，等待一个消费线程调用take操作，take操作将会唤醒该生产线程，同时消费线程会获取生产线程的产品（即数据传递），这样的一个过程称为一次配对过程(当然也可以先take后put,原理是一样的)。