1.栈模型

栈(stack)是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫作栈的顶(top)。对栈的基本操作有push(进栈)和pop(出栈)，前者相当于插入，后者则是删除最后插入的元素。

栈有时候也被叫作LIFO(后进先出)表，只有栈顶元素是可访问的。栈模型如图1.所示。

图1.栈模型

2.栈的实现

由于栈是一个表，因此任何实现表的方法都能实现栈，ArrayList和LinkedList 都能够支持栈的操作。我们以前的一篇文章《用 java 编程实现链表》中构造的双向链表来实现栈的功能。通过在顶端传入实现push，通过删除表顶端元素实现pop，peek操作考察表顶端元素并返回它的数值。在此我们使用源码包java.util.Stack的Stack类，测试代码为：

package SatckPackage;
import java.util.Stack;
public class StackTest {
 public static void main(String[] args){
 Stack<String> stack = new Stack<String>();
 stack.clear();
 stack.push("First");
 stack.push("Second");
 stack.push("Third");
 System.out.println(stack.size());
 System.out.println(stack.peek());
 stack.pop();
 stack.pop();
 System.out.println(stack.size());
 System.out.println(stack.peek()); 
 }
}
 

栈的构造方法比较简单，在此不做详细讲解，输出结果为：

图2.输出结果图

3.栈的应用——迷宫求解问题

求迷宫从入口到出口的所有路径是一个经典的程序设计问题[1]。由于计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。

为了保证在任何位置都能沿原路退回，显然需要用一个后进先出的结构来保存从入口到当前位置的路径。因此在迷宫求解时应用“栈”也就是自然而然的事情了。在计算机中，我们可以用一个二维数组来表示一个迷宫，如下图所示：

图3.迷宫图

图4.迷宫模型图

我们使用字符1来表示迷宫中的墙体，即灰色的方块；使用字符0来表示可以通过的道路，即白色的方块。求解迷宫的 算法 思想可以描述为下图的流程图：

图5.求解迷宫流程图

3.1. 代表地图上方格的cell 类

package SatckPackage;
/**
 * 迷宫通道类，一个Cell代表地图上的一个方块
 */public class Cell {
 private int x; // 单元所在行
 private int y; // 单元所在列
 private char c; // 字符，通道对应'0'，墙对应'1'
 private boolean isVisited;// 是否访问过
 public Cell(int x, int y, char c, boolean isVisited) {
 super();
 this.x = x;
 this.y = y;
 this.c = c;
 this.isVisited = isVisited;
 }
 public char getC() {
 return c;
 }
 public void setC(char c) {
 this.c = c;
 }
 public boolean isVisited() {
 return isVisited;
 }
 public void setVisited(boolean isVisited) {
 this.isVisited = isVisited;
 }
 public int getX() {
 return x;
 }
 public int getY() {
 return y;
 }
 public boolean equals(Object obj) {
 if (this == obj)
 return true;
 if (obj == null)
 return false;
 if (getClass() != obj.getClass())
 return false;
 Cell other = (Cell) obj;
 if (x != other.x)
 return false;
 if (y != other.y)
 return false;
 return true;
 }
 public String toString() {
 return this.getC() + "("+this.getX()+", "+this.getY() + ")";
 }
}
 

3.2.求解迷宫的主方法

package SatckPackage;
import java.util.Stack;
/**
 * 迷宫求解类
 */public class Maze {
 public static void main(String[] args) {
 char maze[][] = { { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
 { '1', '0', '0', '1', '0', '0', '0', '0', '0', '1' },
 { '1', '0', '1', '1', '0', '0', '1', '1', '0', '1' },
 { '1', '0', '0', '1', '0', '1', '1', '0', '0', '1' },
 { '1', '0', '1', '1', '0', '0', '1', '0', '1', '1' },
 { '1', '0', '0', '1', '0', '1', '1', '0', '1', '1' },
 { '1', '0', '0', '1', '1', '0', '0', '0', '0', '1' },
 { '1', '1', '0', '0', '1', '1', '0', '1', '1', '1' },
 { '1', '1', '1', '0', '0', '0', '0', '0', '1', '1' },
 { '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' }};
 mazeExit(maze, 8, 7, 5, 4);
 }
 /**
 * 求解迷宫
 * @param maze 迷宫的字符数组
 * @param in_x 起点x坐标
 * @param in_y 起点y坐标
 * @param out_x 终点x坐标
 * @param out_y 终点y坐标
 */ public static void mazeExit( char  maze[][], int in_x, int in_y, int out_x, int out_y) {
 Cell[][] cells = createMaze(maze);
 printMaze(cells);
 Cell start = cells[in_x][in_y];
 Cell end = cells[out_x][out_y];
 Stack<Cell> stack = new Stack<>(); 
 stack.clear();
 stack.push(start);
 start.setVisited(true);
 while (!stack.isEmpty()) {
 Cell now = stack.peek();
 if (now.equals(end)) {
 // 找到路径
 int x = out_x;
 int y = out_y;
 while(!stack.isEmpty()){
 Cell cell = stack.pop();
 // 要注意的是，只有和上一次的cell相邻的cell才是路径上的通道
 if(Math.abs(cell.getX()-x) + Math.abs(cell.getY()- y) <= 1){
 cell.setC('*');
 }
 x = cell.getX();
 y = cell.getY();
 }
 System.out.println("找到路径：");
 printMaze(cells);
 return;
 } else {
 // 向四个方向探索
 boolean isDead = true;
 for (int i = 0; i < 4; i++) {
 Cell next_cell = getCell(cells, now, i);
 if (isValid(next_cell)) {
 next_cell.setVisited(true);
 stack.push(next_cell); 
 isDead = false; 
 }
 } 
 // 四个方向都不能走，则该点为死胡同，出栈
 if(isDead){
 stack.pop();
 }
 }
 }
 System.out.println("找不到路径");
 }
 /**
 * 判断一个cell是否是通道
 */ public static boolean isValid(Cell cell) {
 return cell.getC() == '0' && !cell.isVisited();
 }
 /**
 * 根据方向得到下一个cell
 */ public static Cell getCell(Cell[][] cells, Cell now, int direction) {
 int x = now.getX();
 int y = now.getY();
 Cell cell = null;
 switch (direction) {
 case 0:
 // 向下
 cell = cells[x + 1][y];
  break ;
 case 1:
 // 向右
 cell = cells[x][y + 1];
 break;
 case 2:
 // 向上
 cell = cells[x - 1][y];
 break;
 case 3:
 // 向左
 cell = cells[x][y - 1];
 break;
 }
 return cell;
 }
 /**
 * 根据输入的二维char数组创建二维Cell数组
 */ private static Cell[][] createMaze(char[][] maze) {
 Cell[][] cells = new Cell[maze. length ][maze[0].length];
 for (int i = 0; i < maze.length; i++) {
 for (int j = 0; j < maze[i].length; j++) {
 char c = maze[i][j];
 Cell cell = new Cell(i, j, c, false);
 cells[i][j] = cell;
 }
 }
 return cells;
 }
 /**
 * 打印迷宫
 */ private static void printMaze(Cell[][] cells) {
 for (int i = 0; i < cells.length; i++) {
 for (int j = 0; j < cells[i].length; j++) {
 System.out.print(cells[i][j].getC() + " ");
 }
 System.out.println();
 }
 }
}
 

输出结果为：

图6.输出结果图

分析上述算法我们可以在下面代码处打上断电来观察输出结果：

 while (!stack.isEmpty()) {
 
 Cell now = stack.peek();
 System.out.println("X="+now.getX());
 System.out.println("Y="+now.getY());
 System.out.println("---------------");
 ···························}
 

图7.算法轨迹

（红色箭头表示push(),蓝色箭头表示pop()）

图7.给出了算法在各个步骤所走过的方格位置，其中红色箭头表示push(),蓝色箭头表示pop()，可以看出算法从起点开始，通过遍历完所有的途径，直到找到一条到达终点的轨迹为止。

[1]