顺序栈的实现

顺序栈的实现"/>

顺序栈的实现

栈的概念

对于栈（Stack），后进先出（Last In First Out，LIFO），栈也是一种线性表，只不过是一种操作受限的线性表，只能在一端操作，也就是不允许在中间进行查找、插入、删除等操作。

栈的图：

进出的一端称为栈顶（top），另一端称为栈底（base），栈可以顺序存储，也可以链式存储，这里讲的是栈的顺序存储方式。

栈也可以比喻成一个乒乓球桶，桶底是封口的，桶顶是打开的，桶的横截面积恰好为一个乒乓球投影的面积，也就是说你只能从最后一个乒乓球后放入乒乓球（后面放进去的乒乓球会压着前面的乒乓球），只能拿走最后一个乒乓球（不能拿走被压着的乒乓球）。

栈的算法实现

栈的数据定义

#define MAX_SIZE 120    //栈的最大容量
typedef int DateElem;
typedef struct _Stack
{DateElem* top;     //栈顶指针DateElem* base;    //栈底指针，指向栈的开始
}Stack;

初始化栈

bool initStack(Stack& s)
{s.base = new DateElem[MAX_SIZE];if (!s.base) return false;        //空间分配失败s.top = s.base;        //为空栈，栈中无任何元素return true;
}

销毁栈

销毁与初始化一一对应，初始化时申请了内存，销毁时就需要释放。

void destoryStack(Stack& s)
{if (s.base != NULL) //栈空间有效{delete s.base;s.base = s.top = NULL;}}

入栈

bool pushStack(Stack& s, DateElem e)
{if (!s.base || (s.top - s.base) >= MAX_SIZE) return false; //栈没建立 或者 栈空间满了*(s.top++) = e; //因为最开始 s->top = 0 return true;
}

出栈

bool popStack(Stack& s, DateElem& e) //用 e 返回被删除的元素的指
{if (!s.base || s.base == s.top) return false;e = *(--s.top); //先将栈顶元素赋值给e，栈顶指针再移动，因为栈顶指针都是指向栈顶元素的后一个位置，除了栈为空时，栈顶指针为 0return true;
}

获取栈顶元素

bool getTop(Stack& s,DateElem &e)
{if (s.top > s.base) //栈不为空{e = *(s.top - 1); //e 返回栈顶元素的值return true;}else{return false;}
}

判断栈是否为空

bool IsEmpty(Stack& s)
{if (s.base == s.top){	return true;}else{return false;}
}

获取栈中元素的个数

int getLength(Stack& s)
{return (int)(s.top - s.base);
}

栈的应用

迷宫问题

在给定区域内（二维数组）告诉你起点，找到一条到出口的移动路线。

迷宫求解问题

对于走出一个迷宫，我们只需要将所有的路都走一遍就可以走出迷宫（需要避免走重复的路，对走过的路做好标记），在这个过程中，如果遇到岔路，就选择其中一条路前进，如果碰到死胡同就返回，回退到上个岔路，选择别的路,如果这个岔路也无路可走了，继续回退到上个岔路选择一条路……直到找到出口，或者是无路可走。（我们把一个坐标的位置看作一个岔路，可以向上、下，左、右走）

找迷宫的通路使用到的是回溯法，穷举法的改进，回溯的过程需要用到栈。（我最开始想到的是栈的递归）

回溯法:对一个包括有很多个结点，每个结点有若千个搜索分支的问题，把原问题分解为若千个子问题求解的算法;当搜索到某个结点发现无法再继续搜索下去时，就让搜索过程回溯(回退)到该节点的前一一个结点，继续搜索该节点外的其他尚未搜索的分支;如果发现该结点无法再搜索下去，就让搜索过程回溯到这个结点的前一结点继续这样的搜索过程;这样的搜索过程--直进行到搜索到问题的解或者搜索完了全部可搜索分支没有解存在为止。

代码实现 

其中栈存储的数据为，而不是之前的 int 类型了：

typedef struct _Position
{int x;int y;
}position;typedef position DateElem;

然后代码我就没有发关于顺序栈的实现了。

具体思想：

一、在当前位置，分别判断左、上、右、下四个方向的位置是否为路。

二、选择一条路，然后这条路就是当前位置了。（每当某个位置变为当前位置就要标记一下，入口也要，防止重复走），判断当前位置是否为终点，不为的话，执行步骤一。

三、如果在当前位置，左、上、右、下四个方向的位置都走过了或者是墙，就回退到上一个位置（存储在栈中），执行步骤一、二。

四、重复步骤一、二、三，直到找到出口或者回退到入口。

#include <iostream>
#include "顺序栈.h"using namespace std;#define ROW 6
#define COL 6typedef struct _Maze //迷宫的结构体
{int map[ROW][COL];
}Maze;void initMaze(Maze* maze, int map[ROW][COL]) //将传入的地图数据来初始化迷宫
{for (int i = 0; i < ROW; i++){for (int j = 0; j < COL; j++){maze->map[i][j] = map[i][j];}}
}
void printMaze(Maze* maze) //打印整个迷宫
{for (int i = 0; i < ROW; i++){for (int j = 0; j < COL; j++){cout << maze->map[i][j] << " ";}cout << endl;}
}int IsValidEnter(position* enter,Maze *maze) //判断入口是否有效
{if (!enter || !maze) return -1; //合法性检查if ((enter->x == 0 || enter->x == ROW-1 ) ||(enter->y == 0 || enter->y == COL-1) &&maze->map[enter->x][enter->y] == 1) //在地图的边界上并且是通路{return 1;}else{return 0;}
}
int IsValidExit(position *cur, Maze* maze,position *enter) //判断出口是否有效
{if (!cur || !maze || !enter) return -1; //合法性检查if (((cur->x == 0 || cur->x == ROW - 1) ||(cur->y == 0 || cur->y == COL - 1)) &&(enter->x != cur->x && enter->y != cur->y)) //在地图边界上，并且不是入口，那就是出口{return 1;}else{return 0;}}
int IsNextPass(position *next, Maze* maze) //判断下一步的位置是否有效
{if (!next || !maze) return -1; //合法性检查if ((next->x >= 0 && next->x < ROW) &&(next->y >= 0 && next->y < COL) &&maze->map[next->x][next->y] == 1) //在地图里，并且是路（没走过），等于2、3、4……就是走过的路{return 1;}else{return 0;}
}
int PassMaze(position *enter,Maze *maze,Stack *s)
{if (!maze || IsValidEnter(enter,maze) == 0) return 0; //迷宫为空或者入口无效position cur = { enter->x,enter->y }; //当前人所在的位置position next; // 保存下一步的位置pushStack(*s, cur); //入口入栈maze->map[enter->x][enter->y] = 2; // 走过的地方要改变他的值，防止重复走while (!IsEmpty(*s)){getTop(*s,cur); //得到当前所在的位置if (IsValidExit(&cur, maze, enter)) //是出口，就可以结束了{return 1;}next = cur;next.y--;    //尝试向左走一步，看看能不能继续走if (IsNextPass(&next, maze) == 1) {pushStack(*s, next); //下一步入栈maze->map[next.x][next.y] = maze->map[cur.x][cur.y] + 1; //下一步的值为当前位置的值+1continue;}next = cur;next.x--; //尝试向上走一步，看看能不能继续走if (IsNextPass(&next, maze) == 1){pushStack(*s, next);maze->map[next.x][next.y] = maze->map[cur.x][cur.y] + 1;continue;}next = cur;next.y++; //尝试向右走一步，看看能不能继续走if (IsNextPass(&next, maze) == 1){pushStack(*s, next);maze->map[next.x][next.y] = maze->map[cur.x][cur.y] + 1;continue;}next = cur;next.x++; //尝试向下走一步，看看能不能继续走if (IsNextPass(&next, maze) == 1){pushStack(*s, next); maze->map[next.x][next.y] = maze->map[cur.x][cur.y] + 1; continue;}//走到这里了，说明当前位置的四个方向都走不通，进行回溯（到上个结点），看看上个结点未被遍历的方向能否走通position temp;popStack(*s, temp);}return false;
}
int main(void)
{int map[ROW][COL] = {0,0,1,0,0,0,0,0,1,1,0,0,0,0,1,0,0,0,0,1,1,1,1,0,0,0,1,0,1,0,0,0,0,0,1,0}; // 二维数组代表迷宫，1代表路，0代表墙Maze maze;		//迷宫的拷贝initMaze(&maze, map);		//初始化maze迷宫//printMaze(&maze);		//打印迷宫，测试position enter = { 0,2 };		//创建了迷宫入口并初始化Stack s;		//栈用来保存已走过的路，便于回溯initStack(s);		//初始化栈if (PassMaze(&enter, &maze, &s)){cout << "恭喜你，找到了出口" << endl;}else{cout << "无路可走了" << endl;}printMaze(&maze); //打印迷宫return 0;
}

代码很多，但是结构清楚。以下是代码的执行效果，能清楚知道移动的轨迹。