栈：先进后出，后进先出

有固定存取规则的数组

栈相关的操作：

int s[20000];//创建一个栈

int b=0,t=0;//栈底，栈顶

   //栈底没有实际意义，栈顶指栈顶元素的下一个位置

s[t++]=5;//入栈

t--;//出栈

   //b~t-1 就是栈的实际存储空间下标范围

cout<<s[t-1];//输出栈顶

if(b==t) //判断栈空

栈相关的类型题：

   进制转换、括号匹配、车厢调度、表达式计算

1、利用栈的存储模式完成进制转换(十进制转R进制)

int n,r;

cin>>n>>r;

//创建栈

char s[20000]={};

int b=0,t=0;

char jz[]="0123456789abcdefghijklmnopqrst";

while(n){

   //余数入栈

   s[t++]=jz[n%r];

   n/=r;

}

//输出转换结果：出栈

while(!(b==t)){

   cout<<s[t-1];

   t--;

}

2、括号匹配问题【左入右出】

（1）单括号匹配

string s;

cin>>s;

//创建栈

char ss[1000];

int b=10,t=10;

bool f=false;

for(int i=0;i<s.size();i++){

   //左入，入栈

   if(s[i]=='('){

       ss[t++]=s[i];

   }

   //右出，出栈

   else if(s[i]==')'){

       //出栈失败，右括号失配，匹配失败

       if(b!=t) t--;

       else f=true,break;

   }

}

//栈非空，匹配失败

//栈空，匹配成功

if(t==b&&f==false) cout<<"YES";

else cout<<"NO";

（2）多括号匹配

string s;

cin>>s;

//创建栈

string z="([";

string y=")]";

char ss[1000];

int b=10,t=10;

bool f=false;

for(int i=0;i<s.size();i++){

   //左入，入栈

   if(s[i]=='('||s[i]=='['){

       ss[t++]=s[i];

   }

   //右出，出栈

   else if(s[i]==')'||s[i]==']'){

       //出栈失败，右括号失配，匹配失败

       if(b!=t&&z.find(ss[t-1])==y.find(s[i])) t--;

       else f=true,break;

   }

}

if()输出

（3）多括号分级匹配

string s;

cin>>s;

//创建栈

string z="<([{";

string y=">)]}";

char ss[1000];

int b=10,t=10;

bool f=false;

for(int i=0;i<s.size();i++){

   //左入，入栈

   if(z.find(s[i])<z.size()){

       if(b==t || z.find(ss[t-1])>=z.find(s[i])) ss[t++]=s[i];

       else f=true,break;

   }

   //右出，出栈

   else if(y.find(s[i])<y.size()){

       //出栈失败，右括号失配，匹配失败

       if(b!=t&&z.find(ss[t-1])==y.find(s[i])) t--;

       else f=true,break;

   }

}

if()输出

t=b;

f=false;

(3)车厢调度

作业：完成1357

下节课：stack包以及表达式计算