栈于队列

一：栈

1.栈的应用背景

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

关键词：先进先出。

2.栈的两种实现方法：

2.1用ArrayList实现栈

具体代码如下：

importjava.util.ArrayList;
publicclassArrayListAsStack{
ArrayListstack=newArrayList();
publicArrayListAsStack(intn){
stack.ensureCapacity(n);
}
publicvoidpush(Objecto1){
stack.add(o1);
}
publicObjectpop(){
returnstack.remove(stack.size()-1);
}
publicObjecttopEle(){
returnstack.get(stack.size()-1);
}
publicbooleanisEmpty(){

returnstack.isEmpty();
}
publicvoidclean(){
stack.clear();
}
}

Pop：只用删除ArrayList中的最后一个元素

Push:在ArrayList中添加一个元素

2.2用LinkedList实现栈

代码如下：

importjava.util.LinkedList;
publicclassLinkedListAsStack{
LinkedListstack=newLinkedList();
publicvoidpush(Objecto1){
stack.add(o1);
}
publicObjectpop(){
returnstack.removeLast();
}
publicObjecttopEle(){
returnstack.getLast();
}
publicbooleanisEmpty(){
returnstack.isEmpty();
}
publicvoidclean(){
stack.clear();
}
}

Pop：删除链表中最后一个节点

Push：在链表中添加一个节点

二：队列

队列与栈的不同之处在于，队列的两端都有用到，数据从队列的尾部添加，从队列的头部取出。FIFO原则。

1.队列的实现

与栈相同，队列可以通过array和linkedlist两种方式实现，在此不再累述。

2.优先队列

队列的先进先出有时候会有一定的局限性。例如：银行办业务的客户必须按照“先进先出”的性质进行等待办理，但是有的客户持有的是金卡，则应该被有限办理。优先队列则用于处理这类的问题。

即优先队：数据的存入是按照先进先出的方式放进去的，但是存入的数据有对应的优先级，则取出的时候根据优先级取出。

三：用栈实现走迷宫

老鼠走迷宫是栈的一个典型应用，如下，有一个简单的迷宫（m代表入口，e代表出口，0代表该路行得通，1代表墙）：

1 1 0 0

0 0 0 e

0 0 m 1

思想：老鼠会尝试所有可行的路径（上、下、左、右四个方向），如果碰到了死角，则会返回到最后一步再尝试其他路径，所以上下左右方向的顺序会影响到最后寻找的出路。

实现：

我们将迷宫放在一个二维数组里，由于数组的计数从0开始，我们为了更直观，在初始二维数组周围加上2，如下

1 1 1 1 1 1

1 1 1 0 0 1

1 0 0 0 e 1

1 0 0 m 1 1

1 1 1 1 1 1

这里需要用到栈，将可能走的位置按照一定的规律压入栈中（例如上下左右），例如到了A的位置，则在A的基础上往下走，如果A后面没有可行的路径，则返回至A的上一步。下面详解实现。

（1）构建MazeCell：表示迷宫的位置

publicclassMazeCell{
intx;
inty;
publicMazeCell(){

}
publicMazeCell(inta,intb){
this.x=a;
this.y=b;
}
publicBooleanequals(MazeCellcell){
if(cell.x==this.x&&cell.y==this.y)
returntrue;
else
returnfalse;
}
}

（2）寻找出路的具体实现

publicclassMaze{
//构建maze所需的参数
char[][]maze=newchar[5][6];
charentrance='m';
charexit='e';
charpass='0';
charnotPass='1';
charvisited='2';
//获得maze路径所需参数
Stack<MazeCell>pushUnvisited=newStack<MazeCell>();
MazeCellcurrentCell=newMazeCell();
MazeCellexitCell=newMazeCell(2,4);
MazeCellentryCell=newMazeCell(3,3);

publicstaticvoidmain(String[]args){
Mazemaze=newMaze();
maze.makeMaze();
maze.getPath();
}

//构造一个maze
publicvoidmakeMaze(){
//给迷宫外加上1
for(inti=0;i<6;i++){
maze[0][i]=notPass;
maze[4][i]=notPass;
}
for(intj=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;
}

//寻找走出迷宫的路径
publicvoidgetPath(){
currentCell=entryCell;
while(!currentCell.equals(exitCell)){
intx=currentCell.x;
inty=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;
}
//将当前位置往前移
MazeCelltmp=pushUnvisited.pop();
currentCell=tmp;
//输出我走过的节点
System.out.println(tmp.x+","+tmp.y);
}
}
publicvoidpushStack(intx,inty){
//如果是visited或notPass，则不能压进栈
if(maze[x][y]==pass||maze[x][y]==exit){
pushUnvisited.push(newMazeCell(x,y));
}
}
}