线性数据结构

线性数据结构是指数据元素按顺序排列，每个元素都与下一个和上一个元素连接（除了第一个和最后一个）。这种排列形成了一个线性序列，使得一次遍历数据变得容易。

数组

数组将元素存储在固定、连续的内存分配中，并通过索引或键来标识。

特性

• 固定大小，使其在内存使用上可预测。
• 索引效率高，提供快速的元素访问。
• 动态调整大小的性能差；调整大小需要分配新数组并复制元素。

链表

链表是通过链接连接的节点集合。每个节点包含一个数据字段和一个或多个指向其他节点的链接。

类型

• 单向链表: 节点只有一个指向下一个节点的链接。
• 双向链表: 节点既有指向下一个节点的链接，也有指向前一个节点的链接，增强了向后遍历的能力。

特性

• 动态大小，允许列表根据需要增长或缩小。
• 高效的插入和删除操作，无需移动元素。
• 索引效率低，因为访问元素通常需要从列表的开头遍历。

栈

栈是元素的集合，其添加和移除项目操作遵循后进先出（LIFO）原则。

特性

• 以 LIFO 方式操作，使其非常适合需要逆转的场景，例如撤销机制。
• 主要操作是 push（添加）和 pop（移除）。

队列

队列以先进先出（FIFO）顺序处理元素，操作包括在尾部添加和从头部移除。

特性

• 以 FIFO 方式操作，确保操作顺序得以保持。
• 主要操作是 enqueue（添加到尾部）和 dequeue（从头部移除）。

常见操作

• 访问: 根据位置检索元素。
• 搜索: 使用特定标准定位元素。
• 插入: 在预定位置添加元素。
• 删除: 从结构中移除元素。

应用

• 数组: 因其直接元素访问能力，是程序中数据存储的基础。
• 链表: 在实现基本数据结构（例如，栈、队列）或文本编辑器中的撤销功能等场景中非常有用。
• 栈: 对于管理函数调用、解析、递归和临时数据存储至关重要。
• 队列: 在广度优先搜索、进程调度和实时系统中的队列管理等算法中至关重要。