。

它由相同类型的元素#xff08;element#xff09;组成#xff0c;并且是使用一块连续的内存来存储。

我们直接可以利用元素的索引#xff08;index#xff09;可以计算出该元素对应的存储地址。

数组…数组

是一种很常见的数据结构。

它由相同类型的元素element组成并且是使用一块连续的内存来存储。

我们直接可以利用元素的索引index可以计算出该元素对应的存储地址。

插入On

删除On//最坏的情况发生在删除数组的开头发生并需要移动第一元素后面所有的元素时

链表简介

链表LinkedList虽然是一种线性表但是并不会按线性的顺序存储数据使用的不是连续的内存空间来存储数据。

O(1)

只需要知道目标位置元素的上一个元素即可。

但是在查找一个节点或者访问特定位置的节点的时候复杂度为

O(n)

使用链表结构可以克服数组需要预先知道数据大小的缺点链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。

但链表不会节省空间相比于数组会占用更多的空间因为链表中每个节点存放的还有指向其他节点的指针。

除此之外链表不具有数组随机读取的优点。

链表分类

指向后面的节点。

因此链表这种数据结构通常在物理内存上是不连续的。

我们习惯性地把第一个结点叫作头结点链表通常有一个不保存任何值的

head

其实是一种特殊的单链表和单链表不同的是循环链表的尾结点不是指向

循环链表

如果需要支持随机访问的话链表没办法做到。

如果需要存储的数据元素的个数不确定并且需要经常添加和删除数据的话使用链表比较合适。

如果需要存储的数据元素的个数确定并且不需要经常添加和删除数据的话使用数组比较合适。

CPU

的缓存机制友好链表则相反。

数组的大小固定而链表则天然支持动态扩容。

如果声明的数组过小需要另外申请一个更大的内存空间存放数组元素然后将原数组拷贝进去这个操作是比较耗时的

栈简介

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

()、()[]{}、{[]}

中这一点应该毋容置疑创建一个栈。

遍历字符串如果字符是左括号就直接加入stack中否则将stack

public

(mappings.containsKey(chars[i]))

{char

例如递归函数调用可以通过栈来实现每次递归调用都会将参数和返回地址压栈。

深度优先遍历DFS

栈既可以通过数组实现也可以通过链表来实现。

不管基于数组还是链表入栈、出栈的时间复杂度都为

下面我们使用数组来实现一个栈并且这个栈具有push()、pop()返回栈顶元素并出栈、peek()

返回栈顶元素不出栈、isEmpty()、size()这些基本的方法。

MyStack

System.out.println(myStack.peek());//8

System.out.println(myStack.size());//8

for

{System.out.println(myStack.pop());

System.out.println(myStack.isEmpty());//true

myStack.pop();//报错java.lang.IllegalArgumentException:

Stack

的线性表。

在具体应用中通常用链表或者数组来实现用数组实现的队列叫作

顺序队列

队列的操作方式和堆栈类似唯一的区别在于队列只允许新数据在后端进行添加。

访问On//最坏情况

顺序队列存在“假溢出”的问题也就是明明有位置却不能添加的情况。

1,2

移动到最后的时候,我们无法再往队列中添加数据即使数组中还有空余空间这种现象就是

”假溢出“

为了避免当只有一个元素的时候队头和队尾重合使处理变得麻烦所以引入两个指针front

指针指向对头元素rear

循环队列可以解决顺序队列的假溢出和越界问题。

解决办法就是从头开始这样也就会形成头尾相接的循环这也就是循环队列名字的由来。

rear

的时候队列为空循环队列中则不一样也可能为满如上图所示。

解决办法有两种

flag,当

就指向这个空闲位置如下图所示那么现在判断队列是否为满的条件就是(rear1)

QueueSizefront

是一种在队列的两端都可以进行插入和删除操作的队列相比单队列来说更加灵活。

removeLast

在每个元素入队时优先队列会将新元素其插入堆中并调整堆。

在队头出队时优先队列会返回堆顶元素并调整堆。

总而言之不论我们进行什么操作优先队列都能按照某种排序方式进行一系列堆的相关操作从而保证整个集合的有序性。

虽然优先队列的底层并非严格的线性结构但是在我们使用的过程中我们是感知不到堆的从使用者的眼中优先队列可以被认为是一种线性的数据结构一种会自动排序的线性队列。

当我们需要按照一定顺序来处理数据的时候可以考虑使用队列这个数据结构。

阻塞队列

阻塞队列可以看成在队列基础上加了阻塞操作的队列。

当队列为空的时候出队操作阻塞当队列满的时候入队操作阻塞。

使用阻塞队列我们可以很容易实现“生产者

线程池中没有空闲线程时新的任务请求线程资源时线程池该如何处理呢答案是将这些请求放在队列中当有空闲线程的时候会循环中反复从队列中获取任务来执行。

队列分为无界队列(基于链表)和有界队列(基于数组)。

无界队列的特点就是可以一直入列除非系统资源耗尽比如FixedThreadPool

使用无界队列

LinkedBlockingQueue。

但是有界队列就不一样了当队列满的话后面再有任务/请求就会拒绝在

Java

中的体现就是会抛出java.util.concurrent.RejectedExecutionException

peek并且在

中普遍使用双端队列Deque来实现栈。

广度优先搜索BFS在图的广度优先搜索过程中队列被用于存储待访问的节点保证按照层次顺序遍历图的节点。

Linux

内核进程队列按优先级排队现实生活中的派对播放器上的播放列表;消息队列等等……