当前课程知识点：数据结构 > 第3章栈和队列 > 3.3 栈的应用 > 3.3 栈的应用

返回《数据结构》慕课在线视频课程列表

3.3 栈的应用在线视频

下一节:3.4栈与递归的实现

返回《数据结构》慕课在线视频列表

3.3 栈的应用课程教案、知识点、字幕

同学们大家好，我是云南大学信息学院教师孔兵

这节课我们讨论栈的应用和递归

上一节我们讲过

因为栈中插入和删除位置受限

这样的受限使栈具有一些特性

最重要的特征就是所谓的后进先出

后插入的先删除

正是因为这样的特性

在一些问题当中

我们可以使用这样的特性来比较有效的解决相关问题

下面，我们看两个例子

第1个例子是数制转换

10进制数和其它进制数的转换

是计算机实现计算的基本问题

解决这个问题的方法很多

其中一个简单的算法是基于下列的原理

就是n等于n整除d，乘以d加上n对d求余

其中n是10进制数，d是我们要转换的进制

比如d是8，表示要转换为8进制

我们看一个例子

10进制数，1348

如果转换为8进制数是2504

基于上述原理

它的转换过程如下

1348整除8，它的商是168

1348对8求余，余数是4

利用商168整除8商是 21

168对8求余，余数是0

用商21继续重复上述的计算

直到商为0，余数为2

我们观察它获得的余数

根据计算的先后次序

获得的次序是4052

从上面面我们看到

1348转换的8进制数是2504

从前向后看

它的次序和求余的计算次序刚好相反

那么，如果我们要编程实现这样的转换

可以在程序中利用一个栈

按照求得余数的次序入栈

例子中入栈的次序是4052

计算完成后再依次出栈

因为栈后进先出的特征

我们获得的出栈序列就是2504

在这个函数当中

利用栈后进先出的特征

解决了数制转换中

计算次序和最终8进制数正常次序相反的问题

第2个例子我们看一下括号匹配的检验

如果表达式中有三种括号，小括号

中括号和大括号

我们希望编写判定表达式中所含括号是否正确配对出现的算法

在这个问题中，也可以利用一个栈

我们忽略表达式中的其它成分

只关注括号序列

假设有例子中的括号系列

下面我们以它为例

来讨论一下

怎么利用战实现括号配对的检验

依次读入括号序列中的括号

遇到左括号，不管他的类型

就把它入栈

在括号序列中

首先遇到的左大括号

左中括号和左小括号，依次入栈

如果遇到的是右括号

则栈顶左括号出栈

进行考察

例子中，第4个读入了右小括号

把栈顶括号出栈

是左小括号

随后考察读入的又括号和出栈的栈顶左括号的匹配情况

可能有两种情况

如果左括号和右括号匹配则进行消解

例子当中，读入是右小括号

出栈的是左小括号

它们是匹配的

则进行消解

随后读入下一个括号

第二种情况是

读入的右括号和出栈的左括号不匹配

比如，读入的是右小括号

出栈的是左大括号或左中括号

这种情况就是括号不匹配

则可以直接判定括号匹配不正确

退出匹配检验函数

上述过程

就是利用栈进行括号匹配检验的主要过程

这个过程可以重复下去

在这样的过程当中

可能出现其它的几种情况

一是，读入右括号后，发现栈为空

这是右括号多了，没有相应的左括号

我们也可以判定括号匹配不正确

二是，括号序列已经读完

右括号都正常消解

但是栈中还有未被消解的左括号

说明左括号多了，没有匹配的右括号

这也可以判定括号匹配不正确

三是，括号序列读完

栈空

所有括号都被消解

这时就可以说括号配对是正确的

这是在应用的第2个例子

好了，今天的内容就到这儿

下节课我们讨论栈与递归的实现

同学们再见

数据结构课程列表：

前言

-1.算法概念导入

--1.1 算法概念导入

-2.数据结构课程介绍

--2.数据结构课程介绍

-数据结构前言PPT

第0章预备知识

-0.1变量、类型和表达式

--0.1变量、类型和表达式

-0.2 函数

-0.3 指针和单链表

--0.3 指针和单链表

-0.4 数组、指向函数的指针

--0.4 数组、指向函数的指针

-第0章预备知识讨论题

-数据结构第0章预备知识PPT

第1章绪论

-1.1什么是数据结构

--1.1什么是数据结构

--测试题

-1.2基本概念和术语

--1.2基本概念和术语

--测试题

-1.3数据结构的描述

--1.3数据结构的描述

--测试题

-1.4抽象数据类型的定义和实现

--1.4抽象数据类型的定义和实现

--测试题

-1.5算法和算法分析概念

--1.5算法和算法分析概念

--测试题

-1.6算法分析示例

--1.6算法分析示例

--测试题

-第1章绪论讨论题

-数据结构第1章绪论PPT

第2章线性表

-2.1 线性表的类型定义

--2.1线性表的类型定义

--测试题

-2.2线性表的顺序表示和实现

--2.2 线性表的顺序表示和实现

--测试题

-2.3 线性链表

--2.3 线性链表

--测试题

-2.4 静态链表

--2.4 静态链表

--测试题

-2.5 循环链表和双向链表

--2.5 循环链表和双向链表

--测试题

-第2章线性表讨论题

-数据结构第2章线性表PPT

第3章栈和队列

-3.1 栈

--测试题

-3.2 栈的实现

--3.2 栈的实现

--测试题

-3.3 栈的应用

--3.3 栈的应用

-3.4 栈与递归的实现

--3.4栈与递归的实现

--测试题

-3.5 队列和链队列

--3.5 队列和链队列

--测试题

-3.6 循环队列

--3.6 循环队列

--测试题

-第3章栈和队列讨论题

-数据结构第3章栈和队列PPT

第4章串

-4.1 串

--测试题

-数据结构第4章串PPT

第5章数组

-5.1 数组定义和表示

--5.1 数组定义和表示

--测试题

-5.2矩阵的压缩存储

--5.2 矩阵的压缩存储

--测试题

-第5章数组讨论题

-数据结构第5章数组PPT

第6章树和二叉树

-6.1 树的定义和基本术语

--6.1 树的定义和基本术语

-6.2 二叉树和二叉树的性质

--6.2 二叉树和二叉树的性质

--测试题

-6.3 二叉树的存储结构

--6.3二叉树的存储结构

--测试题

-6.4 遍历二叉树

--6.4 遍历二叉树（1）

--6.4 遍历二叉树（2）

--测试题

-6.5 线索二叉树

--6.5 线索二叉树

--测试题

-6.6 树的存储

--6.6树的存储

-6.7 树的转换和遍历

--6.7 树的转换和遍历

--测试题

-6.8 赫夫曼树

--6.8 赫夫曼树

-6.9 赫夫曼编码

--6.9 赫夫曼编码

--测试题

-第6章树和二叉树讨论题

-数据结构第6章树和二叉树PPT

第7章图

-7.1 图的定义和术语

--7.1.1图的定义和术语（1）

--7.1.2图的定义和术语（2）

--测试题

-7.2 图的存储结构

--7.2.1 数组表示法（1）

--7.2.2 数组表示法（2）

--7.2.3 邻接表

--测试题

-7.3 图的遍历

--7.3.1 深度优先搜索

--7.3.2 广度优先搜索

--测试题

-7.4 最小生成树

--7.4.1 普里姆算法

--7.4.2 克鲁斯卡尔算法

--测试题

-7.5 有向无环图

--7.5.1 拓扑排序

--7.5.2 关键路径

--测试题

-7.6 最短路径

--7.6.1 单源最短路径-迪杰斯特拉算法

--7.6.2 每一对顶点之间的最短路径-弗洛伊德算法

--测试题

-第7章图讨论题

-数据结构第7章图PPT

第8章查找

-8.1 查找基本概念和顺序查找

--8.1 查找基本概念及顺序查找

--测试题

-8.2 有序表的查找

--8.2 有序表的查找

--测试题

-8.3 二叉排序树

--8.3.1 二叉排序树（1）

--8.3.2 二叉排序树（2）

--测试题

-8.4 平衡二叉树

--8.4 平衡二叉树

--测试题

-8.5 哈希表

--8.5.1 哈希表及哈希函数的构造

--8.5.2 解决冲突的方法

--8.5.3 哈希表的查找和性能分析

--测试题

-第8章查找讨论题

-数据结构第8章查找PPT

第9章内部排序

-9.1插入排序

--9.1.1 插入排序（1）

--9.1.2 插入排序（2）

--测试题

-9.2 希尔排序

--9.2 希尔排序

--测试题

-9.3 快速排序

--9.3 快速排序

--测试题

-9.4 选择排序

--9.4 选择排序

--测试题

-9.5 堆排序

--9.5 堆排序

--测试题

-9.6 归并排序

--9.6 归并排序

--测试题

-9.7 基数排序

--9.7 基数排序

--测试题

-9.8 排序方法总结

--9.8 排序方法总结

-第9章内部排序讨论题

-数据结构第9章内部排序PPT

3.3 栈的应用笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航课程版权归原始院校所有，
本网站仅通过互联网进行慕课课程索引，不提供在线课程学习和视频，请同学们点击报名到课程提供网站进行学习。