线性数据结构1 .阵列(Array )是一般的数据结构。 由相同类型的元素(element )组成，使用连续内存进行存储。
可以直接利用元素的索引(index )来计算与该元素对应的存储地址。
数组的特点是可以随机访问，容量有限。
假设数组的长度为n。 访问： o(1)//在特定位置插入元素： o ) n )//在最坏情况下，如果插入发生在数组的开头，并且需要移动所有元素，则将其删除。 o ) n )//最坏的情况发生在数组的开头，需要移动第一个元素之后的所有元素时发生
2 .链表2.1 .链表简介链表(LinkedList )是一个线性表，但并不是按线性顺序存储数据，而是使用连续的内存空间存储数据。
链表的插入和删除操作的复杂度为o(1)，只要知道目标位置元素前面的元素即可。 然而，在寻找某个节点或接入特定位置的节点的情况下，复杂度是o(n )。
链表结构可以克服数组需要提前知道数据大小的缺点，链表结构可以充分利用计算机的内存空间，实现灵活的内存动态管理。 但是，链表中的每个节点都包含指向其他节点的指针，因此链表比数组更节省空间。 此外，链表没有随机读取数组的优点。
2.2 .链表分类常见链表分类：
假设单链表双向链表循环链表双向循环链表中有n个元素。 访问： o(n )//插入删除访问特定位置的元素： o )1) )//需要知道插入元素的位置2.2.1。 单链表的单向链表只有一个方向，节点后面只有一个指针next指向后面的节点。 因此，像链表这样的数据结构通常在物理内存中是不连续的。 我们习惯上把第一个节点称为头节点。 链表通常具有不保存值的头节点(头节点)，可以通过头节点遍历整个链表。 尾节点通常指向空值。
2.2.2 .循环链表的循环链表实际上是一种特殊的单链表，与单链表不同，循环链表的末尾节点指向链表的第一个节点，而不是空值。
2.2.3 .双向链表中的双向链表包含两个指针，一个prev指向上一个节点，一个next指向下一个节点。
2.2.4 .双向循环链表双向循环链表最后一个节点的next指向head，head的prev指向最后一个节点构成环路。
2.3 .如果需要支持应用场景随机访问，则不能使用链表。 如果不确定需要保存的数据元素的数量，并且需要经常添加和删除数据，则最好使用链表。 如果已确定要存储的数据元素的数量，并且不需要经常添加或删除数据，则最好使用数组。 2.4 .数组vs链表数据支持随机访问，但不支持链表。 数组使用对CPU缓存机制友好的连续内存空间，而链表则相反。 数据大小是固定的，但链表支持动态扩展。 如果声明的数组太小，则需要另一个大内存空间来存储数组元素，然后复制原始数组。 这个操作需要时间。 3 .堆栈3.1 .堆栈摘要堆栈(堆栈)仅在规则线性数据集合的一端(堆栈顶部)允许数据添加(推送)和数据删除(pop )。 因此，按照后退先进先出(LIFO，Last In First Out )的原理动作。 在堆栈中，推式和pop操作发生在堆栈的顶部。
堆栈通常在一维数组或链表中实现，数组中实现的堆栈称为顺序堆栈，链表中实现的堆栈称为链堆栈。
假设堆栈中有n个元素。 访问： o(n )//最差情况下，插入删除： o )1) )//在顶部插入和删除元素
3.2 .堆栈的一般应用如果我们处理的数据只涉及在一侧插入和删除数据，并且满足LIFO，Last In First Out (第一个最后一个输出)的特性，则可以使用场景堆栈这一数据结构。
3.2.1 .要实现浏览器的回滚和前向功能，只需使用两个堆栈(堆栈1和堆栈2 )即可实现此功能。 例如，假设您依次看到了4个页面： 1、2、3和4。 依次将1、2、3和4四个页面推入堆栈1。 的滑板喝醉了想回顾2这一页时，请点击后退按钮。 将4、3两个页面依次从堆栈1中弹出，然后推入堆栈2。 如果还想返回第3页，请单击“前进”按钮，将第3页从堆栈2中弹出，然后按到堆栈1中。 示例在以下：中示出
3.2.2 .检查符号是否与只包含“”、“”、“{”、“}”、“[”、“]”的字符串成对出现，判断该字符串是否有效。
有效字符串如下：
左括号必须用同一类型的右括号封闭。 左括号必须按正确的顺序关闭。 例如" () "、" ) " ) " ) " "、" () " "是有效字符串
“()”、「(()”不同。
这个问题实际上是Leetcode的主题，可以利用堆栈来解决这个问题。
首先，将括号间的对应规则存储在Map中应该是毋庸置疑的； 创建堆栈。 遍历字符串，如果字符是左括号，则直接添加到堆栈中。 否则，将堆栈的堆栈顶部元素与此括号进行比较，如果不相等，则返回false。 解开结
束，如果stack为空，返回 true。 public boolean isValid(String s){ // 括号之间的对应规则 HashMap<Character, Character> mappings = new HashMap<Character, Character>(); mappings.put(')', '('); mappings.put('}', '{'); mappings.put(']', '['); Stack<Character> stack = new Stack<Character>(); char[] chars = s.toCharArray(); for (int i = 0; i < chars.length; i++) { if (mappings.containsKey(chars[i])) { char topElement = stack.empty() ? '#' : stack.pop(); if (topElement != mappings.get(chars[i])) { return false; } } else { stack.push(chars[i]); } } return stack.isEmpty();} 3.2.3. 反转字符串将字符串中的每个字符先入栈再出栈就可以了。
3.2.4. 维护函数调用最后一个被调用的函数必须先完成执行，符合栈的 后进先出（LIFO, Last In First Out） 特性。
3.3. 栈的实现栈既可以通过数组实现，也可以通过链表来实现。不管基于数组还是链表，入栈、出栈的时间复杂度都为 O(1)。
下面我们使用数组来实现一个栈，并且这个栈具有push()、pop()（返回栈顶元素并出栈）、peek() （返回栈顶元素不出栈）、isEmpty()、size()这些基本的方法。
提示：每次入栈之前先判断栈的容量是否够用，如果不够用就用Arrays.copyOf()进行扩容；
public class MyStack { private int[] storage;//存放栈中元素的数组 private int capacity;//栈的容量 private int count;//栈中元素数量 private static final int GROW_FACTOR = 2; //不带初始容量的构造方法。默认容量为8 public MyStack() { this.capacity = 8; this.storage=new int[8]; this.count = 0; } //带初始容量的构造方法 public MyStack(int initialCapacity) { if (initialCapacity < 1) throw new IllegalArgumentException("Capacity too small."); this.capacity = initialCapacity; this.storage = new int[initialCapacity]; this.count = 0; } //入栈 public void push(int value) { if (count == capacity) { ensureCapacity(); } storage[count++] = value; } //确保容量大小 private void ensureCapacity() { int newCapacity = capacity * GROW_FACTOR; storage = Arrays.copyOf(storage, newCapacity); capacity = newCapacity; } //返回栈顶元素并出栈 private int pop() { if (count == 0) throw new IllegalArgumentException("Stack is empty."); count--; return storage[count]; } //返回栈顶元素不出栈 private int peek() { if (count == 0){ throw new IllegalArgumentException("Stack is empty."); }else { return storage[count-1]; } } //判断栈是否为空 private boolean isEmpty() { return count == 0; } //返回栈中元素的个数 private int size() { return count; }}验证
MyStack myStack = new MyStack(3);myStack.push(1);myStack.push(2);myStack.push(3);myStack.push(4);myStack.push(5);myStack.push(6);myStack.push(7);myStack.push(8);System.out.println(myStack.peek());//8System.out.println(myStack.size());//8for (int i = 0; i < 8; i++) { System.out.println(myStack.pop());}System.out.println(myStack.isEmpty());//truemyStack.pop();//报错：java.lang.IllegalArgumentException: Stack is empty. 4. 队列 4.1. 队列简介队列 是 先进先出( FIFO，First In, First Out) 的线性表。在具体应用中通常用链表或者数组来实现，用数组实现的队列叫作 顺序队列 ，用链表实现的队列叫作 链式队列 。队列只允许在后端（rear）进行插入操作也就是 入队 enqueue，在前端（front）进行删除操作也就是出队 dequeue
队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。
假设队列中有n个元素。
访问：O（n）//最坏情况
插入删除：O（1）//后端插入前端删除元素
单队列就是常见的队列, 每次添加元素时，都是添加到队尾。单队列又分为 顺序队列（数组实现） 和 链式队列（链表实现）。
顺序队列存在“假溢出”的问题也就是lgdqc有位置却不能添加的情况。
假设下图是一个顺序队列，我们将前两个元素 1,2 出队，并入队两个元素 7,8。当进行入队、出队操作的时候，front 和 rear 都会持续往后移动，当 rear 移动到最后的时候,我们无法再往队列中添加数据，即使数组中还有空余空间，这种现象就是 ”假溢出“ 。除了假溢出问题之外，如下图所示，当添加元素 8 的时候，rear 指针移动到数组之外（越界）。
为了避免当只有一个元素的时候，队头和队尾重合使处理变得麻烦，所以引入两个指针，front 指针指向对头元素，rear
指针指向队列最后一个元素的下一个位置，这样当 front 等于 rear 时，此队列不是还剩一个元素，而是空队列。——From
《大话数据结构》
循环队列可以解决顺序队列的假溢出和越界问题。解决办法就是：从头开始，这样也就会形成头尾相接的循环，这也就是循环队列名字的由来。
还是用上面的图，我们将 rear 指针指向数组下标为 0 的位置就不会有越界问题了。当我们再向队列中添加元素的时候， rear 向后移动。
顺序队列中，我们说 front==rear 的时候队列为空，循环队列中则不一样，也可能为满，如上图所示。解决办法有两种：
4.3. 常见应用场景
当我们需要按照一定顺序来处理数据的时候可以考虑使用队列这个数据结构。
阻塞队列： 阻塞队列可以看成在队列基础上加了阻塞操作的队列。当队列为空的时候，出队操作阻塞，当队列满的时候，入队操作阻塞。使用阻塞队列我们可以很容易实现“生产者 - 消费者“模型。线程池中的请求/任务队列： 线程池中没有空闲线程时，新的任务请求线程资源时，线程池该如何处理呢？答案是将这些请求放在队列中，当有空闲线程的时候，会循环中反复从队列中获取任务来执行。队列分为无界队列(基于链表)和有界队列(基于数组)。无界队列的特点就是可以一直入列，除非系统资源耗尽，比如 ：FixedThreadPool 使用无界队列 LinkedBlockingQueue。但是有界队列就不一样了，当队列满的话后面再有任务/请求就会拒绝，在 Java 中的体现就是会抛出java.util.concurrent.RejectedExecutionException 异常。Linux 内核进程队列（按优先级排队）现实生活中的派对，播放器上的播放列表;消息队列等等…