软件工程师手册/生命周期/设计/选择数据结构
< 软件工程师手册
存在大约几种标准的数据结构类型。
- 堆栈
- 队列
- 更多内容即将推出...
这些可以通过各种方式实现，但每种结构的特定特征始终保持不变。
简而言之，堆栈是遵循后进先出 (LIFO) 范式的集合数据。这意味着，放入堆栈的最后一个项目是第一个被取出的项目。除了此项目以外，其他项目无法直接访问或移除，除非完全清除堆栈。
以下是人们可以对堆栈执行的常见操作
- push - 将某项放入堆栈顶端
- pop - 弹出堆栈顶端（最后一个放入的项目）
- peek - 查看堆栈顶端的项目（最后一个放入的项目）
- is_empty - 检查堆栈是否为空
- is_full - 检查堆栈是否已满
请记住，人们实现堆栈的具体方式可能完全不同，这可能导致堆栈上可用的方法也有所不同。例如，如果堆栈是静态的（无法增长）并且大小为 N，则使用 is_full 方便地判断堆栈是否已满。但是，如果堆栈是动态的（如果需要，可以增长），则当堆栈在技术上无法填满时，is_full 就不方便。尽管有些人可能选择使用具有上限的动态堆栈，这使得 is_full 再次有用。此外，这取决于创建堆栈的开发人员的风格。最起码，总会存在类似 push 或 pop 的操作，尽管它们的名称可能不同。
一些堆栈的具体示例
- 想想 Pez 糖果分配器 - 你放进去的最后一颗糖果是第一个被拿出来的。
- 这里还有一个示例 - 自助餐线的餐盘分配器。餐盘堆放在弹簧加载的平台上，顾客从最上面逐个拿取。
一些与计算机相关的示例
- RPN（逆波兰表示法）计算器。
队列是遵循先进先出 (FIFO) 范式的集合数据。这意味着放入队列的第一个数据也是从队列中返回的第一个数据。无法从队列中随机访问项目，只能访问处于“第一个”位置的项目。如果你想从时间的角度来考虑，数组中最旧的项目是第一个返回的项目，也是唯一可以访问的项目。
以下是队列可以执行的常见操作
- enqueue - 将某项放入队列末尾
- dequeue - 移除队列中的第一个项目（最旧的项目）
- is_full - 检查队列是否已满
- is_empty - 检查队列是否为空
与堆栈一样，is_full（也许还有 is_empty）在不同的实现（静态数组、动态数组、链表……等等）中可能有用也可能没有用。哪些方法可用，还取决于创建队列的开发人员的风格。最起码，总会存在 enqueue 和 dequeue，尽管它们的名称可能不同。
一些队列的具体示例
- 游乐园的游乐设施队伍 - 最前面的人，等待时间最长，最先玩（或下一个玩）。
- 银行的队伍，人们在等待下一个空闲的柜台。