栈和队列

博主： wmicheng
发布时间：2025 年 02 月 10 日
29 次浏览
暂无评论
10009字数
分类：数据结构

## 栈和队列

## **栈**

### 基本概念

> #### 栈的定义：

- **栈**（Stack）是只允许在一端进行插入或删除操作的线性表
- **逻辑结构**：与普通线性表相同
- **数据的运算**：插入、删除操作有区别
- **栈顶**：允许插入和删除的一端，对应元素被称为栈顶元素
- **栈底**：不允许插入和删除的一端，对应元素被称为栈底元素
- **特点**：后进先出`Last In First Out`（`LIFO`）

> #### 栈的基本操作：

`InitStack(&S)`：**初始化栈**。构造一个空栈`S`，分配内存空间。

`DestroyStack(&S)`：**销毁栈**。销毁并释放栈`S`所占用的内存空间。

`Push(&S,x)`：**进栈**，若栈`S`未满，则将`x`加入使之成为新栈顶。

`Pop(&S,&x)`：**出栈**，若栈`S`非空，则弹出栈顶元素，并用`x`返回。

`GetTop(S, &x)`：**读栈顶元素**。若栈`S`非空，则用`x`返回栈顶元素

`StackEmpty(S)`：**判断栈空**。若`S`为空，则返回`true`，否则返回`false`。

**出栈顺序数量：**

- `n`个不同元素进栈，出栈元素不同排列的个数为：$\frac{1}{\mathrm{n}+1} C_{2 n}^{n}$(**卡特兰**（**Catalan**）数)

### 栈的存储结构

| 顺序栈的定义和初始化                          | 链栈的定义和初始化      |
| --------------------------------------------- | ----------------------- |
| ![栈的顺序存储结构](https://wmicheng.top/images/note/img/栈的顺序存储结构.png) | ![链栈](https://wmicheng.top/images/note/img/链栈.png)   |
| ![进栈操作](https://wmicheng.top/images/note/img/进栈操作.png)                 | ![链栈1](https://wmicheng.top/images/note/img/链栈1.png) |
| ![出栈操作](https://wmicheng.top/images/note/img/出栈操作.png)                 | ![链栈2](https://wmicheng.top/images/note/img/链栈2.png) |
| ![读取栈顶元素](https://wmicheng.top/images/note/img/读取栈顶元素.png)         |                         |

**注意**：也可以让栈顶指针`top`先指向`0`，每次进栈`S.top++`，出栈`--S.top`

**共享栈：**

- 使用静态数组要求提前规定好栈的大小，容易造成内存资源的浪费因此共享栈应运而生
- 两个栈共享同一片空间，`0、1`号栈朝着同一方向进栈
- 栈满的条件：`top0 + 1 == top1`

![共享栈](https://wmicheng.top/images/note/img/共享栈.png)

### 栈的链式存储结构

> #### 栈的链式存储实质

- 进栈：头插法建立单链表，也就是对头结点的后插操作
- 出栈：单链表的删除操作，对头结点的“后删”操作
- 推荐使用不带头结点的链栈
- 创销增删查的操作参考链表

| 顺序栈                        | 链栈                      |
| ----------------------------- | ------------------------- |
| ![顺序栈XM](https://wmicheng.top/images/note/img/顺序栈XM.png) | ![链栈XM](https://wmicheng.top/images/note/img/链栈XM.png) |

## **队列**

### 队列的基本概念

> #### 队列的定义：

- **栈**（Stack）是只允许在一端进行插入或删除操作的操作受限的线性表
- **队列**（Queue）是只允许在一端进行插入，在另一端删除的线性表
- **队头**：允许删除的一端，对应的元素被称为队头元素
- **队尾**：允许插入的一端，对应的元素被称为队尾元素
- **队列的特点**：先进先出`First In First Out`（**FIFO**）

### **队列的基本操作**

`InitQueue(&Q)`：初始化队列，构造一个空队列`Q`。

`DestroyQueue(&Q)`：销毁队列。销毁并释放队列Q所占用的内存空间。

`EnQueue(&Q,x)`：入队，若队列`Q`未满，将`x`加入，使之成为新的队尾。

`DeQueue(&Q,&x)`：出队，若队列`Q`非空，删除队头元素，并用`x`返回。

`GetHead(Q,&x)`：读队头元素，若队列`Q`非空，则将队头元素赋值给`x`。

`QueueEmpty(Q)`：判队列空，若队列`Q`为空返回`true`，否则返回`false`。

### 队列的顺序存储结构

> #### 队列&循环队列的定义和初始化

| 队列的定义和初始化循环                            | 循环队列的定义和初始化                |
| ------------------------------------------------- | ------------------------------------- |
| ![队列的顺序存储结构](https://wmicheng.top/images/note/img/队列的顺序存储结构.png) | ![出队操作](https://wmicheng.top/images/note/img/出队操作.png)         |
| ![入队操作](https://wmicheng.top/images/note/img/入队操作.png)                     | ![循环队列入队](https://wmicheng.top/images/note/img/循环队列入队.png) |

![循环队列出队](https://wmicheng.top/images/note/img/循环队列出队.png)

> #### 入队操作

- 通过取余操作，只要队列不满，就可以一直利用之前已经出队了的空间，逻辑上实现了循环队列的操作
- 于是，队列已满的条件：队尾指针的再下一个位置是队头，即`(Q.rear+1)%MaxSize==Q.front;`
- 代价：牺牲了一个存储单元，因为如果`rear`和`front`相同，与判空的条件相同了

#### 判断队列已满/已空

|              **判断队列已满/已空**              |
| :---------------------------------------------: |
| ![判断队列已满已空1](https://wmicheng.top/images/note/img/判断队列已满已空1.jpg) |
| ![判断队列已满已空2](https://wmicheng.top/images/note/img/判断队列已满已空2.jpg) |
| ![判断队列已满已空3](https://wmicheng.top/images/note/img/判断队列已满已空3.jpg) |

### 队列的链式存储结构

| 队列的链式存储结构（带头结点）                               | 队列的链式存储结构（不带头结点）                             |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![队列的链式存储结构（带头结点）](https://wmicheng.top/images/note/img/队列的链式存储结构（带头结点）.png) | ![队列的链式存储结构（不带头结点）](https://wmicheng.top/images/note/img/队列的链式存储结构（不带头结点）.png) |
| ![入队（带头结点）](https://wmicheng.top/images/note/img/入队（带头结点）.png)                | ![入队（不带头结点）](https://wmicheng.top/images/note/img/入队（不带头结点）.png)            |
| ![出队（带头结点）](https://wmicheng.top/images/note/img/出队（带头结点）.png)                | ![出队（不带头结点）](https://wmicheng.top/images/note/img/出队（不带头结点）.png)            |

> #### 队列满的条件

- 顺序存储：预分配的空间耗尽时队满
- 链式存储：一般不会队满，除非内存不足
- 因此一般不用考虑队满

### 双端队列

> #### 定义

- 双端队列：只允许从两端插入、两端删除的线性表
- 输入受限的双端队列：只允许从一端插入、两端删除的线性表
- 输出受限的双端队列：只允许从两端插入、一端删除的线性表
- 不管是怎么样的双端队列实际都是栈和队列的变种

> #### 考点

- 判断输出序列合法性
- 在栈中合法的输出序列，在双端队列中必定合法

## **栈在括号匹配中的应用**

### 括号匹配问题

- 若有括号无法被匹配则出现编译错误
- 遇到左括号就入栈
- 遇到右括号，就“消耗”一个左括号

![括号匹配问题](https://wmicheng.top/images/note/img/括号匹配问题.png)

> #### 代码实现

![括号匹配问题实现](https://wmicheng.top/images/note/img/括号匹配问题实现.png)

### 栈在表达式求值中的应用

> #### 算数表达式

- 由三个部分组成：操作数、运算符、界限符
- 我们平时写的算术表达式都是中缀表达式
- 如何可以不用界限符也能无歧义地表达运算顺序
- Reverse Polish notation（逆波兰表达式=后缀表达式）
- Polish notation（波兰表达式=前缀表达式）

> #### 中缀、后缀、前缀表达式

![缀表达式](https://wmicheng.top/images/note/img/缀表达式.jpg)

### 中缀转后缀的方法

| 中缀转后缀的方法（手算）                                     | 中缀表达式转后缀表达式（机算用栈实现）                       |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![中缀转后缀的方法（手算1](https://wmicheng.top/images/note/img/中缀转后缀的方法（手算1.jpg) | ![中缀表达式转后缀表达式（机算）](https://wmicheng.top/images/note/img/中缀表达式转后缀表达式（机算）.jpg) |
| ![中缀转后缀的方法（手算](https://wmicheng.top/images/note/img/中缀转后缀的方法（手算.jpg) | ![中缀表达式转后缀表达式（机算）1](https://wmicheng.top/images/note/img/中缀表达式转后缀表达式（机算）1.jpg) |
| ![中缀转后缀的方法（手算3](https://wmicheng.top/images/note/img/中缀转后缀的方法（手算3.jpg) | ![中缀表达式转后缀表达式（机算）2](https://wmicheng.top/images/note/img/中缀表达式转后缀表达式（机算）2.jpg) |

> #### 中缀转后缀的方法（手算）

- 确定中缀表达式中各个运算符的运算顺序
- 选择下一个运算符，按照「左操作数右操作数运算符」的方式组合成一个新的操作数
- 如果还有运算符没被处理，就继续第二步
- 注意：运算顺序不唯一，因此对应的后缀表达式也不唯一
- “左优先”原则：只要左边的运算符能先计算，就优先算左边的，保证手算和机算是一致的

> #### 中缀表达式转后缀表达式（机算，用栈实现）

- 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。
- 从左到右处理各个元素，直到末尾。可能遇到三种情况：
  1. 遇到操作数。直接加入后缀表达式。
  2. 遇到界限符。遇到“(”直接入栈；遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意：“(”不加入后缀表达式。
  3. 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。
- 按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

### 后缀表达式的计算

| 后缀表达式的计算（手算                                       | 后缀表达式的计算（机算，用栈实现）                           |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![后缀表达式的计算（手算）](https://wmicheng.top/images/note/img/后缀表达式的计算（手算）.jpg) | ![中缀转后缀的方法（机算](https://wmicheng.top/images/note/img/中缀转后缀的方法（机算.jpg) |
| ![后缀表达式的计算（手算）1](https://wmicheng.top/images/note/img/后缀表达式的计算（手算）1.jpg) | ![中缀转后缀的方法（机算1](https://wmicheng.top/images/note/img/中缀转后缀的方法（机算1.jpg) |
| ![中缀转后缀的方法（手算2](https://wmicheng.top/images/note/img/中缀转后缀的方法（手算2.jpg) | ![中缀转后缀的方法（机算2](https://wmicheng.top/images/note/img/中缀转后缀的方法（机算2.jpg) |

> #### 后缀表达式的计算（手算）

- 从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应运算，合体为一个操作数
- 注意：两个操作数的左右顺序
- 特点：最后出现的操作数先被运算，LIFO（后进先出），可以使用栈来完成这个步骤
- “左优先”原则：只要左边的运算符能先计算，就优先算左边的

> #### 后缀表达式的计算（机算，用栈实现）

- 从左往右扫描下一个元素，直到处理完所有元素
- 若扫描到操作数则压入栈，并回到第一步；否则执行第三步
- 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到第一步
- 注意：先出栈的是“右操作数”
- 若表达式合法，则最后栈中只会留下一个元素，就是最终结果
- 后缀表达式适用于基于栈的编程语言（stack-orientedprogramming language），如：Forth、PostScript）（了解）

### 中缀转前缀的方法

| 中缀表达式转前缀表达式（手算）                               | 中缀表达式的计算（机算，用栈实现）                           |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| ![中缀表达式转前缀表达式（手算）](https://wmicheng.top/images/note/img/中缀表达式转前缀表达式（手算）.jpg) | ![中缀表达式的计算（用栈实现）](https://wmicheng.top/images/note/img/中缀表达式的计算（用栈实现）.jpg) |
| ![中缀表达式转前缀表达式（手算）1](https://wmicheng.top/images/note/img/中缀表达式转前缀表达式（手算）1.jpg) | ![中缀表达式的计算（用栈实现）1](https://wmicheng.top/images/note/img/中缀表达式的计算（用栈实现）1.jpg) |

> #### 中缀表达式转前缀表达式（手算）

- 确定中缀表达式中各个运算符的运算顺序
- 选择下一个运算符，按照「运算符左操作数右操作数」的方式组合成一个新的操作数
- 如果还有运算符没被处理，就继续第二步
- “右优先”原则：只要右边的运算符能先计算，就优先算右边的

> #### 中缀表达式的计算（机算，用栈实现）

- 中缀表达式的计算=中缀转后缀+后缀表达式求值，两个算法的结合
- 用栈实现中缀表达式的计算：
  1. 初始化两个栈，操作数栈和运算符栈
  2. 若扫描到操作数，压入操作数栈
  3. 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）

## **栈与队列的应用**

|           `栈的应用`            |                         `队列的应用`                         |
| :-----------------------------: | :----------------------------------------------------------: |
|        **递归中的应用**         | **树的层次遍历**    **图的广度优先遍历****操作系统中的应用** |
| ![栈的应用1](https://wmicheng.top/images/note/img/栈的应用1.jpg) |             ![队列的应用3](https://wmicheng.top/images/note/img/队列的应用3.jpg)              |
| ![栈的应用2](https://wmicheng.top/images/note/img/栈的应用2.jpg) |             ![队列的应用2](https://wmicheng.top/images/note/img/队列的应用2.jpg)              |
| ![栈的应用3](https://wmicheng.top/images/note/img/栈的应用3.jpg) |             ![队列的应用1](https://wmicheng.top/images/note/img/队列的应用1.jpg)              |

### 特殊矩阵的压缩储存

**一维数组的存储结构：**

- 起始地址：`LOC`
- 各数组元素大小相同，且物理上连续存放。
- 数组元素`a[i]`的存放地址= `LOC + i * sizeof(ElemType)`

**二维数组的存储结构：**

- 分为行优先和列优先，本质就是把二维的逻辑视角转换为内存中的一维储存
- M行N列的二维数组b\[M]\[N]中，若按行优先存储，则b\[i]\[j]的存储地址= `LOC + (i*N + j) * sizeof(ElemType)`
- M行N列的二维数组b\[M]\[N]中，若按列优先存储，则b\[i]\[j]的存储地址= `LOC + ( j*M+ i ) * sizeof(ElemType)`
- 二维数组也有随机存储的特性

**普通矩阵的存储：**

- 可用二维数组存储
- 注意：描述矩阵元素时，行、列号通常从1开始；而描述数组时通常下标从0开始
- 某些特殊矩阵可以压缩存储空间（比如对称矩阵）

**对称矩阵的压缩存储：**

- 若n阶方阵中任意一个元素ai,j都有ai,j = aj,i则该矩阵为对称矩阵
- 普通存储：n\*n二维数组
- 压缩存储策略：只存储主对角线+下三角区（或主对角线+上三角区），按行优先原则将各元素存入一维数组中
- 数组大小应为多少：(1+n)\*n/2
- 站在程序员的角度，对称矩阵压缩存储后怎样才能方便使用：可以实现一个“映射”函数矩阵下标->一维数组下标
- 按行优先的原则，ai,j是第几个元素：
  
  $$
  k=\left\{\begin{array}{ll} \frac{i(i-1)}{2}+j-1, & i\geq j(\text { 下三角区和主对角线元素) } \\ \frac{j(j-1)}{2}+i-1, & i<j\left(\text { 上三角区元素 } a_{i j}=a_{j i}\right) \end{array}\right.
  $$

**三角矩阵的压缩存储：**

- 下三角矩阵：除了主对角线和下三角区，其余的元素都相同
- 上三角矩阵：除了主对角线和上三角区，其余的元素都相同
- 压缩存储策略：按行优先原则将橙色区元素存入一维数组中，并在最后一个位置存储常量c
- 下三角矩阵，按行优先的原则，ai,j是第几个元素：
  
  $$
  k=\left\{\begin{array}{ll} \frac{i(i-1)}{2}+j-1, & i \geqslant j \text { (下三角区和主对角线元素) } \\ \frac{n(n+1)}{2}, & i<j \text { (上三角区元素) } \end{array}\right.
  $$
- 上三角矩阵，按行优先的原则，ai,j是第几个元素：
  
  $$
  k=\left\{\begin{array}{ll} \frac{(i-1)(2 n-i+2)}{2}+(j-i), & i \leqslant j(\text { 上三角区和主对角线元素) } \\ \frac{n(n+1)}{2}, & i>j(\text { 下三角区元素) } \end{array}\right.
  $$

**三对角矩阵的压缩存储：**

- 三对角矩阵，又称带状矩阵：当|i - j|>1时，有ai,j = 0 （1≤ i, j ≤n）
- 压缩存储策略：按行优先（或列优先）原则，只存储带状部分
- 按行优先的原则，ai,j是第几个元素：

**稀疏矩阵的压缩存储：**

- 稀疏矩阵：非零元素远远少于矩阵元素的个数
- 压缩存储策略1：顺序存储——三元组$<i（行），j（列），v（值）>$，失去了数组随机存储的特性
- 压缩存储策略2：链式存储，十字链表法
  
  ![稀疏矩阵压缩](https://wmicheng.top/images/note/img/稀疏矩阵压缩.jpg)

最后修改：2025 年 02 月 11 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

栈和队列

wmicheng • 2025 年 02 月 10 日

## 栈和队列

## **栈**

### 基本概念

> #### 栈的定义：

> #### 栈的基本操作：

`InitStack(&S)`：**初始化栈**。构造一个空栈`S`，分配内存空间。

`DestroyStack(&S)`：**销毁栈**。销毁并释放栈`S`所占用的内存空间。

`Push(&S,x)`：**进栈**，若栈`S`未满，则将`x`加入使之成为新栈顶。

`Pop(&S,&x)`：**出栈**，若栈`S`非空，则弹出栈顶元素，并用`x`返回。

`GetTop(S, &x)`：**读栈顶元素**。若栈`S`非空，则用`x`返回栈顶元素

`StackEmpty(S)`：**判断栈空**。若`S`为空，则返回`true`，否则返回`false`。

**出栈顺序数量：**

- `n`个不同元素进栈，出栈元素不同排列的个数为：$\frac{1}{\mathrm{n}+1} C_{2 n}^{n}$(**卡特兰**（**Catalan**）数)

### 栈的存储结构

**注意**：也可以让栈顶指针`top`先指向`0`，每次进栈`S.top++`，出栈`--S.top`

**共享栈：**

![共享栈](https://wmicheng.top/images/note/img/共享栈.png)

### 栈的链式存储结构

> #### 栈的链式存储实质

## **队列**

### 队列的基本概念

> #### 队列的定义：

### **队列的基本操作**

`InitQueue(&Q)`：初始化队列，构造一个空队列`Q`。

`DestroyQueue(&Q)`：销毁队列。销毁并释放队列Q所占用的内存空间。

`EnQueue(&Q,x)`：入队，若队列`Q`未满，将`x`加入，使之成为新的队尾。

`DeQueue(&Q,&x)`：出队，若队列`Q`非空，删除队头元素，并用`x`返回。

`GetHead(Q,&x)`：读队头元素，若队列`Q`非空，则将队头元素赋值给`x`。

`QueueEmpty(Q)`：判队列空，若队列`Q`为空返回`true`，否则返回`false`。

### 队列的顺序存储结构

> #### 队列&循环队列的定义和初始化

![循环队列出队](https://wmicheng.top/images/note/img/循环队列出队.png)

> #### 入队操作

#### 判断队列已满/已空

### 队列的链式存储结构

> #### 队列满的条件

- 顺序存储：预分配的空间耗尽时队满
- 链式存储：一般不会队满，除非内存不足
- 因此一般不用考虑队满

### 双端队列

> #### 定义

> #### 考点

- 判断输出序列合法性
- 在栈中合法的输出序列，在双端队列中必定合法

## **栈在括号匹配中的应用**

### 括号匹配问题

- 若有括号无法被匹配则出现编译错误
- 遇到左括号就入栈
- 遇到右括号，就“消耗”一个左括号

![括号匹配问题](https://wmicheng.top/images/note/img/括号匹配问题.png)

> #### 代码实现

![括号匹配问题实现](https://wmicheng.top/images/note/img/括号匹配问题实现.png)

### 栈在表达式求值中的应用

> #### 算数表达式

> #### 中缀、后缀、前缀表达式

![缀表达式](https://wmicheng.top/images/note/img/缀表达式.jpg)

### 中缀转后缀的方法

> #### 中缀转后缀的方法（手算）

> #### 中缀表达式转后缀表达式（机算，用栈实现）

### 后缀表达式的计算

> #### 后缀表达式的计算（手算）

> #### 后缀表达式的计算（机算，用栈实现）

### 中缀转前缀的方法

> #### 中缀表达式转前缀表达式（手算）

> #### 中缀表达式的计算（机算，用栈实现）

## **栈与队列的应用**

### 特殊矩阵的压缩储存

**一维数组的存储结构：**

- 起始地址：`LOC`
- 各数组元素大小相同，且物理上连续存放。
- 数组元素`a[i]`的存放地址= `LOC + i * sizeof(ElemType)`

**二维数组的存储结构：**

**普通矩阵的存储：**

**对称矩阵的压缩存储：**

**三角矩阵的压缩存储：**

**三对角矩阵的压缩存储：**

**稀疏矩阵的压缩存储：**

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

栈和队列

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款