首页 > 代码库 > 数据结构_栈
数据结构_栈
栈是仅限在表尾进行插入和删除的线性表。因此对于栈来说，表尾端有着特殊的含义，叫栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。
栈又称为后进先出的线性表（LIFO）。
栈的应用举例。
1.数制转换(SDUTOJ2131)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
int main()
{
int n,r;
stack<int>sta;
cin>>n>>r;
while(n)
{
sta.push(n%r);
n/=r;
}
while(!sta.empty())
{
cout<<sta.top();
sta.pop();
}
return 0;
}
STL_stack简介
2.括号匹配(SDUTOJ2134)
#include<stdio.h>
#include<string.h>
int main()
{
char ch[10000],c;
char stk[10000];
int top,l,i;
while(gets(ch)!=NULL)
{
top=0;
i=0;
while((c=ch[i])!='\0')
{
i++;
l=0;
if(c=='(' || c=='{' || c=='[')
stk[top++]=c;
else if(c==']'&& (stk[top-1]=='(' || stk[top-1]=='{') )
{
l=1;
break;
}
else if(c=='}'&& (stk[top-1]=='(' || stk[top-1]=='[') )
{
l=1;
break;
}
else if(c==')'&& (stk[top-1]=='[' || stk[top-1]=='{') )
{
l=1;
break;
}
else if(c==')' || c=='}' || c==']')
{
if(top>=0)top--;
else
{
l=1;
break;
}
}
}
if(l==0&&top==0)printf("yes\n");
else printf("no\n");
}
}
3.行编辑程序(SDUTOJ1479)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
char s[100000];
int main()
{
int i,j;
char str[1000];
while(gets(str)!=NULL)
{
memset(s,0,sizeof(s));
int top=-1;
for(i=0;str[i]!='\0';i++)
{
if(str[i]!='#'&&str[i]!='@')
s[++top]=str[i];
else if(str[i]=='#')
{
if(top!=-1)
--top;
}
else if(str[i]=='@')
top=-1;
}
s[top+1]=0;
cout<<s<<endl;
}
return 0;
}4.迷宫求解(SDUTOJ2449)
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int mmap[10][10],vis[10][10],cnt,n,m;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void dfs(int s,int e)
{
if(s==n-1&&e==m-1)
{
cnt++;
return ;
}
for(int i=0;i<4;i++)
{
int x=s+dx[i];
int y=e+dy[i];
if(x>=0&&x<n&&y>=0&&y<m&&!vis[x][y]&&!mmap[x][y])
{
vis[x][y]=1;
dfs(x,y);
vis[x][y]=0;
}
}
}
int main()
{
int t,i,j;
cin>>t;
while(t--)
{
cnt=0;
memset(vis,0,sizeof(vis));
cin>>n>>m;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
cin>>mmap[i][j];
}
}
vis[0][0]=1;
dfs(0,0);
cout<<cnt<<endl;
}
return 0;
}
5.表达式求值(SDUTOJ2484)
把一个中缀表达式转换成后缀表达式：
从左到右依次从一个中缀式中读取一个字符
1、如果该字符为操作数，则立刻输出；
2、如果该字符为左括号‘(‘ 则立即将其压栈；
3、如果该字符为一个操作符：
3.1、如果栈为空，或者栈顶元素为左括号‘(‘，则立即将该操作符压栈；
3.2、如果栈顶操作符的优先级小于他自己，则立即将该操作符压栈；
3.3、如果栈顶操作符优先级大于等于自己，则先将栈顶元素出栈，继续判断与栈顶操作符的优先级，重复3.2和3.3操作；
4、如果该字符为右括号‘)‘，则依次从栈中弹出元素，直至栈为空或者弹出元素为左括号。
5、如果表达式遍历完毕，则依次出栈，直至栈空
把一个中缀表达式转换成前缀表达式：操作和转成后缀表达式一样，只是要先把中缀表达式反过来处理。如中缀表达式是a*b+(c-d/e)*f，处理顺序就是f*(e/d-c)+b*a
还有就是前面操作3.3大于等于改成大于就行了，因为顺序已经反过来了。
下面代码很乱，不建议看。。。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char str1[10000],sta[10000],str2[10000],ch[10000];
int t=0;
int tt(char c)
{
if(c=='('||c==')')
return 0;
else if(c=='+'||c=='-')
return 1;
else if(c=='*'||c=='/')
return 2;
}
void to(char *str)
{
int top=-1;
for(int i=0; str[i]!='\0'; i++)
{
if(str[i]=='#')
{
for(int j=top; j>=0; j--)
ch[t++]=sta[j];
ch[t]=0;
break;
}
if(str[i]>='a'&&str[i]<='z')
ch[t++]=str[i];
else if(str[i]=='(')
{
sta[++top]=str[i];
}
else if(str[i]==')')
{
for(int j=top; j>=0; j--)
{
if(sta[j]!='(')
ch[t++]=sta[j];
else
{
top=j-1;
break;
}
}
}
else
{
if(top==-1)
sta[++top]=str[i];
else
{
while(tt(str[i])<=tt(sta[top]))
{
ch[t++]=sta[top--];
}
sta[++top]=str[i];
}
}
}
}
void to2(char *str)
{
int top=-1;
for(int i=0; str[i]!='\0'; i++)
{
if(str[i]=='#')
{
for(int j=top; j>=0; j--)
ch[t++]=sta[j];
ch[t]=0;
break;
}
if(str[i]>='a'&&str[i]<='z')
ch[t++]=str[i];
else if(str[i]=='(')
{
sta[++top]=str[i];
}
else if(str[i]==')')
{
for(int j=top; j>=0; j--)
{
if(sta[j]!='(')
ch[t++]=sta[j];
else
{
top=j-1;
break;
}
}
}
else
{
if(top==-1)
sta[++top]=str[i];
else
{
while(tt(str[i])<tt(sta[top]))
{
ch[t++]=sta[top--];
}
sta[++top]=str[i];
}
}
}
}
int main()
{
cin>>str1;
memset(ch,0,sizeof(ch));
t=0;
int i,l=strlen(str1)-1,j;
for(i=0; str1[i]!='#'; i++)
{
if(str1[l-i-1]==')')
str2[i]='(';
else if(str1[l-i-1]=='(')
str2[i]=')';
else str2[i]=str1[l-i-1];
}
str2[i++]='#';
str2[i]=0;
to2(str2);
for(j=t-1;j>=0;j--)
printf("%c",ch[j]);
cout<<endl;
for(j=0;j<l;j++)
{
if(str1[j]!=')'&&str1[j]!='(')
printf("%c",str1[j]);
}
cout<<endl;
t=0;
memset(ch,0,sizeof(ch));
to(str1);
cout<<ch;
return 0;
}
//a+b*(c-d)-e/f#
//-+a*b-cd/ef
//abcd-*+ef/-
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。