本文共 10047 字，大约阅读时间需要 33 分钟。

学习视频：天勤考研 使用语言：c++

如果队栈和队列不是很清楚的，可以看一下这篇博客。

1.输出序列

1.入：1、2…、n,出:p1、p2…、pn。

若pi=n(1<i<n),则？

结论：pi>pi+1>…>pn。

因为pi=n，可得入栈已经完成，又因为1<i<n，所以可得到pi后面只有出栈操作。因为入栈的时候是从小到大入的栈，所以出栈一定是从大到小。所以可以得到上述结论。

2.入：1、2…、n,出:p1、p2…、pn。

若i<j<k,则pi、pj、pk的大小关系如何？

pi,pj,pk大小关系总共有这6种，3的全排列。 我们可以把i,j,k看成1,2,3,入栈数据看成1、2、3，所以出栈就是p1,p2,p3 1、2、3最多有6种出栈方式：

（1）1 2 3

（2）1 3 2

（3）2 1 3

（4）2 3 1

（5）3 1 2

（6）3 2 1

我们依次看他们的出栈是否能够完成

（1）1进，1出，2进，2出，3进，3出 （2）1进，1出，2进，3进，3出，2出 （3）1进，2进，2出，1出，3进，3出 （4）1进，2进，2出，3进，3出，1出 （5）显然不能成功 （6）1进，2进，3进，3出，2出，1出

第五种不成功，且大小关系为：pj<pk<pi

结论：大小关系不可能为pj<pk<pi

如果求有多少种出栈序列，可以使用卡特兰数来求。

3.卡特兰数（Catalan number）

Cn=(2n)!/[(n+1)!n!]

当n个数按照某种顺序入栈，并且可在任意时刻出栈，不同出栈序列的个数为Cn。

2.表达式转换的思路

三种表达式：中缀、前缀(运算符在前)、后缀(运算符符在后)。

运算符的优先级图表：

优先级的值越小的优先级越高。

1.中缀转前缀

第一步：根据运算符的优先级，把操作数和运算符之间的所有操作通过括号括起来。

第二步：把所有运算符都放到当前括号的前面。

第三步：去掉所有括号。

2.中缀转后缀

第一步：根据运算符的优先级，把操作数和运算符之间的所有操作通过括号括起来。

第二步：把所有运算符都放到当前括号的后面。

第三步：去掉所有括号

3.后缀转中缀

从前往后扫描，找到第一个运算符，然后把运算符放到操作数的中间，然后用括号括起来。然后依次进行同样的操作。最后把所有运算符操作完成，就把多余的括号去掉。

4.后缀转前缀

从前往后扫描，找到第一个运算符，然后把运算符放到操作数的前面，然后用括号括起来。然后依次进行同样的操作。最后把所有运算符操作完成，就把所有的括号去掉。

3.用栈来进行表达式之间的转换

1.中缀转后缀

注意条件：

1.栈存储的是运算符。所以遇到操作数直接把它写出来，遇到运算符才入栈。 2.扫描方向：从左往右。 3.运算符出栈的条件：(1)如果入栈运算符的优先级小于或等于栈顶（指当前运算符还未入栈时的栈顶）的优先级，则栈顶元素出栈。例如：栈顶元素为-，后一个进入元素为+，因为+与-优先级相同，则-号出栈，+号入栈。 （2）如果遇到左括号，则后面所有运算符都入栈，直到遇到右括号。当遇到右括号时，依次出栈运算符，直到遇到左括号。 4.扫描完成后，把栈中剩余运算符依次出栈。 代码：

#include 
   
    using namespace std;#define maxSize 10//优先级比较，这里我只进行了+，/，*，-,的比较，如果需要其他的，可自行设置int getPriority(char r){
       if(r=='+'||r=='-'){
           return 0;    }else if(r=='*'||r=='/'){
           return 2;    }else{
           return 1;    }}//中缀转后缀//infix为开始存储中缀数据的数组，s2为转换后的后缀数据数组，s1为一个栈void infixToPostFix(char infix[],char s2[],int &top2){
       char s1[maxSize];    int top1=-1;    int i=0;    //判断数据是否为空，以及扫描数组是否完成    while(infix[i]!='\0')    {
       	//a<=和<=z的原因是因为我这里传入的数据为a,b,c,d等，如果你传入数字，可去掉        if('a'<=infix[i]&&infix[i]<='z'||('0'<=infix[i]&&infix[i]<='9')){
               s2[++top2]=infix[i];            ++i;        }        else if(infix[i]=='('){
               s1[++top1]='(';            ++i;        }        else if(infix[i]=='+'||infix[i]=='-'||infix[i]=='*'||infix[i]=='/'){
               if(top1==-1||s1[top1]=='('||getPriority(infix[i])>getPriority(s1[top1])){
                   s1[++top1]=infix[i];                ++i;            }else{
                   s2[++top2]=s1[top1--];            }        }        else if(infix[i]==')'){
               while(s1[top1]!='('){
                   s2[++top2]=s1[top1--];            }            --top1; //防止把'('添加入栈。            ++i;        }    }	//扫描完成，清空栈里面的数据    while(top1 !=-1){
           s2[++top2]=s1[top1--];    }}int main(){
       char infix[20]={
   0};    char s2[20];    int top2=-1;        //字符串转化为字符数组    string name="a+b-a*((c+d)/e-f)+g";    strcpy(infix , name.c_str());        infixToPostFix(infix,s2,top2);        //字符数组转换为字符串    string name1;    name1=s2;    cout<
    
     <
    
   

结果：

2.中缀转前缀

注意条件：

1.栈存储的是运算符。所以遇到操作数直接把它写出来，遇到运算符才入栈。 2.扫描方向：从右往左。 3.运算符出栈的条件：(1)如果入栈运算符的优先级小于栈顶（指当前运算符还未入栈时的栈顶）的优先级，则栈顶元素出栈。例如：栈顶元素为*，后一个进入元素为-，因为-号的优先级小于栈顶*号的优先级，则*号出栈，-号入栈。 （2）如果遇到右括号，则后面所有运算符都入栈，直到遇到左括号。当遇到左括号时，依次出栈运算符，直到遇到右括号。 4.扫描完成后，把栈中剩余运算符依次出栈。

代码：

#include 
   
    using namespace std;#define maxSize 10//优先级判断int getPriority(char r){
       if(r=='+'||r=='-'){
           return 0;    }else if(r=='*'||r=='/'){
           return 2;    }else{
           return 1;    }}void infixToPostFix(char infix[],char s2[],int &top2){
       char s1[maxSize];    int top1=-1;    //判断infix数组字符个数    int i=strlen(infix)-1;    //当i<0时，扫描完成    while(i>=0)    {
           if('a'<=infix[i]&&infix[i]<='z'||('0'<=infix[i]&&infix[i]<='9')){
               s2[++top2]=infix[i];            --i;        }        else if(infix[i]==')'){
               s1[++top1]=')';            --i;        }        else if(infix[i]=='+'||infix[i]=='-'||infix[i]=='*'||infix[i]=='/'){
               if(top1==-1||s1[top1]==')'||getPriority(infix[i])>=getPriority(s1[top1])){
                   s1[++top1]=infix[i];                --i;            }else{
                   s2[++top2]=s1[top1--];            }        }        else if(infix[i]=='('){
               while(s1[top1]!=')'){
                   s2[++top2]=s1[top1--];            }            --top1;            --i;        }    }    while(top1 !=-1){
           s2[++top2]=s1[top1--];    }}int main(){
       char infix[20]={
   0};    char s2[20];    int top2=-1;        //字符串转字符数组    string name="a+b-a*((c+d)/e-f)+g";    strcpy(infix , name.c_str());        infixToPostFix(infix,s2,top2);        //字符数组转字符串    string name1;    name1=s2;		//字符串转置    reverse(name1.begin(),name1.end());    cout<
    
     <
    
   

结果：

3.后缀转前缀（前缀转后缀与它类似）

从左往右扫描，如果遇到运算符，则把操作数放到运算符的后面（前缀转后缀反之），因为运算符最多可以将两个操作数进行运算，然后把操作数和运算符结合当成一个操作数（例如：ab+,当遇到+运算符时，正好运算符前面有两个操作数a,b，所有把操作数放到运算符后面，得到+ab,可以把+ab看出一个操作数），把这个合成的操作数用于下一次操作，依次重复前面的操作，当所有的运算符扫描完成时，则可以得到我们需要的前缀表达式。

4.用栈进行表达式求值

1.中缀表达式求值

1.两个栈：一个存储操作数，一个存储运算符。

2.扫描方向：从左往右。 3.运算符出栈的条件：(1)如果入栈运算符的优先级小于或等于栈顶（指当前运算符还未入栈时的栈顶）的优先级，则栈顶元素出栈。例如：栈顶元素为-，后一个进入元素为+，因为+与-优先级相同，则-号出栈，+号入栈。 （2）如果遇到左括号，则后面所有运算符都入栈，直到遇到右括号。当遇到右括号时，依次出栈运算符，直到遇到左括号。 4.运算符出栈之后，将存储操作数的栈依次出栈两个操作数，然后通过运算符进行运算，然后存入操作数存储的栈。 5.当扫描完成之后，运算符栈依次出栈。每运算符栈出栈一个运算符，则操作数栈出栈两个操作数，然后运算存储到操作数栈。 6.当运算符栈为空，操作数栈的栈底的值，为中缀表达式求值之后的值。

代码：

#include 
   
    using namespace std;#define MIN 0.00001#define maxSize 10int getPriority(char op){
       if(op=='+'||op=='-')        return 0;    else         return 1;}int calSub(float opand1,char op,float opand2,float &result){
       if(op=='+')        result=opand1+opand2;    if(op=='-')        result=opand1-opand2;    if(op=='*')        result=opand1*opand2;    if(op=='/'){
           if(fabs(opand2)
    
     getPriority(s2[top2]))            {
                   s2[++top2]=exp[i];                ++i;            }            else{
                   float opand1,opand2,result;                char op;                int flag;                opand2=s1[top1--];                opand1=s1[top1--];                op=s2[top2--];                flag=calSub(opand1,op,opand2,result);                if(flag==0)                {
                       cout<<"errror"<
    
   

结果：

2.后缀表达式求值

1.一个栈：用来存储操作数。

2.扫描方向：从左往右。 3.当遇到运算符时，则从栈中出栈两个操作数，然后通过运算符进行运算，把运算结果放到栈中。依次进行重复操作。 4.扫描完成，栈底元素的值为所求后缀表达式的值。 代码：

#include 
   
    using namespace std;#define MIN 0.00001#define maxSize 10int getPriority(char op){
       if(op=='+'||op=='-')        return 0;    else         return 1;}int calSub(float opand1,char op,float opand2,float &result){
       if(op=='+')        result=opand1+opand2;    if(op=='-')        result=opand1-opand2;    if(op=='*')        result=opand1*opand2;    if(op=='/'){
           if(fabs(opand2)
   

结果：

3.前缀表达式求值

1.一个栈：用来存储操作数。

2.扫描方向：从右往左。 3.当遇到运算符时，则从栈中出栈两个操作数，然后通过运算符进行运算，把运算结果放到栈中。依次进行重复操作。 4.扫描完成，栈底元素的值为所求前缀表达式的值。 代码：

#include 
   
    using namespace std;#define MIN 0.00001#define maxSize 10int getPriority(char op){
       if(op=='+'||op=='-')        return 0;    else         return 1;}int calSub(float opand1,char op,float opand2,float &result){
       if(op=='+')        result=opand1+opand2;    if(op=='-')        result=opand1-opand2;    if(op=='*')        result=opand1*opand2;    if(op=='/'){
           if(fabs(opand2)
   

结果：

5.循环队列的配置问题

1.正常配置

1.当front==rear为真，队空

2.入队：rear=(rear+1)%maxSize;queue[rear]=x; 3.出队：front=(front+1)%maxSize;x=queue[front]; 4.队满：front=(rear+1)%maxSize为真 5.队内元素个数：(rear-front+maxSize)%maxSize;（把rear大于front和rear小于front两者情况合并了)

2.非正常配置

第一种非正常配置：改变入队出队条件

1.入队不同：queue[rear]=x;rear=(rear+1)%maxSize; 2.出队不同：x=queue[front];front=(front+1)%maxSize; 非正常配置导致： 队满时这种情况与正常配置的不同之处：非正常配置rear指向空，正常配置front指向空。

第二种非正常配置：改变队空条件：

队空状态发生改变，队空：front==(rear+1)%maxSize为真 非正常条件导致： 1.计算元素个数发生改变：(rear-front+1+maxSize)%maxSize;

2.队满条件发生改变：front==(rear+2)%maxSize为真。

6.双端队列

双端队列三种情况：正常、输入限制、输出限制。

正常：

输入受限： 输出受限：

1.不可能通过输入受限的双端队列输出的序列的是？

我们首先可以通过卡特兰数（关于卡特兰数输出序列那里有说）来求不可能序列的个数： 卡特兰数公式：Cn=(2n)!/[(n+1)!n!] 求出可能的序列数为：C4=14 求出不可能的序列数为：4!-14=10

通过如下方法依次求出可以首先的出队序列：

2.不可能通过输出受限的双端队列输出的序列的是？

我们首先可以通过卡特兰数（关于卡特兰数输出序列那里有说）来求不可能序列的个数：

卡特兰数公式：Cn=(2n)!/[(n+1)!n!] 求出可能的序列数为：C4=14 求出不可能的序列数为：4!-14=10

求法与上方相同。

7.栈的扩展

1.共享栈

共享栈产生的原因？

当top1栈栈满时，但是top2还有很多的多余的空间。

我们可以把两个栈共享一个内存空间。

这样的话，就可以使用多余的内存空间 共享栈的实现： 1.共享栈的出生化：int stack[maxSize];int top[2]={-1,maxSize}; 2.s1栈空：top[0]==-1为真时；s2栈空：top[1]==maxSize为真时。 3.s1入栈：stack[++top[0]]=x; s2入栈：stack[--top[1]]=x; 4.s1出栈：x=stack[top[0]--]; s2入栈：x=stack[top[1]++]; 5.栈满:top[0]+1==top[1]为真。

2.用栈模拟队列

思路：就是用两个栈来实现队列的操作，但是有可能是不能达到队列的效果，所有我们需要讨论哪些不能达到我们需要的效果。

和这道题思路类似的。 满足下列规则，才能实现栈模拟队列的操作。 用栈模拟队列的规则： 入队规则： 1.若s1未满，则元素直接入s1; 2.若s1满，s2空，则将s1中元素全部出栈并入s2,腾出位置后再入s1。

出队规则：

1.若s2不空，则从s2中元素直接出栈。 2.若s2空，则从s1中元素全部出栈并入s2，然后从s2中出栈。

队满:s1满且s2不空，则不能继续入队，即为队满状态。

8.括号匹配

1.括号问题

匹配:

不匹配:

用栈来实现思路：

通过从左到右依次扫描，当遇到相匹配的括号则出栈；扫描完成之后，当栈为空时，则证明括号匹配，当栈不为空时，则括号不匹配。 匹配规则：

int isMatched(char left,char right){
       if(left=='('&&right==')')        return 1;    else if(left=='['&&right==']')        return 1;    else if(left=='{'&&right=='}')        return 1;    else         return 0;}

总共代码：

#include
   
    using namespace std;#define maxSize 10int isMatched(char left,char right){
       if(left=='('&&right==')')        return 1;    else if(left=='['&&right==']')        return 1;    else if(left=='{'&&right=='}')        return 1;    else         return 0;}int isParenttheseBalanced(char exp[]){
       char s[maxSize];int top=-1;    for(int i=0;exp[i]!='\0';++i)    {
           if(exp[i]=='('||exp[i]=='['||exp[i]=='{')            s[++top]=exp[i];       else{
              if(top==-1)                return 0;            char left=s[top--];            if(isMatched(left,exp[i])==0){
                   return 0;            }       }    }    if(top>-1)        return 0;    return 1;}int main(){
       char exp[20]={
   };    string name="{[()]}";    strcpy(exp,name.c_str());    cout<
    
     <
    
   

结果：

2.计算问题

常见问题：

如果上面这个式子看不懂，可以看下面这个例题： 其实这题的思路就和递归很像，但是我们这里是用栈来实现的。 实现起来也比较简单。

int calF(int m){
   	int cum=1;	int s[maxSize],top=-1;	while(m!=0)	{
   		s[++top]=m;		m/=3; //这里是整数除法	}	while(top!=-1)		cum*=s[top--];	return cum;}

关于栈的考点总结完毕。

转载地址：http://sfezi.baihongyu.com/