算法初步——栈
2022/4/18 22:12:36
本文主要是介绍算法初步——栈,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
上一节中我们讲到了队列(没有看的小伙伴先去补补课:算法初步——队列 - Echo_sun - 博客园 (cnblogs.com)),它是一种十分先进的数据结构,遵循着先进先出的原则。在这一节,我们将要介绍一种后进先出的数据结构——栈。
栈和队列一样,也是一种特殊的线性表,它的特殊性在于:栈只能在一端进行插入和删除操作。就像博主比较喜欢吃桶装薯片,那么我们拿出来或放进去薯片只能在整桶薯片的最上面进行(貌似现在的桶装薯片为了减少分量,在里面加了一个塑料抽屉)。栈的实现也很简单,我们只需要一个一维数组和一个指向栈顶的变量top即可。我们通过对top的操作来实现对整个栈的插入和删除操作。
栈的应用有一个非常典型的例子——判断回文。(这里解释一下回文:例如“ababa”,”xxyyxx”都是回文字符串,所谓回文字符串就是指正读反读均相同的字符串。)通过栈,我们很容易就可以判断一个字符串是不是回文字符串。
首先,我们要读取字符串并求出该字符串的长度。
gets_s(a);//读入一行字符串
len = strlen(a);//求出字符串的长度
如果一个字符串是回文,那么它是关于中间对称的,我们需要求出它的中点:
mid = len / 2 - 1;//求出字符串的中间
接下来就轮到我们的栈大杀四方了。
首先我们将中点之前的字符入栈。
for (int i = 0; i <= mid; i++) { s[++top] = a[i]; }
接着我们就来到了最关键的地方,我们需要将栈里的字符进行出栈并于未入栈的字符进行匹配,如果都能匹配则说明该字符串为回文字符串,反之则不是。
for (int i = next; i < len;i++) { if (a[i] != s[top]) break; top--; } //如果top值为0,则说明所有的字符均被匹配完成 if (top == 0) cout << "YES" << endl; else cout << "NO" << endl;
完整代码如下:
#include<iostream> using namespace std; int main() { char a[101], s[101]; int len, mid, next; gets_s(a);//读入一行字符串 len = strlen(a);//求出字符串的长度 mid = len / 2 - 1;//求出字符串的中间 int top = 0;//栈的初始化 //我们将mid之前的字符全部入栈 for (int i = 0; i <= mid; i++) { s[++top] = a[i]; } //判断一下字符串的长度是奇数还是偶数,并找出需要进行字符匹配的起始下标 if (len % 2 == 0) next = mid + 1; else next = mid + 2; //开始匹配 for (int i = next; i < len;i++) { if (a[i] != s[top]) break; top--; } //如果top值为0,则说明所有的字符均被匹配完成 if (top == 0) cout << "YES" << endl; else cout << "NO" << endl; return 0; }
栈还可以被用来验证括号的匹配。我们编程过程中共需要用到三种括号:圆括号(),方括号[ ],花括号{ },编译器在进行编译时会检查括号是否匹配正确(相信大家都遇到过忘记写一个 } 导致报错的尴尬时刻。下面你们就可以动手为编译器写出一个验证括号匹配性的算法了。
这篇关于算法初步——栈的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)