当前课程知识点：数据结构（Data Structures） > 2. List > 2.10 Application of Stack > Video
返回《数据结构（Data Structures）》慕课在线视频课程列表
返回《数据结构（Data Structures）》慕课在线视频列表
在这节课中我们将学习到栈的应用
我们下面来通过一个实例
去解释栈的应用
这个例子是关于括号匹配的检测的
一个括号的字符串中
如果所有的括号都能够成对出现
那么我们就说这个字符串
它是一个平衡的括号字符串
否则我们就说这个字符串它是不平衡的
那下面我们要解决的问题就是说
要去写一段程序
去自动地判断输入的这个括号字符串
它是否是平衡的
为了去解决这个问题
我们下面来看一个具体的例子
这个例子我们可以从左往右
逐个检查字符串中的每一个括号
字符串中第一个括号
它是一个左括号
因为我们暂时无法判断后面哪个右括号
将会和这个左括号来匹配
所以我们先把这个左括号记录下来
然后我们又看到第二个也是左括号
同样我们还是无法确定
这个括号它的匹配的情况
因此我们同样把它记录下来
第三个还是左括号
我们也先把它给记录下来
这个时候我们已经记录了
三个没有匹配的左括号
第四个出现的是右括号
那么和这个右括号匹配的
应该是最后记录的那个左括号
所以我们将从记录的档案中
取出最后添加进去的左括号来进行匹配
在这里我们就可以看到
这个记录档案本身
它具有类似于栈的后进先出的性质
最后添加进去的将会最新给取出来
完全可以采用一个栈来去实现它
那么往里面添加左括号的过程
就是一个push的过程
而取出左括号的过程
就相当于一个pop的过程
明白了这个基本的原理之后
我们继续去处理剩下的括号
接下来是一个右括号
我们将会从栈中弹出一个左括号进行匹配
然后又遇到一个左括号
那么我们将把它加入到栈中去
接着是右括号
我们从栈中弹出左括号
最后也是一个右括号
我们继续从栈中弹出左括号
如果我们输入的是一个平衡的括号字符串
那么当我们运行结束的时候
这个栈应该是空的
也就是说不存在没有匹配成功的左括号
同时字符串中的括号
也必须全部处理完毕
不存在没有匹配的右括号
只有这两个条件都满足的时候
我们才说这个字符串
它是一个平衡的字符串
否则我们就说它是一个不平衡的字符串
下面我们来看一个不平衡的例子
类似于前面的处理过程
我们需要逐个去分析串中的括号
那么首先看到的是有两个左括号
我们把它们依次压入到栈中去
接着是一个右括号
那么我们将执行一次出栈的操作
这个时候字符串已经处理完了
但是栈它还不是空的
所以我们这个时候可以判断
这个字符串它是一个不平衡的字符串
通过以上这个例子
我们可以进一步地体验到
栈的后进先出的显著性质
而栈的应用往往也要立足于
这样的一种特殊的性质
好的 这节课我们就讲到这里
下节课我们再见
-1. Introduction--1.1 Introduction of Data
-1.1 Introduction of Data Structure
--Introduction of Data Structure
-1.2 Data Structure and A
-1.2 Data Structure and Algorithm
--Video
-1.3 Asymptotic Analysis
-1.3 Asymptotic Analysis
--Video
-1.4 Simplifying Rules of
-1.4 Simplifying Rules of Asymptotic Analysis
--Video
-2.1 Introduction of List
-2.1 Introduction of List
--Video
-2.2 Array based List
-2.2 Array based List
--Video
-2.3 Insertion Operation on Array
-2.3 Insertion Operation on Array based List
--Video
-2.4 Remove Operation on Array based List
-2.4 Remove Operation on Array based List
--Video
-2.5 Linked list
-2.5 Linked list
--Video
-2.6 Insertion Operation on Linked list
-2.6 Insertion Operation on Linked list
--Video
-2.7 Remove Operation on Linked list
-2.7 Remove Operation on Linked list
--Video
-2.8 SetPos Operation on Linked list
-2.8 SetPos Operation on Linked list
--Video
-2.9 Stack
-2.9 Stack
--Video
-2.10 Application of Stack
--Video
-2.11 Queue
-2.11 Queue
--Video
-3.1 Definition of Binary Tree
-3.1 Definition of Binary Tree
--Video
-3.2 Implementation of Binary Tree
-3.2 Implementation of Binary Tree
--Video
-3.3Traversal
-3.3 Traversal
--Video
-3.4 Binary Search Tree
-3.4 Binary Search Tree
--Video
-3.5 Search on BST
-3.5 Search on BST
--Video
-3.6 Insertion on BST
-3.6 Insertion on BST
--Video
-3.7 Introduction of Heap
-3.7 Introduction of Heap
--Video
-3.8 Construction of Heap
-3.8 Construction of Heap
--Video
-3.9 Operations on Heap
--Video
-3.10 General Tree
--Video
-4.1 Definition of Searching
--Video
-4.2 Searching of Sorted Array
-4.2 Searching of Sorted Array
--Video
-4.3 Definition of Hash Table
--Video
-4.4 Collision in Hash Table
-4.4 Collision in Hash Table
--Video
-4.5 Extension of Linear Probing
--Video
-4.6 Insertion Operation of Hash Table
--Video
-4.7 Search Operation of Hash Table
-4.7 Search Operation of Hash Table
--Video
-5.1 Introduction of Index
--Video
-5.2 Linear Index
-5.2 Linear Index
--Video
-5.3 2-3 tree index
-5.3 2-3 tree index
--Video
-5.4 Implementation of 2-3 tree
-5.4 Implementation of 2-3 tree
--Video
-5.5 B-Tree
-5.5 B-Tree
--Video
-5.6 Insertion Operation on B+ Tree
--Video
-5.7 Deletion Operation on B+ Tree
--Video
-6.1 Definition of Graph
--Video
-6.2 Implementation of Graph
--Video
-6.3 Adjacency Matrix
--Video
-6.4 Adjacency List
--Video
-6.5 Graph Traversal - DFS
--Video
-6.6 Graph Traversal - BFS
--Video
-6.7 Topological Sort
--Video
-6.8 Shortest Path Problem
--Video
-6.9 Single Source Shortest Path
--Video
-6.10 Dijkstra Algorithm
--Video
-7.1 Sorting Problem
--Video
-7.2 Insertion Sort
--Video
-7.3 Selection Sort
--Video
-7.4 Bubble Sort
--Video
-7.5 Shell Sort
--Video
-7.6 Quick Sort
--Video
-7.7 Heap Sort
--Video
-7.8 Comparison
--Video
