#理由一：
    面试的时候，千万不要被数据结构与算法拖了后腿
#理由二：
    你真的愿意做一辈子CRUD Boy吗
#理由三：
    不想写出开源框架，中间件的工程师，不是好厨子

#学习方法
1.从基础开始，系统化学习
2.多动手，每一种数据结构与算法，都自己用代码实现出来
3.思路更重要：理解实现思想，不要背代码
4.与日常开发结合，对应应用场景

#学习内容：
1.数据结构的定义
2.算法的定义
3.复杂度分析
4.常用数据结构
    数组、链表、栈、队列
    散列表、二叉树、堆
    跳表、图
5.常用算法
    递归、排序、二分查找
    搜索、哈希、贪心、分治
    动态规划、字符串匹配

#考考你：
1.你能用自己的话描述队列吗？
2.你知道常见的队列分类吗？
3.你知道队列代码实现的关键吗？
4.你知道如何实现一个循环队列吗？
5.你知道队列的常见的应用场景吗？

package com.anan.struct.linetable;
/**
 * 顺序队列：基于数组实现
 * @param <E>
 */
public class ArrayQueue<E> {
    private Object[] items;
    private  int n;
    // 队列需要两个下标：对头下标索引、队尾下标索引
    private int head;
    private int tail;
    public ArrayQueue(int capacity){
        this.items = new Object[capacity];
        this.n = capacity;
    }
    /**
     * 入队操作：
     */
    public boolean enqueue(E e){
        // 检查队列是否满
        // 队列满条件 tail==n && head == 0
        if(tail == n){
            // 检查对头是否没有出队
            if(head == 0){
                return false;
            }
            // 如果已经有元素出队，则向对头移动数据
            for (int i = head; i < tail ; i++) {
                items[i - head] = items[i];
            }
            tail = tail - head;
            head = 0;
        }
        // 入队
        items[tail] = e;
        tail ++;
        return true;
    }
    /**
     * 出队操作：
     */
    public E dequeue(){
        // 检查队列是否空
        // 队列空条件：head == tail
        if(head == tail){
            return null;
        }
        // 出队
        E e = (E)items[head];
        head ++;
        return e;
    }
}

package com.anan.struct.linetable;
/**
 * 测试队列
 */
public class ArrayQueueTest {
    public static void main(String[] args) {
        // 1.创建队列
        int capacity = 10;
        ArrayQueue<Integer> queue = new ArrayQueue<Integer>(capacity);
        System.out.println("1.创建队列---------队列容量：" + capacity);
        // 2.入队操作
        System.out.println("2.入队操作---------");
        int count = 5;
        for (int i = 0; i < count; i++) {
            queue.enqueue(i);
            System.out.println("入队元素：" + i);
        }
        // 3.出队操作
        System.out.println("3.出队操作---------");
        for (int i = 0; i < count; i++) {
            System.out.println("出队元素：" + queue.dequeue());
        }
    }
}

D:\02teach\01soft\jdk8\bin\java com.anan.struct.linetable.ArrayQueueTest
1.创建队列---------队列容量：10
2.入队操作---------
入队元素：0
入队元素：1
入队元素：2
入队元素：3
入队元素：4
3.出队操作---------
出队元素：0
出队元素：1
出队元素：2
出队元素：3
出队元素：4
Process finished with exit code 0

package com.anan.struct.linetable;
/**
 * 循环队列
 */
public class CircularQueue<E> {
    private Object[] items;
    private int n;
    // 队头、对尾指针
    private int head;
    private int tail;
    public CircularQueue(int capacity){
        items = new Object[capacity];
        n = capacity;
    }
    /**
     * 入队操作
     */
    public boolean enqueue(E e){
        // 判断队列是否满
        // 队列满条件：(tail + 1) % n == head
        if((tail + 1) % n == head){
            return false;
        }
        items[tail] = e;
        tail = (tail + 1) % n;
        return true;
    }
    /**
     * 出队操作
     */
    public E dequeue(){
        // 判断队列是否空
        // 队列空条件：tail == head
        if(tail == head){
            return null;
        }
        E e = (E)items[head];
        head = (head + 1) % n;
        return e;
    }
}

#考考你答案：
1.你能用自己的话描述队列吗？
  1.1.队列是基于线性表的数据结构
  1.2.队列是一种操作受限的数据结构
  1.3.队列满足先进先出（FIFO）的特点
  1.4.队列在队头出队元素，在队尾入队元素
  
2.你知道常见的队列分类吗？
  2.1.从底层数据结构分类有：顺序队列、链式队列
  2.2.从实现特点分类有：循环队列、阻塞队列、并发队列
  
3.你知道队列代码实现的关键吗？
  3.1.队列满足先进先出（FIFO）特点
  3.2.队列在队头出队元素，在队尾入队元素
  3.3.实现队列的关键：
    a.需要两个指针：head、tail分别指向队头和队尾
    b.入队时，判断队列满条件：tail == n && head == 0
    c.出队时，判断队列空条件：tail == head
    
4.你知道如何实现一个循环队列吗？
  4.1.在案例中，基于数组实现了一个普通的队列
  4.2.入队操作的时候，如果队列满，需要移动数据
  // 如果队列满，且已经有元素出队，则向对头移动数据
   for (int i = head; i < tail ; i++) {
          items[i - head] = items[i];
   }
  4.3.这样会将入队操作，时间复杂度从O(1)，转变成O(n)，执行效率下降
  4.4.有没有更好的方式，保持入队操作的时间复杂度为O(1)不变呢？
  4.5.答案是：通过循环队列来实现
  4.6.关于循环队列的代码，你可以参考【3.3】循环队列实现
  4.7.重点关注队列满的条件：(tail + 1) % n == head
  4.8.看你是否能理解，欢迎留言我们一起讨论
  
5.你知道队列的常见的应用场景吗？
  5.1.队列主要针对有限资源控制的应用场景
  5.2.比如数据库连接池的应用
  5.3.比如线程池的应用
  5.4.如果你有兴趣，可以看一下JUC中线程池的底层实现
  5.5.JUC线程池的底层，应用了：阻塞队列
  5.6.通过队列还能实现：生产者---消费者模型