栈、队列、链表
一、栈
1. 定义
栈是一种线性数据结构，遵循后进先出（LIFO, Last In First Out）的原则。这意味着最后被添加到栈中的元素将会是最先被移除的元素。
2. 基本操作
- Push：将一个元素添加到栈顶。
- Pop：移除并返回栈顶的元素。
- Peek 或 Top：查看栈顶的元素，但不会移除它。
- IsEmpty：检查栈是否为空。
- Size：返回栈中元素的数量。
3. 特点
- 后进先出：栈的操作总是发生在栈顶。
- 动态性：栈的大小是动态的，可以根据需要增长或缩小。
- 简单高效：插入和删除操作的时间复杂度为 O(1)。
4. 应用
- 函数调用：编程语言中的函数调用栈。
- 表达式求值：如中缀表达式转后缀表达式。
- 回溯算法：如迷宫问题、图的深度优先搜索（DFS）。
二、队列
1. 定义
队列是一种线性数据结构，遵循先进先出（FIFO, First In First Out）的原则。这意味着最先被添加到队列中的元素将会是最先被移除的元素。
2. 基本操作
- Enqueue：在队列的尾部添加一个新元素。
- Dequeue：从队列的头部移除并返回一个元素。
- Front 或 Peek：查看队列头部的元素，但不会移除它。
- IsEmpty：检查队列是否为空。
- Size：返回队列中元素的数量。
3. 特点
- 先进先出：队列的操作分别发生在队首和队尾。
- 动态性：队列的大小是动态的，可以根据需要增长或缩小。
- 简单高效：插入和删除操作的时间复杂度为 O(1)。
4. 应用
- 任务调度：操作系统的进程调度。
- 打印任务：打印机中的文档打印。
- 消息队列：网络通信中的消息传递。
- 缓存系统：如 LRU（最近最少使用）缓存。
三、链表
1. 定义
链表（Linked List）是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据部分和指向列表中下一个节点的引用（或指针）。与数组不同的是，链表中的元素在内存中不是连续存储的，而是通过每个节点的指针相互链接起来。
2. 链表类型
-
单向链表（Singly Linked List）：
- 每个节点只包含一个指向前一个节点或后一个节点的指针。
- 只能从头节点开始遍历至尾节点。
-
双向链表（Doubly Linked List）：
- 每个节点包含两个指针，一个指向前一个节点，另一个指向后一个节点。
- 支持双向遍历，即可以从头节点遍历到尾节点，也可以从尾节点遍历回头节点。
-
循环链表（Circular Linked List）：
- 单向或双向链表的一种变体，其中最后一个节点的指针指向第一个节点，形成一个环。
- 在某些应用场景中，循环链表可以简化算法的实现。
3. 基本操作
- 插入：在链表的某个位置插入一个新的节点。根据插入的位置不同，分为头插、尾插和中间插入。
- 删除：从链表中移除一个节点。同样，根据删除的位置不同，有头删、尾删和中间删除。
- 查找：在链表中搜索特定值的节点。
- 遍历：按顺序访问链表中的每一个节点。
4. 链表优缺点
链表的优点：
- 动态性：链表的大小是动态的，可以根据需要增长或缩小。
- 插入和删除效率高：在链表中插入或删除节点通常只需要改变相关节点的指针，而不必像数组那样移动大量元素。
链表的缺点：
- 随机访问效率低：不像数组可以通过索引直接访问任意位置的元素，链表必须从头节点或尾节点开始逐个访问，直到找到目标节点。
- 额外的空间开销：每个节点除了存储数据外，还需要存储一个或两个指针，这会占用额外的内存空间。
5. 应用
- 实现其他数据结构：如栈、队列、哈希表。
- 文件系统：管理文件系统的目录和文件。
- 内存管理：管理内存块的分配和释放。
- 多任务调度：循环链表在多任务调度中非常有用。
四、总结
- 栈：适合需要后进先出操作的场景，如函数调用、表达式求值等。
- 队列：适合需要先进先出操作的场景，如任务调度、消息传递等。
- 链表：适合需要灵活插入和删除操作的场景，如文件系统管理、内存管理等。