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