栈是数据结构中一种重要的线性结构，限定仅在表尾进行插入和删除操作的线性表，因此我们也可以认为它是一种特殊的线性表。由于栈的这个特点，我们又可以称其为后进先出的结构。如图所示：

由于栈具有后进先出的性质我们可以利用，是程序设计中一个有用的工具。利用栈我们可以来实现数制转换、后缀表达式求值、迷宫求解等等。在书本上我们可以看到用C语言实现的简单思路，但是程序仍旧存在许多bug。今天，我想尝试用强大的C++来实现。

迷宫问题的求解思路大致则是从入口出发，顺着某一方向向前探索，若能走通，则继续向前探索；若不能走通，则换一方向进行探索，直至所有可能的通路都探索完为止。利用栈的特性，我们可以将探索过可通的路依次进栈，如果遇到不通的路则进行出栈操作，进行回退，重复探索。

ps：为了方便起见我利用了一个记事本来存放迷宫，用1表示不通，0表示通路。将走过的路程标注为2.

代码实现：

structPos//可通过下标访问位置{int_ROW;int_COL;};voidGetMaze(int*a,intn)//从文件中读出迷宫地图{FILE*fout=fopen("Maze.txt","r");assert(fout);for(inti=0;i<n;i++){for(intj=0;j<n;){charch=fgetc(fout);if(ch=='0'||ch=='1'){a[i*n+j]=ch-'0';++j;}else{continue;}}}fclose(fout);}boolCheckIsAccess(int*a,intn,Posnext)//检查是否为通路{assert(a);if((next._ROW>=0)&&(next._ROW<n)&&(next._COL>=0)&&(next._COL<n)&&(a[next._ROW*n+next._COL]==0)){returntrue;}else{returnfalse;}}boolMazePath(int*a,intn,Pos&entry,stack<Pos>&path)//探索过程{Poscur=entry;path.push(cur);while(!path.empty()){Posnext=cur;a[cur._ROW*n+cur._COL]=2;if(next._ROW==n-1)/*||next._ROW==0||next._COL==n-1||next._COL==0*/{returntrue;}//判断上下左右是否为通路next=cur;next._ROW--;//上if(CheckIsAccess(a,n,next)){cur=next;path.push(cur);continue;}next=cur;next._ROW++;//下if(CheckIsAccess(a,n,next)){cur=next;path.push(cur);continue;}next=cur;next._COL--;//左if(CheckIsAccess(a,n,next)){cur=next;path.push(cur);continue;}next=cur;next._COL++;//右if(CheckIsAccess(a,n,next)){cur=next;path.push(cur);continue;}//回退cur=path.top();path.pop();}}voidPrintMaze(int*a,intn)//输出迷宫{for(inti=0;i<n;i++){for(intj=0;j<n;j++){cout<<a[i*n+j]<<"";}cout<<endl;}}