栈和队列是两种常用的、重要的数据结构。

栈和队列是限定插入和删除只能在表的“端点”进行的线性表。

3.1.1、栈的定义和特点

栈（stack）是一个特殊的线性表，是限定仅在一端（通常是表尾）进行插入和删除操作的线性表
又称为 后进先出（Last In First Out）的线性表，简称 LIFO 结构。

  • 栈是仅在尾部进行插入、删除操作的线性表

  • 表尾（即 a 端 ）称为 栈顶 Top，表头（即a端）称为 栈底 Base

  • 插入元素到 栈顶（即表尾）的操作，称为 入栈（PUSH）

  • 从 栈顶（即表尾）删除最后一个元素的操作，称为 出栈（POP）

640.gif

思考：假设有3个元素 a、b、c ，入栈顺序是 a、b、c，则它们出栈的顺序有几种情况？

栈的相关概念

  1. 定义：限定只能在表的一端进行插入和删除运算的线性表（只能在栈顶操作）

  2. 逻辑结构：与线性表相同，仍为一对一关系

  3. 存储结构：用顺序栈和链栈存储均可，但以顺序栈更常见

  4. 运算规则：只能在栈顶运算，且访问结点时依照后进先出（LIFO）的原则

  5. 实现方法：关键是编写入栈和出栈函数，具体实现顺序栈和链栈的不同而不同

栈与一般线性表有什么不同

一般线性表 栈
逻辑结构 一对一 一对一
存储结构 顺序表、链表 顺序表、链表
运算规则 随机存取 后进先出（LIFO）

栈的应用

由于栈的操作具有后进先出的固有特征，如果需要求解的过程具有“后进先出”的天然特性的话，则求解的算法中也必然需要利用“栈”。

  • 数制转换 、表达式求值、括号校验匹配

  • 八皇后问题、行编辑程序、函数调用

  • 迷宫求解、递归调用是实现

3.1.2、队列的定义和特点

队列（queue）是一种 先进先出（First In First Out）FIFO 的线性表。在表一端插入（表尾），在另一端（表头）删除

队列的相关概念

  1. 定义：只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表（头删尾插）

  2. 逻辑结构：与线性表相同，仍为一对一关系

  3. 存储结构：顺序队或链队，以循环顺序队列更常见

  4. 运算规则：只能在队首和队尾运算，且访问节点时依照 先进先出（FIFO）的原则

  5. 实现方法：关键是掌握入队和出队的操作，具体实现依顺序队或链队的不同而不同。

640 (1).gif

队列的应用

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

  • 脱机打印机输出：按申请的顺序依次输出

  • 多用户系统中，多个用户排成队，分时的循环使用CPU和主存

  • 按用户的优先级排成多个队，每个优先级有个队列

  • 实时控制系统中，信号按接收的先后顺序依次处理

  • 网络电文传输，按到达的时间先后顺序依次进行