栈和队列的底层实现及迷宫问题

一：栈1.栈的应用背景

栈是一种线性数据结构，并且只能在某一端存数据和取数据。

关键词：先进先出。

2.栈的两种实现方法：2.1用ArrayList实现栈

具体代码如下：

public class Maze {    //构建maze所需的参数    char[][] maze = new char[5][6];    char entrance = 'm';    char exit = 'e';    char pass= '0';    char notPass='1';    char visited = '2';    //获得maze路径所需参数    Stack<MazeCell> pushUnvisited = new Stack<MazeCell>();    MazeCell currentCell = new MazeCell();    MazeCell exitCell = new MazeCell(2,4);    MazeCell entryCell = new MazeCell(3,3);        public static void main(String[]args){        Maze maze = new Maze();        maze.makeMaze();        maze.getPath();     }          //构造一个maze     public void makeMaze(){        //给迷宫外加上1        for(int i = 0;i<6;i++){           maze[0][i] =notPass;           maze[4][i]=notPass;        }        for(int j = 0;j<5;j++){              maze[j][0] =notPass;              maze[j][5]=notPass;            }        maze[1][1] = notPass;        maze[1][2] =notPass;        maze[1][3] = pass;        maze[1][4] = pass;        maze[2][1] = pass;        maze[2][2] =pass;        maze[2][3] = pass;        maze[2][4] =exit;        maze[3][1] = pass;        maze[3][2] =pass;        maze[3][3] = entrance;        maze[3][4] =notPass;     }          //寻找走出迷宫的路径     public void getPath(){        currentCell = entryCell;        while(!currentCell.equals(exitCell)){            int x = currentCell.x;            int y = currentCell.y;            //搜索路径为上下左右，不同的顺序会有不同结果            pushStack(x-1,y);            pushStack(x+1,y);            pushStack(x,y-1);            pushStack(x,y+1);            //把走过的位置标记成visited            if(!currentCell.equals(entryCell)){                maze[x][y] = visited;            }            //如果在还没到达终点，栈就空了，说明该迷宫米有出路            if(pushUnvisited.isEmpty()){               System.out.println("failure");               return;            }            //将当前位置往前移            MazeCell tmp = pushUnvisited.pop();            currentCell = tmp;            //输出我走过的节点            System.out.println(tmp.x+","+tmp.y);        }     }     public void pushStack(int x ,int y){        //如果是visited或notPass，则不能压进栈        if(maze[x][y] == pass||maze[x][y]==exit){            pushUnvisited.push(new MazeCell(x,y));        }     }}