存储结构的比较

数组、链表、栈、队列与堆

在计算机科学中，存储结构是数据元素及其逻辑关系在计算机存储器里的表示，不同的存储结构有着各自的特点和适用场景，常见的存储结构包括数组、链表、栈、队列和堆等，下面将对它们进行详细的比较。

一、数组

1、存储方式

数组在内存中是连续存储的，在 C 语言中，定义一个整型数组int arr[5] = {1, 2, 3, 4, 5};，这 5 个元素在内存中依次连续存放，其内存地址是连续递增的，假设数组的基地址为 LOCATION，每个整型元素占用 4 个字节（假设），那么数组元素的内存地址分别为 LOCATION、LOCATION + 4、LOCATION + 8、LOCATION + 12、LOCATION + 16。

2、访问方式

可以通过下标随机访问数组中的任意元素，时间复杂度为 O(1)，比如要访问数组中的第 i 个元素，直接通过arr[i] 就可以快速定位并获取其值，无需遍历整个数组。

3、插入和删除操作

插入和删除操作相对复杂，如果要在第 i 个位置插入一个元素，需要将第 i 个元素以及之后的所有元素都向后移动一位，以腾出空间来存放新元素；删除操作同理，需要将待删除元素之后的所有元素向前移动一位来填补空缺，这些操作的平均时间复杂度为 O(n)，n 是数组的长度。

4、应用场景

适用于对数据随机访问频繁，而插入和删除操作相对较少的场景，在图像处理中，像素点数据通常使用数组存储，因为需要快速地根据坐标访问特定的像素值进行图像的显示、修改等操作。

二、链表

1、存储方式

链表的存储单元在物理位置上不一定是连续的，它由一系列节点组成，每个节点包含数据域和指针域（用于指向下一个节点），一个单链表的节点结构可以定义为struct Node { int data; struct Node* next; };，各个节点通过next 指针连接起来，形成一个链式结构。

2、访问方式

不能像数组那样随机访问元素，只能通过指针从表头开始逐个遍历节点来查找特定元素，平均时间复杂度为 O(n)，要查找链表中值为 x 的节点，需要从第一个节点开始，沿着next 指针依次比较每个节点的数据域，直到找到目标节点或遍历完整个链表。

3、插入和删除操作

插入和删除操作相对灵活，若要在第 i 个位置插入一个元素，只需找到第 i 1 个节点，然后修改其next 指针指向新创建的节点，新节点的next 指针指向原来的第 i 个节点即可；删除操作类似，找到待删除节点的前驱节点，将其next 指针指向待删除节点的后继节点，这些操作的平均时间复杂度为 O(1)（不考虑查找前驱节点的时间）。

4、应用场景

适用于数据的插入和删除操作频繁，且对数据的存储顺序没有严格要求的场景，在操作系统中，进程调度队列可以使用链表来实现，方便添加和移除进程。

三、栈

1、存储方式

栈是一种后进先出（LIFO）的线性数据结构，可以使用数组或链表来实现其存储结构，采用数组实现时，栈顶元素存放在数组的末尾；采用链表实现时，栈顶元素为链表的表头节点。

2、访问方式

主要关注栈顶元素的访问，通过栈顶指针可以直接获取栈顶元素，时间复杂度为 O(1)，在一个用数组实现的栈中，若栈顶指针为 top，数组为 stack，则栈顶元素为 stack[top]。

3、插入和删除操作

插入（入栈）和删除（出栈）操作都在栈顶进行，时间复杂度均为 O(1)，入栈时，将新元素存入栈顶位置，并更新栈顶指针；出栈时，弹出栈顶元素，并调整栈顶指针。

4、应用场景

常用于函数调用栈、表达式求值、浏览器的后退和前进功能等场景，在函数调用时，每调用一个函数，就会将函数的相关信息（如返回地址、参数等）压入栈中，当函数执行完毕后，再从栈中弹出这些信息，以返回到上一个函数继续执行。

四、队列

1、存储方式

队列是一种先进先出（FIFO）的线性数据结构，同样可以用数组或链表来实现，用数组实现时，队头元素在数组的起始位置，队尾元素在数组的末尾；用链表实现时，队头为链表的表头节点，队尾为链表的最后一个节点。

2、访问方式

主要关注队头和队尾元素的访问，对于用数组实现的循环队列，通过队头指针和队尾指针可以方便地确定队头和队尾元素的位置；对于链表实现的队列，通过头指针和尾指针也可以快速访问队头和队尾元素，时间复杂度均为 O(1)。

3、插入和删除操作

插入（入队）操作在队尾进行，删除（出队）操作在队头进行，时间复杂度均为 O(1)，入队时，将新元素添加到队尾位置，并更新队尾指针；出队时，弹出队头元素，并调整队头指针。

4、应用场景

广泛应用于任务调度、缓冲区管理等场景，在打印机任务队列中，打印任务按照先来先服务的原则排队等待打印，先提交的任务先被打印。

五、堆

1、存储方式

堆是一种特殊的完全二叉树，通常使用数组来存储，对于一个有 n 个节点的堆，其节点在数组中的存储位置满足特定的父子关系，对于最大堆，对于任意节点 i（i > 0），其父节点为floor(i/2)，左子节点为2i，右子节点为2i + 1。

2、访问方式

可以通过数组下标快速定位到任意节点及其父节点、子节点，时间复杂度为 O(1)，要访问堆中下标为 i 的节点的左子节点，直接计算2 * i 即可得到其在数组中的下标。

3、插入和删除操作

插入操作相对复杂，需要在数组的末尾添加新元素，然后通过向上调整（过滤）操作来维护堆的性质，平均时间复杂度为 O(log n)；删除操作通常是删除堆顶元素，然后将堆的最后一个元素移到堆顶位置，再通过向下调整（筛选）操作来恢复堆的性质，平均时间复杂度也为 O(log n)。

4、应用场景

常用于优先级队列的实现、图算法中的最短路径问题（如 Dijkstra 算法）、堆排序等场景，在操作系统中，进程调度可以根据进程的优先级构成一个优先级队列（用堆实现），优先执行优先级高的进程。

存储结构	存储方式	访问方式	插入操作	删除操作	应用场景
数组	连续存储	随机访问 O(1)	平均 O(n)	不常用	随机访问频繁，插入删除少
链表	非连续，节点含指针	顺序访问 O(n)	平均 O(1)	平均 O(1)	插入删除频繁，顺序不重要
栈	可由数组或链表实现	O(1)（栈顶）	O(1)（栈顶）	O(1)（栈顶）	函数调用栈、表达式求值等
队列	可由数组或链表实现	O(1)（队头/队尾）	O(1)（队尾/队头）	任务调度、缓冲区管理等
堆	通常用数组存储（完全二叉树）	O(1)（节点定位）	平均 O(log n)	平均 O(log n)	优先级队列、最短路径问题等

FAQs

问题 1：为什么数组的插入和删除操作比链表慢？

答：数组要求元素在内存中连续存储，插入或删除元素时需要移动大量后续元素来保持连续性，所以时间复杂度较高；而链表的节点在物理位置上不连续，插入和删除只需修改相邻节点的指针指向，无需移动元素，操作相对快捷。

问题 2：栈和队列的主要区别是什么？

答：栈是后进先出（LIFO）的数据结构，主要操作是入栈（在栈顶插入元素）和出栈（弹出栈顶元素）；队列是先进先出（FIFO）的数据结构，主要操作是入队（在队尾插入元素）和出队（弹出队头元素），它们在数据的进出顺序以及对数据的操作重点上有所不同。

小编有话说

存储结构的选择需要根据具体的应用需求来决定，如果对数据的随机访问速度要求高，数组可能是较好的选择；如果数据的插入和删除操作频繁且顺序不重要，链表会更合适；而栈和队列则分别适用于具有后进先出和先进先出特性的场景，在实际开发中，理解各种存储结构的特点和适用场景，能够帮助我们更高效地设计和实现数据存储与处理的逻辑。