一文搞懂数组、堆栈与链表、队列的区别

线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。而与它相对立的概念是非线性表，比如二叉树、堆、图等。

所谓的数据结构就是表示数据之间的关系。这些数据结构中的每一个元素都是紧密相连的，不能有空隙。

数据结构是抽象的概念，没有语言之别，就像是设计模式一样，是一种抽象的思想，用任何语言的代码都能构建出来。而我们的python中的字符串，列表，字典，元祖，集合都是基本数据类型，他们是依附于语言存在的，不同的语言有不同的基本数据类型。

在二进制下的数据类型所占的位数：

int8位

longint16位

shortint4位

char---assic8位;gbk16位;utf-8，24位;unicode32位;

float--占4个字节，即32位，具体分布如下：1bit(符号位，即正负号)，8bit(指数位)，23bit(尾数位)。

数组

数组是一维图形。

数组是定长，所谓的定长就是在创建之初就需要告诉解释器它的长度，而我们的列表是不定长的，所谓的不定长就是我们创建了一个列表，我们肉眼看到的可能这个列表只有3个元素或者我们就干脆创建一个空列表，但是在内部实现的时候解释器给这个列表一个初始长度，假设这个长度是20，然后我们对这个我们所创建了列表进行增删改查的时候，这个列表的长度就会发生变化，然后发生变化的过程中，系统内部就把这个列表一开始的所有数据给拷贝下来，然后根据你增删改查的结果对列表进行扩大或者缩小。

数组中的数据类型必须要保持一致，一个数组中只能存一种数据类型，所谓的数据类型就是：整数int，小数float，字符串char这些类型。列表里面存的数据类型是不一样的，但是在解释器内部，这些个不同的数据类型都是被python实例化出来的一个个对象，然后在列表中存的都是这些对象的一个个的地址指针。

数组可以通过索引取值，时间复杂度是O1.(O1这个时间复杂度跟数组的规模是没有差别的，不论是多长的数组，它的时间复杂度都是O1.而On的话，这个n可以是任何常数，比如可以是20、300、5000等等，都远远没有O1快)它的取值原理是因为数组存的是同一种数据类型，而数据类型都是固定长度的，所以可以通过长度取值。比如这里有一个数组A，它存的都是整数类型，第一个元素的地址假设是0110，那么我们要获取这个A数组中的第4个元素，只需要通过第一个元素的地址加上(4-1)*8=24，即0110+24=0134，就是第4个元素的地址，然后就能直接很快地拿到这个元素，内存地址都是连续的。这就是它取值快的地方。但是它有弊端，我们的数组中每一个元素都是紧挨着的，打一个比方，算盘，它的每一根柱子上都是一串算珠，我们把这个算盘立起来的时候，算珠都会垂直落到底部，我们假设拆掉一个柱子上的一个算珠，那么这个算珠上面的算珠会依次降落到下一个算珠的位置上，然后这个柱子的算珠整体高度就会下降一个算珠的高度，或者我们增加一个算珠，我们所增加的这个算珠上面的所有算珠都会上升到上一个算珠的位置上，因为算珠之间不能有空隙，要一个个紧紧挨着。我们的数组就类似这样的情况，当我们要在数组中插入一个值的时候，我们所插入的这个位置，后面的所有元素都要依次往后挪一个元素的位置，就像我们给算盘增加算珠一样，在增加的位置上的每一上面的算珠都要往上挪一个算珠的位置;同理，如果要删除一个数组中的元素的话，那么这个被删除的元素的位置就空出来了，然后因为我们的数组里面的元素都是紧挨着的，所以这个被删除的元素后面的元素都会依次往前挪一个元素的位置，就像我们的算盘上取掉一个算珠，这个算珠的上面每一个算珠都要往下降一个算珠的位置，就是这个道理。所以如果删除或者是插入一个数组中的中间元素的话，它后面的所有元素都需要挪动位置，这里就没有取值那么便捷了，时间复杂度就会增加，但是，如果是增加或者是删除最后一个元素就不会涉及到其他元素的操作，这里就不存在时间复杂度的增加问题了。

堆栈

堆栈也是一维图形。

我们想象一下一个装羽毛球的球桶，它的直径就是羽毛球的羽毛那一端所围成的圆形的直径，这样一个个羽毛球放进去刚好卡在桶壁内，没有多余空隙，以免晃动中产生摩擦带来不必要的损耗。假设这个球桶只有一个口，另一段是封死的，这个时候假设这个球桶是空的，我们把羽毛球一个个依次放进去的时候，只能从这个口放进去，然后也只能从这个口拿出来，也就是先进后出，后进先出。

在这个堆栈中我们只研究栈顶，这个栈顶的位置就是我们的堆栈整体高度。也就是说在这个羽毛球桶中，最上面的这个羽毛球在刻度4处，这个球桶中就有4个球，此时我们拿出去一个球，这个球桶中最上面的这个球就在3这个刻度上了，此时球桶中就有3个球，这个球桶中最上面的球就被我们标记为栈顶。实现一个堆栈的方式就是一个变量+一个数组。这个变量指向这个数组中的最后一个元素，比如这个数组中有8个元素，这个变量指向8，这个堆栈就有8个元素，栈顶就是8。

堆栈组成可以用列表实现，也可以用数组实现，如果用列表的话就可以存放不同的数据类型。

需要附上堆栈的代码实现，以上仅仅是概念性的原理。代码需要有一个类，类里面有两个方法，入栈和出栈，入栈时需要考虑到栈的大小，栈满时不可入，同时，出栈也要考虑到栈空时不能出。

队列

队列也是一维图形。

队列不同于堆栈有一个口，进出都是它(我们叫做出入耦合)，队列不一样，它有2个口，一个单独的出口，一个单独的入口(我们叫做出入分离)。同向时如果出入口重合，则队列为空，反向时如果出入口重合，则队列为满。我们在队列问题中，仅仅考虑两个点，入口和出口，而且这两个要分开考虑，不能想得过于复杂。所以按照堆栈的实现方式，队列的实现就是两个变量+数组。

队列同上，用数组和列表都能实现。

链表

链表也是一维图形。

链表中的每一个元素都会标记一个尾部指向，这个指向是指向下一个元素，然后每一个元素之间用尾部彼此相连，所谓链表就像铁链一样，彼此之间紧密相扣，形成一条链条。链表是没有大小的，不同于数组，堆栈和队列。

双向链表就是不仅会标记尾部指向，还会有头部指向，一条链表中的任意一个元素拿出来，它有头部指向，指向上一个元素，还有尾部指向，指向下一个元素，这就是双向链表。

链表分单向和双向，两种。彼此之间不能混合，单向和单向组合，双向和双向组合。循环链表，就是尾项指向头项，首位相连形成一个圆，就是循环链表，也就没有头尾之分。

链表的增删改查，跟数组比起来就要快很多了，比如我们要删除一个链表中的元素，就需要把这个元素的上一个元素的尾部指向指向到这个元素的下一个元素的尾部指向即可，就像是把这个链条上的一个链环拿掉就把这个链条分成了两截，然后把这个断开的部分重新链接上即可，比如是abcd的链条，把c拿掉，就让b和d链接上即可，不会涉及到更多元素的操作，比起数组就方便很多。但是有一点弊端，就是数组取值，是通过索引取值，会很快，而链表如果要取值，就需要从链头开始找依次去找到那个值然后返回，这样就会慢很多，如果刚好要找的那个值是链尾，那么就需要遍历整个链表。时间复杂度是O(n)。

一、数组

数组(Array)是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

数组可以根据下标随机访问，计算机根据寻址公式可以快速查找下标为i的元素：

a[i]_address = base_address + i() * data_type_size

即下标为i的元素地址=数组首地址+下标 i 乘以 数据类型大小。例如数组中存储的是 int 类型数据data_type_size 就为 4 个字节。数组要求连续的内存空间，所以想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

小结：数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问O(1)，但插入、删除操作比较低效，平均情况时间复杂度为 O(n)。

二、链表(Linked list)

链表不需要像数组一样需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。

常见的链表结构有：单链表、双向链表和循环链表。通常第一个结点叫作头结点，把最后一个结点叫作尾结点，头结点用来记录链表的基地址。

1、单链表：每个链表的结点除了存储数据之外，还有一个后继指针 next记录下一个结点的地址。尾结点指向一个空地址 NULL。

2、循环链表：循环链表是特殊的单链表。循环链表的尾结点指针是指向链表的头结点。

3、双向链表：每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是 O(1)。因为链表中的数据并非连续存储的，想随机访问第 k 个元素，无法像数组那样通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。

小结：链表是内存不连续的，通过“指针”将零散的内存块串联起来使用的。链表的插入和删除操作比较快都快O(1)，随机访问的性能没有数组好O(n)，编写代码时注意边界条件，对插入第一个结点和删除最后一个结点的情况进行特殊处理。

三、栈

栈的特点：后进先出。栈主要包含两个操作，入栈 push()和出栈 pop()，也就是在栈顶插入一个数据和从栈顶删除一个数据。

数组实现的栈，我们叫作顺序栈，支持动态扩容。用链表实现的栈，我们叫作链式栈。

栈的应用：

1、函数调用栈

操作系统给每个线程分配了一块独立的内存空间，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈

eg:

int main() {

int a = 1;

int ret = 0;

int res = 0;

ret = add(3, 5);

res = a + ret;

printf("%d", res);

reuturn 0;

}

int add(int x, int y) {

int sum = 0;

sum = x + y;

return sum;

}

函数栈里出栈、入栈的操作：

2、表达式求值

eg：3+5*8-6。

实际上，编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈;当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

小结：栈是一种“操作受限”的线性表，只允许在一端插入和删除数据即入栈和出栈，只需要一个栈顶指针。后进者先出，先进者后出。典型应用场景函数调用，表达式求值也需要理解。入栈、出栈的时间复杂度都为 O(1)。

四、队列

队列的特点：先进先出。主要包含两个操作，入队enqueue()，放一个数据到队列尾部;出队 dequeue()，从队列头部取一个元素。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

队空和队满的判定条件：队满的判断条件是 tail == n，队空的判断条件是 head == tail。

在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，我们就需要像环一样的循环队列。循环队列当队满时，(tail+1)%n=head。其中最后tail 指向的位置实际上是没有存储数据的。所以，循环队列会浪费一个数组的存储空间。

小结：队列也是一种“操作受限”的线性表，先进者先出，对应入队和出队，队列需要两个指针：一个是 head 指针，指向队头;一个是 tail 指针，指向队尾。注意队空和队满的判定条件，典型应用场景如循环队列、阻塞队列、并发队列、线程池。

五、递归

1、递归需要满足的三个条件：

一个问题的解可以分解为几个子问题的解

这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样。

存在递归终止条件。

2、如何编写递归代码?

最关键的是写出递推公式，找到终止条件。

3、为什么递归代码容易造成堆栈溢出呢?

函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险。

4、那如何避免出现堆栈溢出呢?

我们可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。

为了避免重复计算，我们可以通过一个数据结构(比如散列表)来保存已经求解过的 f(k)。当递归调用到 f(k)时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算。

小结：递归不算数据结构但是一种应用非常广泛的编程技巧，注意使用递归需满足的条件以及如何找出递归公式和终止条件，避免死循环，编码时注意避免堆栈溢出和重复计算。 典型应用如 DFS 深度优先搜索、前中后序二叉树遍历，斐波那契数列。