stack-栈的学习笔记
栈是一种后进先出的数据结构(Last in First out LIFO),只能在一端进行插入和删除操作。
常见的用处:判断回文字符串,检验括号匹配
做过的题目:CDUT OJ 1143
借助栈判断回文字符串
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
char a[101],s[101];
int i,len,mid,next,top;
// 读入一行字符串
gets(a);
// 求字符串长度
len = strlen(a);
// 求字符串中点之前的位置(入栈终点)
mid = len / 2 - 1;
// 初始化栈
top = 0;
// 将mid前依次入栈
for(i = 0;i <= mid;i++)
s[++top] = a[i];
// 判断字符串长度是奇数还是偶数 找出需要进行匹配的起始下标
if(len % 2 == 0)
next = mid + 1;
else
next = mid + 2;
// 开始匹配
for(i = next;i <= len - 1;i++)
{
if(a[i] != s[top])
break;
top--;
}
// 若top为0说明全部匹配顺利循环结束
if(top == 0)
printf("YES");
else
printf("NO");
getchar();//利用getchar()函数让程序调试运行结束后等待编程者按下键盘才返回编辑界面
return 0;
}
借助栈实现括号匹配的检验
#include <iostream>
#include <stack>
#include <string>
using namespace std;
stack<char> mystack;
bool checksymbol = 1;
bool check(char a)
{
switch(a)
{
//左括号入栈
case '{':
mystack.push(a);
break;
case '(':
mystack.push(a);
break;
case '[':
mystack.push(a);
break;
//右括号与栈顶元素比较
//匹配 删除栈顶元素 不匹配 表达式括号有问题
case '}':
{
if(mystack.top() != '{')
checksymbol = 0;
else
mystack.pop();
break;
}
case ')':
{
if(mystack.top() != '(')
checksymbol = 0;
else
mystack.pop();
break;
}
case ']':
{
if(mystack.top() != '[')
checksymbol = 0;
else
mystack.pop();
break;
}
}
}
int main()
{
//给定需要判断的表达式
string s;
cin>>s;
//判断函数
int length = s.length();
for(int i = 0;i < length;i++)
{
check(s[i]);
}
//到最后栈为空 表达式括号没问题
if(!mystack.empty())//stack为空返回1 不空返回0
checksymbol = 0;
if(checksymbol == 1)
cout<<"YES";
else
cout<<"NO";
return 0;
}