（1）本文大致包含：栈的定义，cpp中栈的常用函数，栈的应用（逆波兰表达式，汉诺塔，开关布线盒，离线等价类，火车重拍问题的栈解决方法，迷宫问题（包括BFS））

一些能用队列处理的问题这里也给出了解决方法，比如火车重排，迷宫问题。

本文中的样例均来自数据结构的黑书

关于栈的定义

栈是一个后进先出的数据结构（LIFO），具体形象化一下就类似羽毛球筒，最先放进去的往往是最后取出来的。递归时候函数的累加其实也是一种栈的堆叠，最后被调用的函数，往往是第一个被执行完毕的；

大多数语言中，栈都有自己的数据类型，不需要我们去手动构建（cpp中就有名为stack的类），根据性质，常用的函数其实只有

stack<int> s;
s.top();返回栈顶
s.pop();不返回东西，删除栈顶元素
s.push();往栈里面添加东西     //不同的语言会增加不同的函数，功能也封装了不少

栈的常见应用

（迷宫问题详见下方，单独整理出来了一个）

（1）逆波兰表达式：

逆波兰表达式可以用来把一个简单的算式处理成（后缀表达式），关于如何生成逆波兰表达式，以如何用逆波兰表达式进行计算，都需要栈进行处理：

（1）逆波兰表达式的实现：大致思路就是，遍历目标字符串的每一个字符，如果遍历得到的是数字，就存入s2栈中，如果得到的字符是计算符号，就要按优先级处理（*%/ > +-）括号特殊

如果当前读取到的字符，优先级小于s1栈顶的运算字符，就把s1当前的栈顶移动到s2（这个步骤可能重复多次）最后把读取到的字符填入s1

如果读取到的是左括号，直接存入s1,如果读入的是右括号，则在s1中所有左括号之上的运算符，都移动到s2，然后删除左括号

遍历完左右字符后，把s1中的字符都填入s2，s2在倒过来，就是逆波兰表达式了

（2）逆波兰表达式的计算：准备一个新的栈s3，如果读取到数字，就填入s3，如果读取到运算符，就进行（次栈顶）（运算符）（栈顶）的运算，并把计算结果存入栈中，最后栈剩下的最后一个元素就是我们要的结果

cpp代码实现：

//普通的栈利用还是最简单的逆波兰表达式比较靠谱一点点，局限是单个的字符。。。。
void nbl(string str){
    stack<char> s1;
    stack<char> s2;
    for(int i=0;i<=str.length()-1;i++){
        if(str[i]<='9'&&str[i]>='0'){
            s2.push(str[i]);
        }else{
            if(str[i]=='('){
                s1.push(str[i]);
            }else if(str[i]=='*'||str[i]=='/'||str[i]=='%'){
                if(!s1.empty()&&(s1.top()=='*'||s1.top()=='/'||s1.top()=='%')){
                    s2.push(s1.top());
                    s1.pop();
                }
                s1.push(str[i]);
            }else if(str[i]=='+'||str[i]=='-'){
                while(!s1.empty()&&(s1.top()=='*'||s1.top()=='/'||s1.top()=='%'||s1.top()=='+'||s1.top()=='-')){
                    s2.push(s1.top());
                    s1.pop();
                }
                s1.push(str[i]);
            }else if(str[i]==')'){
                while(s1.top()!='('){
                    s2.push(s1.top());
                    s1.pop();
                }
            }
        }
    }
   while(!s1.empty()){
       s2.push(s1.top());
       s1.pop();
   }
   //得到这个逆波兰表达式以后的计算方式为:
   string target="";
   while(!s2.empty()){
       target=s2.top()+target;s2.pop();
   }
   stack<int> s3;
   for(int i=0;i<=target.length()-1;i++){
       if(target[i]<='9'&&target[i]>='0'){
           s3.push(target[i]-48);
       }else{
           int a=s3.top();s3.pop();
           int b=s3.top();s3.pop();
           if(target[i]=='+'){
               s3.push(b+a);
           }else if(target[i]=='-'){
               s3.push(b-a);
           }else if(target[i]=='*'){
               s3.push(b*a);
           }else if(target[i]=='/'){
               s3.push(b/a);
           }else if(target[i]=='%'){
               s3.push(b%a);
           }
       }
   }
   cout<<s3.top();
}

2.关于汉诺塔，就是简单的递归处理

代码实现如下：

//汉诺塔；处理原理就是递归楼,大致明白了，但是深究还是出问题
void hano(int n,int start,int temp,int end){
    if(n==1){
        cout<<start<<"-->"<<end<<endl;
    }else{
        hano(n-1,start,end,temp);
        cout<<start<<"-->"<<end<<endl;
        hano(n-1,temp,end,start);
    }
};
//除此之外，汉诺塔也可以使用栈的方式进行处理，不过本质上是一模一样的，只不过是把输出文字的部分具象化成栈了而已

3.关于火车重排问题：

火车重拍问题就真的很恶心，，，我指的是实现的这方面。

火车重排的思路大致就是：有一个输入端，n个缓冲数组，一个输出端

//火车重排问题，其实就是对栈的简单应用，以后有需要的时候再进行实现
//火车重拍问题有个问题就是，不同的队列需要不同的缓冲轨道，例如581742963需要三条，198765432就需要9条

//大致的逻辑就是:如果当前输入铁轨的火车能直接输出，就先输出，然后判断一下缓冲铁轨里面最小的车符不符合条件
//如果缓冲铁轨里面的车符合条件，对应的缓冲铁轨就弹出这个车，然后输出，同时在缓冲铁轨里面寻找最小的车和所在的栈；

//如果当前输入铁轨不能直接输出的时候，就考虑把这个车存进缓冲和铁轨里面：
//挨个寻找缓冲铁轨（1）寻找所有栈顶大于当前车的栈中，栈顶最小的一个，往这里存入
                //（2）如果栈是空的，也可以直接用
                //再然后判断一下，新输入的这个车在缓冲铁轨中是不是最小
                //如果是，就更新一下最小的缓冲铁轨序号和最小的车
int nextOfCar;              //输出铁轨里面需要的下一个车
int smallestCar;            //缓冲铁轨中最小的车
stack<int>* arrStack;      //缓冲铁轨数组
int isTrack;               //最小车所在的缓冲铁轨
void trainSort(int inputOrder[],int numberOfTrack,int numberOfCar){
    nextOfCar=1;
    smallestCar=numberOfCar+1;
    arrStack=new stack<int>[numberOfTrack+1];
    for(int i=numberOfCar-1;i>=0;i--){
        if(inputOrder[i]==numberOfCar){
            nextOfCar++;//这里++就代表已经把这个小车扔进输出端了
            while(smallestCar==nextOfCar){
                //先把当前这个最小的车厢给扔出去
                arrStack[isTrack].pop();
                //重新寻找下一个smallest
                for(int x=1;x<=numberOfTrack;x++){
                    if(arrStack[i].size()!=0&&arrStack[i].top()<smallestCar){
                        smallestCar=arrStack[i].top();//找到最小车厢的编号
                        isTrack=i;                   //找到最小车厢所在的缓冲铁轨
                    }
                }
                //等待目标更新
                nextOfCar++;
            }
        }else{
            int MinTop=numberOfCar+1;
            int UsefulTrack=0;
            for(int x=1;x<=numberOfTrack;x++){
                if(!arrStack[x].empty()){//如果铁轨非空，就寻找一下符合搜索条件的铁轨
                    if(inputOrder[i]<arrStack[x].top()&&arrStack[x].top()<MinTop){
                        UsefulTrack=x;
                        MinTop=arrStack[x].top();
                    }
                }else{
                    UsefulTrack=x;//如果铁轨是空的，就直接用空的铁轨就行
                }
            }

            if(UsefulTrack==0){
                return;//代表没有有效的缓冲铁轨，可以尝试增加铁轨的数目
            }else{
                arrStack[UsefulTrack].push(inputOrder[i]);
            }

            if(inputOrder[i]<smallestCar){//如果刚进入缓冲铁轨的车是最小的
                smallestCar=inputOrder[i];  //那么就更新一下最小车号，和最小车所在的缓冲铁轨；
                isTrack=UsefulTrack;
            }
        }
    }
}

两种方法的对比

//关于列车重拍问题的两种实现：
//列车重拍问题的本质是，如果输入铁轨上的下一个符合输出要求，就直接输出
//如果输入铁轨不符合要求，把缓冲铁轨里面的东西都输入进来
//然后再把输入铁轨的东西存到缓冲铁轨里面
//难点一：缓冲数组的数目，缓冲数组的数目不是固定的，也没有公式能计算
//难点二；读取顺序，先看输入铁轨行不行，如果输入就把输入铁轨的内容直接进入输出铁轨即可,然后检查一下缓冲铁轨的最小值，如果合适就存进来
//如果输入铁轨不行，就直接想办法存入
//难点三，存入缓冲铁轨，找到所有大于存入目标的最小位置或者空栈;

//其实这个实现本质上不难，难就难在变量太多了不好整理。。。
void rainStack(int arrTrain[],int numOfTrain ,int numOfTrack){
    stack<int> *Tracks=new stack<int>[numOfTrack+1];
    int MinTrain;//缓冲铁轨中最小的一个
    int MinTrack;//缓冲铁轨中最小一个的所在位置
    int NextNeedTrain=1;
    for(int i=0;i<numOfTrain;i++){
        if(arrTrain[i]==NextNeedTrain){
            NextNeedTrain++;
            while(MinTrain==NextNeedTrain){
                NextNeedTrain++;
                Tracks[MinTrack].pop();
                MinTrain=114514;
                for(int x=1;x<=numOfTrack;x++){
                    if(!Tracks[x].empty()&&Tracks[x].top()<MinTrain){
                        MinTrain=Tracks[x].top();
                        MinTrack=x;
                    }
                }
            }
        }else{
            //寻找符合条件的缓冲铁轨
            int Min=0;
            int MinNum=114514;
            for(int x=1;x<=numOfTrack;x++){
                if(!Tracks[x].empty()){
                    if(Tracks[x].top()>=arrTrain[i]&&Tracks[x].top()>MinNum){
                        Min=x;
                        MinNum=Tracks[x].top();
                    }
                }else{//检测到轨道为空直接用即可
                    Min=x;
                }
            }
            //存入合适的缓冲铁轨
            if(Min!=0){
                Tracks[Min].push(arrTrain[i]);
            }else{
                cout<<"没有找到合适的缓冲铁轨"<<endl;
                return;
            }
            //观察一下是否需要更新一下最小铁轨
            if(arrTrain[i]<MinTrain){
                MinTrack=Min;
                MinTrain=arrTrain[i];
            }
        }
    }
}


//列车重拍问题的队列实现如下：
//用队列实现的话本质上应该和上面是差不多的，区别就在于缓冲数组的填入和调用
//缓冲数组的调用为：选择头部最小的位置然后输出
//缓冲数组的填入为：选择队尾小于输入值中最大的一个，然后进行填充
void rainQueue(int arrTrain[],int numOfTrain ,int numOfTrack){
    queue<int> *Tracks=new queue<int>[numOfTrack+1];
    int MinTrain;//缓冲铁轨中，队首最小的一个
    int MinTrack;//缓冲铁轨中，队首一个的所在位置
    int NextNeedTrain=1;
    for(int i=0;i<numOfTrain;i++){
        if(arrTrain[i]==NextNeedTrain){
            NextNeedTrain++;
            while(MinTrain==NextNeedTrain){
                NextNeedTrain++;
                Tracks[MinTrack].pop();
                MinTrain=114514;
                for(int x=1;x<=numOfTrack;x++){
                    if(!Tracks[x].empty()&&Tracks[x].front()<MinTrain){
                        MinTrain=Tracks[x].front();
                        MinTrack=x;
                    }
                }
            }
        }else{
            //寻找符合条件的缓冲铁轨
            int Max=0;
            int MaxNum=-1;
            for(int x=1;x<=numOfTrack;x++){
                if(!Tracks[x].empty()){
                    if(Tracks[x].back()<=arrTrain[i]&&Tracks[x].back()>MaxNum){
                        Max=x;
                        MaxNum=Tracks[x].back();
                    }
                }else{//检测到轨道为空直接用即可
                    Max=x;
                }
            }
            //存入合适的缓冲铁轨
            if(Max!=0){
                Tracks[Max].push(arrTrain[i]);
            }else{
                cout<<"没有找到合适的缓冲铁轨"<<endl;
                return;
            }
            //尾部插入应该是不影响这里，就算是插入了空的队列，这里也能检测得到是否是最小的
            if(arrTrain[i]<MinTrain){
                MinTrack=Max;
                MinTrain=arrTrain[i];
            }
        }
    }
}

4.关于开关布线盒

开关布线盒的问题详见书上是怎么描述的，其实这东西在本质上入栈，出栈的操作和leetcode15括号匹配，后缀表达式计算是一样的

5.关于离线等价类问题

 离线等价类的储存方法

{1}[2,5]
{2}[1]
{4}[3]
{3}[4]
{5}[1]

表述出来就是{1，2，5}是一类
{3，4}是一类，，，，，，这个储存方法和邻接表存储矩阵一模一样

离线等价类的读取方法这里也用文字描述了

循环遍历每个数字：在每次循环中，如果当前数字没有被走过（visited数组又来了），存入栈，然后这点标记走过。紧接着，用while不断判断栈是否为空。

如果栈不为空， 输出栈顶，然后把弹出栈顶的所有没走过的子代都存进来

。。。。这么一看用队列也行，就类似BFS搜索的时候那个队列操作

迷宫问题（↓）

迷宫问题从大一就开始折磨我了。。。。。

其实最开始的，寻找路径问题就是dfs的抽象操作，当时还叫递归来着

不过现在我们的需求是获得最短的路径（假设只有唯一一种最短的路径，多种最短路径的问题我们后续有机会再处理）

如代码所示，我们遇到这样一个迷宫

（下面的代码都默认3，3为终点）

//迷宫的代码如下
int MG[4][4]={
        {0,1,0,0},
        {0,0,0,0},
        {0,1,1,0},
        {0,0,1,0}
};

利用DFS获得迷宫的最短路径：

dfs获取最短路径的思路为：

首先创建一个path的数组，可以记录走过的路径，也方便我们进行回溯

预设Min数值，从来储存和比较最小的步数，一开始设为一个很大的常数

预设shortPath数组，用来存储最短的路径，同时也方便更新（存在意义，平时寻找最大最小值的时候设置的min和max是一样的，你细品一下。。。）

代码逻辑：

如果当前这个点（x,y）还没到终点，就标记这个点已经走到了

然后开始尝试四个方向继续深度寻找

找完这四个方向（四个方向的深度路径都探索过了）以后，把（x，y）点恢复成没有走到的情况，防止其他可行路线在这里被堵住

一旦这个点走到了终点，那么就代表step代表走过的步数，path里面存着一个能到达终点的路径

比较Min和step，然后判断是否要更新shortPath和Min

代码实现如下

其中DFS的最短原理是通过深度，寻找到每一个能到达终点的路径，然后比较着选出最短的一条路径

//关于dfs寻找迷宫最短路径的方法
int Min=100;
pair<int,int>* path[100];
pair<int,int>* shortPath[100];
void dfs(int x,int y,int step){
    path[step]=new pair<int,int>;
    path[step]->first=x;
    path[step]->second=y;
    cout<<x<<y<<endl;
    if(x==3&&y==3){//到达终点的情况
        if(step<Min){
            Min=step;
            for(int i=1;i<=step;i++){
                shortPath[i]=path[i];//保存一下最短路径
            }
        }
    }else{
        MG[x][y]=1;
        if(x+1<=3&&MG[x+1][y]==0){
            dfs(x+1,y,step+1);
        }
        if(x-1>=0&&MG[x-1][y]==0){
            dfs(x-1,y,step+1);
        }
        if(y+1<=3&&MG[x][y+1]==0){
            dfs(x,y+1,step+1);
        }
        if(y-1>=0&&MG[x][y-1]==0){
            dfs(x,y-1,step+1);
        }
        MG[x][y]=0;//恢复一下，是为了防止阻碍其他最短的情况
    }
}

//short里面就存在着一个长度为MIn的路径
//调用操作为dfs（0，0，1）

BFS实现迷宫问题的方法：

BFS的最短原理其实和自身的性质有关

BFS在迷宫中的应用就是，每次把身边的点都存进来，逐步蚕食（具体参考世界盒子游戏中的孢子生物的增值方式，只要碰到终点，就一定是一个最短的距离，这是一个特性）

关于如何获取最短路径：在每次走到一个点的时候，单独开一个数组储存每个点的来源是哪个点，最短路径寻找完毕后，直接顺着往上找即可

关于实现的逻辑为：

建立vis数组（用来储存某个点是否可以通行，初始和迷宫数组一样）只要进了队列就要标记走过，否则会出现重复存入队列的情况

建立pre数组，用来指向这个点的源头/父点

建立len数组，储存到每个点的长度，每个点的长度都是父点+1

具体代码示例如下，核心还是bfs操作

//下面是bfs的实现方法
//bfs的特点就是每个点只需要走一次
//下面这个矩阵是判断能否走过这个点
//这里不用pair数据类型了
class point{
public:
    int first;
    int second;
    point(){};//方便初始化
    point(int first, int second) : first(first), second(second) {}
};
int vis[4][4]={
        {0,1,0,0},
        {0,0,0,0},
        {0,1,1,0},
        {0,0,1,0}
};
int len[4][4]={
        {0,1,0,0},
        {0,0,0,0},
        {0,1,1,0},
        {0,0,1,0}
};
point pre[4][4];

void bfs(){
    queue<point> q;//引入一个队列
    q.push(point(0,0));
    vis[0][0]=1;
    while(!q.empty()){
        point temp=q.front();q.pop();
        int x=temp.first;int y=temp.second;
        vis[x][y]=1;
        //下面把每个点都扫入进来
        if(x+1<=3&&vis[x+1][y]==0){
            len[x+1][y]=len[x][y]+1;
            pre[x+1][y]=temp;
            q.push(point(x+1,y));
            vis[x+1][y]=1;//这个点已经不能走了
        }
        if(x-1>=0&&vis[x-1][y]==0){
            len[x-1][y]=len[x][y]+1;
            pre[x-1][y]=temp;
            q.push(point(x-1,y));
            vis[x-1][y]=1;//这个点已经不能走了
        }
        if(y+1<=3&&vis[x][y+1]==0){
            len[x][y+1]=len[x][y]+1;
            pre[x][y+1]=temp;
            q.push(point(x,y+1));
            vis[x][y+1]=1;//这个点已经不能走了
        }
        if(y-1>=0&&vis[x][y-1]==0){
            len[x][y-1]=len[x][y]+1;
            pre[x][y-1]=temp;
            q.push(point(x,y-1));
            vis[x][y-1]=1;//这个点已经不能走了
        }
    }
//下面这部分是追溯操作
    int x=3;
    int y=3;
    while(x!=0||y!=0){
        cout<<x<<y<<endl;
        int nx=pre[x][y].first;
        int ny=pre[x][y].second;
        x=nx;y=ny;
    }
    cout<<0<<""<<0<<endl;
};

这两种算法的总结

DFS深度寻找所有的可能性，然后比较出一个结果

BFS根据蚕食策略，找到所有的点，然后得到一个结果

DFS可以更直观地得到路径，而BFS似乎更倾向于得到每个点的最短距离

嘛。。不过该能做到的都能做到，只不过实现方法不同罢了

关于迷宫的所有走法：

想得到迷宫的所有走法我们可以借用DFS，每一次走到path都会得到一个path数组，这其实就是其中一种情况，最短路径就是从这里面挑一一种

int MG2[4][4]={
        {0,1,0,0},
        {0,0,0,0},
        {0,1,1,0},
        {0,0,1,0}
};
void allMG(int x,int y,int step){
    if(x==3&&y==3){//一旦到达终点就输出迷宫
        MG2[x][y]=7;
        for(int i=0;i<=3;i++){
            for(int j=0;j<=3;j++){
                cout<<MG2[i][j];
            }
            cout<<endl;
        }
        MG2[x][y]=0;
        cout<<"请输入任意键得到下一个迷宫"<<endl;
        system("pause");
    }else{
        MG2[x][y]=7;
        if(x+1<=3&&MG2[x+1][y]==0){
            allMG(x+1,y,step+1);
        }
        if(x-1>=0&&MG2[x-1][y]==0){
            allMG(x-1,y,step+1);
        }
        if(y+1<=3&&MG2[x][y+1]==0){
            allMG(x,y+1,step+1);
        }
        if(y-1>=0&&MG2[x][y-1]==0){
            allMG(x,y-1,step+1);
        }
        MG2[x][y]=0;
    }
}

判断迷宫是否有通路的方法

（1）最简单纯粹的递归

//最后一个判断迷宫的可行性/从某个点触发能否到达终点
//1.可以用BFS把迷宫扫一遍，看看能否扫到最后一个位置，这应该是性能比较好的方法
//2.用递归的方法
bool isPass(int MG[4][4],int x,int y){
   if(x==3&y==3){
       return true;
   }else if(x<0||x>3||y<0||y>3){
       return false;
   }else if(MG[x][y]!=0){
       return false;
   }else{
       MG[x][y]=1;//注意这里的关键步骤
       bool a=isPass(MG,x+1,y)||isPass(MG,x-1,y)||isPass(MG,x,y+1)||isPass(MG,x,y-1);
       MG[x][y]=0;
       return a;
   }
}

（2）寻路递归

bool oneMG(int x,int y){
    if(x==3&&y==3){
        MG[x][y]=7;
        return true;
    }else{
        if(x<0||x>3||y<0||y>3){
            return false;
        }else if(MG[x][y]!=0){
            return false;
        }else{
            MG[x][y]=2;//问题就出在这里。。。。。。
            if(oneMG(x+1,y)){
                MG[x][y]=7;
                return true;
            }else if(oneMG(x-1,y)){
                MG[x][y]=7;
                return true;
            }else if(oneMG(x,y+1)){
                MG[x][y]=7;
                return true;
            }else if(oneMG(x,y-1)){
                MG[x][y]=7;
                return true;
            }else{
                return false;
            }
        }
    }
}

//利用递归求解迷宫的时候，一定要把走过的路线标记上，不然很容易发生溢出栈
//走过记得标记，完成所需要的递归后看情况，是否要进行清除操作

注意就是递归的时候，走过的地方要标记一下，防止发生咬合现象导致溢出栈