数据结构-第六讲 栈及括号匹配
1.栈的定义及相关概念
栈是这么定义的：
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
运算受限：也就是这个表你不能随便的删除插入。只能按照它的规则进行插入删除。比如栈就只能在一端进行插入和删除。同样，队列也是运算受限，只能在两头操作。
线性表：栈也是一种线性表，前面详细介绍过线性表，它表达的是一种数据的逻辑关系。也就是在栈内各个元素是相邻的。当然在具体实现上也分数组和链表实现，他们的物理存储结构不同。但是逻辑结构(实现的目的)相同。
栈顶栈底： 这个描述是偏向于逻辑上的内容，因为大家知道数组在末尾插入删除更容易，而单链表通常在头插入删除更容易。所以数组可以用末尾做栈顶，而链表可以头做栈顶。
栈的应用： 栈的应用广泛，比如你的程序执行查看调用堆栈、计算机四则加减运算、算法的非递归形式、括号匹配问题等等。所以栈也是必须掌握的一门数据结构。最简单大家都经历过，你拿一本书上下叠在一起，就是一个后进先出的过程，你可以把它看成一个栈。
2.栈的代码
老师的代码
分析：
1.初始化
2.push插入
3.入栈和出栈
4.提取top
5.测试
3.括号匹配问题
我的学习总结：
方法：
解决括号匹配问题最常见的方法是借助于栈这种数据结构。栈是一种先进后出（FILO）的线性表，它只允许在一端进行插入和删除操作。我们可以把栈想象成一摞盘子，只能从上面放盘子或者取盘子。栈有以下几种基本操作：
初始化栈：创建一个空栈，没有任何元素。压栈（push）：在栈顶插入一个元素，栈的长度增加一。弹栈（pop）：删除栈顶的元素，并返回它，栈的长度减少一。判断栈空（empty）：如果栈没有任何元素，返回真，否则返回假。判断栈满（full）：如果栈的长度达到了最大容量，返回真，否则返回假。栈顶元素（gettop）：返回栈顶的元素，但不删除它，栈的长度不变。
使用栈来解决括号匹配问题的算法思路如下：
初始化一个空栈，用来存放左括号。从左到右逐个字符扫描字符串，对于每个字符：
如果是左括号，就压入栈中。如果是右括号，就弹出栈顶元素，并判断它们是否匹配：
如果匹配，就继续扫描下一个字符。如果不匹配，就说明字符串不合法，结束算法。如果字符串扫描完毕，还要判断栈是否为空：
如果为空，就说明字符串合法，结束算法。如果不为空，就说明字符串不合法，结束算法。
我的代码 ：
激活谷谷主为您准备了激活教程，为节约您的时间请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/91199.html
