简介
啦啦啦，小葵花妈妈课堂开课啦！为什么我队栈老是用不好？多半是因为你没看这篇文章~ 那么，这篇文章，我们就一起来说说C++ STL中的队与栈，大致分位2部分：
- 第一部分：相关容器的编程API
- 第二部分：栈的应用：末日迷宫
作为容器适配器，栈和队列在许多算法中都发挥着不可替代的作用！！！
栈和队列的相关代码已经托管到Github上了~我是代码，快点我
容器的使用
stack
stack的特点是后进先出，常用与逆序、保存历史等~ 广泛应用于以递归为代表的算法中！
常用API:
void TestStack()
{
stack<int> s;
s.push(1);
s.push(3);
s.push(4);
while(!s.empty())
{
cout<<s.top()<<endl;
s.pop();
}
}
### queue
queue特点是后进先出，向我们平常的排队一样，从队首进，队尾出，广泛应用于以宽度优先搜索为代表的算法中！
常用API：
void TestQueue()
{
queue<int> q;
q.push(1);
q.push(3);
q.push(4);
while(!q.empty())
{
cout<<q.front()<<endl;
q.pop();
}
}
priority_queue
priority_queue 优先队列，相比queue相比，更符合我们的实际“插队”，优先级高的拥有插队特权！ 当然优先级高低是我们自己定义的，我们乐意谁优先级高，就可以让他插队！
常用API：
class compare
{
public:
bool operator()(int a,int b)//自定义优先级算法
{
return a<b;
}
};
void TestPriorityQueue()
{
//容器可以是 vector, deque 等数组形，但不能用 list. 比较方式可以为less<T> 或者greater<T>
//STL里面容器默认用的是 vector. 比较方式默认用 operator< 即队头元素最大。
priority_queue<int, vector<int>, compare > q;
q.push(1);
q.push(3);
q.push(4);
while(!q.empty())
{
//不用front，使用top
cout<<q.top()<<endl;
q.pop();
}
}
末日迷宫
接下来，我们讨论一个迷宫寻径的算法，
为什么叫“末日迷宫”呢？说来话长，话说在2012年世界末日的时候，程序猿小明突发奇想，要用C++破解迷宫！所以呢就叫末日迷宫啦！
好了，扯犊子玩了，来看看算法：
条件：10*10迷宫，用矩阵表示，1表示墙，0表示路，已知入口和出口的坐标，就路径！
基本思想： 迷宫问题，就是要不断地试错，重点是遇到错误之后，要能够返回，所以呢我们就用stack保存路径， 采用暴力破解法，当到一个新的点之后，依次：下、左、上、右，进行试错，全部错误即为死胡同， 对已经确认为死胡同的路，我们要标记，防止以后再走， 对于走过的路，我们也要标记，防止重复绕圈！
源码及结构体如下：
typedef struct ways //路径上的点
{
int x;
int y;
int dir;
}ways;
typedef struct maze
{
vector<vector<int> > M;
ways in;
ways out;
int n;//迷宫纬度
maze():M(10,vector<int>(10,0)),n(10){};
}maze;
void initmaze(maze &m)
{
int n =m.n;
m.in.x=1;
m.in.y=0;
m.out.x=8;
m.out.y=9;
for(int i=0;i<n*n;i++)
{
if(i/n==0||i/n==9||i%n==0||i%n==9)
m.M[i/n][i%n]=1;
}
m.M[1][3]=1;
m.M[1][7]=1;
m.M[2][3]=1;
m.M[2][7]=1;
m.M[3][5]=1;
m.M[3][6]=1;
m.M[4][2]=1;
m.M[4][3]=1;
m.M[4][4]=1;
m.M[5][4]=1;
m.M[6][2]=1;
m.M[6][6]=1;
m.M[7][2]=1;
m.M[7][3]=1;
m.M[7][4]=1;
m.M[7][6]=1;
m.M[7][7]=1;
m.M[8][1]=1;
m.M[m.in.x][m.in.y]=0;
m.M[m.out.x][m.out.y]=0;
}
void printway(maze &m,vector<vector<int> > &v) //可视化显示
{
for(int i=0;i<(m.n*m.n);i++)
{
if(v[i/m.n][i%m.n]==2)
cout<<".";
else if(m.M[i/m.n][i%m.n]==0)
cout<<" ";
else if(m.M[i/m.n][i%m.n]==1)
cout<<"#";
if((i%m.n)==(m.n-1))cout<<endl;
}
}
void findWay(maze &m) //核心算法
{
stack<ways> s;
vector<vector<int> > status(m.M);
ways nowloc={1,0,0};
s.push(nowloc);
while((!s.empty())&&(nowloc.x!=m.out.x||nowloc.y!=m.out.y))
{
nowloc = s.top();
if(nowloc.x<0||nowloc.y<0||status[nowloc.x][nowloc.y]==1)//点不可行
{
s.pop();
continue;
}
if(nowloc.dir<4) // 下一方向
{
s.top().dir++;
status[nowloc.x][nowloc.y]=2;
if(nowloc.dir==0)
nowloc.x++;
else if(nowloc.dir==1)
nowloc.y--;
else if(nowloc.dir==2)
nowloc.x--;
else if(nowloc.dir==3)
nowloc.y++;
if(status[nowloc.x][nowloc.y]!=2)// 如果是轨迹上的点，忽略
{
nowloc.dir=0;
s.push(nowloc);
}
}
else //死胡同
{
s.pop();
status[nowloc.x][nowloc.y]=1;
}
}
if(s.empty())
{
cout<<"该迷宫无解！！！"<<endl;
}
else
printway(m,status);
}
//末日迷宫
void outMaze()
{
maze m;
initmaze(m);
findWay(m);
}
迷宫寻径运行结果：
总结
栈和队列是对线性表的封装，虽然看上去很简单，但是 这些提供的特殊访问方式，在后面复杂结构体的算法实现中具有不可替代的作用！