数组
数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
线性表（Linear List）：顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。
非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。
数组具有随机访问特性，并且可以借助 cpu 缓存策略提高效率。数组必须存储在连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。
数组插入和删除的时间复杂度为O(n)，如果不考虑数据连续性，在插入数据的时候可以先将要插入位置的数据移到最后，然后再将数据插入，时间复杂度可降为 O(1)，删除操作亦然。数组随机访问的时间复杂度为 O(1)。
使用数组需要警惕数组的访问越界，C语言中更甚。Java 中的 ArrayList 容器，支持动态扩容，但扩容操会产生数据搬移，时间复杂度也是上升到 O(n)，使用时最好事先指定数据大小。
这里补充一个知识点，为什么数组要从 0 开始编号，而不是从 1 开始？
- 从偏移角度理解a[0] 0为偏移量，如果从1计数，会多出K-1。增加cpu负担。为什么循环要写成for(int i = 0;i<3;i++) 而不是for(int i = 0 ;i<=2;i++)。第一个直接就可以算出3-0 = 3 有三个数据，而后者 2-0+1个数据；
- 也有一定的历史原因。
链表
- 和数组一样，链表也是一种线性表。
- 从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。
- 链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。
链表分为单向链表、双向链表、循环链表、双向循环链表。链表的删除和插入操作时间复杂度为O(1)，只需改变指针的值，查找的时间复杂度为O(n)。
选择数组还是链表？
插入、删除和随机访问的时间复杂度
数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。
链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。数组缺点
若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。
大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。链表缺点
内存空间消耗更大，因为需要额外的空间存储指针信息。
对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。如何选择？
数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。如果代码对内存的使用非常苛刻，那数组就更适合。
栈
后进者先出，先进者后出，这就是典型的“栈”结构。有一个非常贴切的例子，就是一摞叠在一起的盘子。我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。
从栈的操作特性上来看，其实，栈是一种“操作受限”的线性表，只允许在端插入和删除数据，只支持两个基本操作：入栈 push()和出栈 pop()。栈根据实现方法不同可以分为顺序栈和链式栈。
栈的应用：
- 函数调用中的应用，操作系统给每个线程分配了一块独立的内存空间；
- 栈在表达式求值中的应用（比如：34+13*9+44-12/3）；
- 栈在括号匹配中的应用（比如：{}{()}），可用于代码编译；
- 实现浏览器的前进后退功能
JVM 内存管理中有个“堆栈”的概念和内存中的栈有何区别？
内存中的堆栈和数据结构堆栈不是一个概念，可以说内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。
内存空间在逻辑上分为三部分：代码区、静态数据区和动态数据区，动态数据区又分为栈区和堆区。
代码区：存储方法体的二进制代码。高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）控制代码区执行代码的切换。静态数据区：存储全局变量、静态变量、常量，常量包括final修饰的常量和String常量。系统自动分配和回收。
栈区：存储运行方法的形参、局部变量、返回值。由系统自动分配和回收。
堆区：new一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。真实的堆栈应该和计算机架构有关，cpu有栈顶指针寄存器，然后指令有push和pop的指令，这个是数字电路作死的，函数之间的跳变，编译器把要跳的地址赋值给栈顶指针寄存器，然后根据你写的代码编译成push和pop，这部分代码对写高级语言的程序员是透明的，如果写汇编，这些都得自己写
队列
先进者先出，这就是典型的“队列”，最基本的操作也是两个：入队 enqueue()，放一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。和栈一样，队列也是一种操作受限的线性表。
常用的队列
阻塞队列
- 在队列的基础上增加阻塞操作，就成了阻塞队列；
- 阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回；
- 从上面的定义可以看出这就是一个“生产者-消费者模型”。这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了，这时生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据处理效率，比如配置几个消费者，来应对一个生产者。
并发队列
- 在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列；
- 并发队列简单的实现就是在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作；
- 实际上，基于数组的循环队列利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
线程池资源枯竭的处理
在资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
