栈、队列、链表

一、栈

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. 链表类型

1. 单向链表（Singly Linked List）：

   • 每个节点只包含一个指向前一个节点或后一个节点的指针。
   • 只能从头节点开始遍历至尾节点。

2. 双向链表（Doubly Linked List）：

   • 每个节点包含两个指针，一个指向前一个节点，另一个指向后一个节点。
   • 支持双向遍历，即可以从头节点遍历到尾节点，也可以从尾节点遍历回头节点。

3. 循环链表（Circular Linked List）：

   • 单向或双向链表的一种变体，其中最后一个节点的指针指向第一个节点，形成一个环。
   • 在某些应用场景中，循环链表可以简化算法的实现。

3. 基本操作

• 插入：在链表的某个位置插入一个新的节点。根据插入的位置不同，分为头插、尾插和中间插入。
• 删除：从链表中移除一个节点。同样，根据删除的位置不同，有头删、尾删和中间删除。
• 查找：在链表中搜索特定值的节点。
• 遍历：按顺序访问链表中的每一个节点。

4. 链表优缺点 

链表的优点：

• 动态性：链表的大小是动态的，可以根据需要增长或缩小。
• 插入和删除效率高：在链表中插入或删除节点通常只需要改变相关节点的指针，而不必像数组那样移动大量元素。

链表的缺点：

• 随机访问效率低：不像数组可以通过索引直接访问任意位置的元素，链表必须从头节点或尾节点开始逐个访问，直到找到目标节点。
• 额外的空间开销：每个节点除了存储数据外，还需要存储一个或两个指针，这会占用额外的内存空间。

5. 应用

• 实现其他数据结构：如栈、队列、哈希表。
• 文件系统：管理文件系统的目录和文件。
• 内存管理：管理内存块的分配和释放。
• 多任务调度：循环链表在多任务调度中非常有用。

四、总结

• 栈：适合需要后进先出操作的场景，如函数调用、表达式求值等。
• 队列：适合需要先进先出操作的场景，如任务调度、消息传递等。
• 链表：适合需要灵活插入和删除操作的场景，如文件系统管理、内存管理等。