数据结构 - 栈和队列

栈和队列的定义

• 栈和队列是两种常用的、重要的数据结构
• 栈和队列是限定插入和删除只能在表的 “端点” 进行的 线性表
  • 栈和队列是线性表的子集（是插入和删除位置受限的线性表）

栈的定义和特点

栈(stack) 是一个特殊的线性表，是限定仅在一端（通常是表尾）进行插入和删除操作的线性表。表尾的一端有其特殊含义，称为 栈顶(top) ，相应地，表头称为 栈底(bottom) 。

栈的特点就是 后进先出（LIFO, Last In First Out）。

为了更好的理解，我们可以把栈想象成 手电筒、子弹夹。像手电筒装电池，后进去的电池先拿出来。

子弹夹也是，最后填充的子弹在子弹夹的顶端，最先填充的子弹在尾端。

栈的相关概念

• 插入元素到 栈顶 的操作，称为 入栈(Push) 。
• 从 栈顶 删除最后一个元素的操作，称为 出栈(Pop) 。

栈的示意图

栈的应用

由于栈的操作具有 后进先出 的固有特性，使得栈成为程序设计中的有用工具。另外，如果问题解的过程具有 后进先出 的天然特性话，则求解的算法中也必然需要利用 栈。例如：

数制转换	表达式求值
括号匹配的检验	八皇后问题
行编辑程序	函数调用
迷宫求解	递归调用的实现

队列的定义和特点

在队列中，只允许在一端进行插入，而在另一端删除元素。允许插入的一端叫做 队尾(rear) ，允许删除的一端则称为 队头(front) 。

队列的特点就是 先进先出（FIFO, First In First Out）。

队列的示意图

队列的常见应用

由于队列的操作具有 先进先出 的特性，使得队列成为程序设计中解决突似 排队问题 的有用工具。

例如：

• 脱机打印输出:按申请的先后顺序依次输出。
• 多用户系统中，多个用户排成队，分时地循环使用CPU和主存。
• 按用户的优先级排成多个队，每个优先级一个队列。
• 实时控制系统中，信号按接收的先后顺序依次处理。
• 网络电文传输，按到达的时间先后顺序依次进行。