4.3 堆栈的应用
4.3.1 进制转换
十进制转成8进制：
1 package com.datastructure.chapter04.demo; 2 3 import com.datastructure.chapter04.impl.StackSLinked; 4 import com.datastructure.chapter04.interfaces.Stack; 5 6 public class ApplicationOfStack { 7 8 9 10 /** 11 * @Title: baseConversion 12 * @Description: 13 * 10进制转成8进制：每次对十进制数求余后的结果接着求余，余数的逆序就是8进制数14 * 2007/8=250余715 * 250/8=31余216 * 31/8=3余717 * 3/8=0余318 * 所以8进制结果372719 * @param @param i20 * @param @return 21 * @return Stack 22 * @throws 23 */24 public Stack baseConversion(int i){25 Stack s = new StackSLinked();26 while(i>0){27 s.push(i%8+"");28 i=i/8;29 }30 return s;31 }32 33 public static void main(String[] args) {34 35 ApplicationOfStack app = new ApplicationOfStack();36 Stack stack = app.baseConversion(2007);37 //输出372738 while(!stack.isEmpty()){39 System.out.print(stack.pop());40 }41 42 }43 44 45 } 4.3.2 括号匹配检测
1 package com.datastructure.chapter04.demo; 2 3 import com.datastructure.chapter04.impl.StackSLinked; 4 import com.datastructure.chapter04.interfaces.Stack; 5 6 public class ApplicationOfStack { 7 8 9 10 /** 11 * @Title: baseConversion 12 * @Description: 13 * 10进制转成8进制：每次对十进制数求余后的结果接着求余，余数的逆序就是8进制数14 * 2007/8=250余715 * 250/8=31余216 * 31/8=3余717 * 3/8=0余318 * 所以8进制结果372719 * @param @param i20 * @param @return 21 * @return Stack 22 * @throws 23 */24 public Stack baseConversion(int i){25 Stack s = new StackSLinked();26 while(i>0){27 s.push(i%8+"");28 i=i/8;29 }30 return s;31 }32 33 /** 34 * @Title: bracketMatch 35 * @Description: 括号匹配检测 36 * @param @param str37 * @param @return 38 * @return boolean 39 * @throws 40 */41 public boolean bracketMatch(String str){42 StackSLinked s = new StackSLinked();43 44 for (int i = 0; i < str.length(); i++) {45 char c = str.charAt(i);46 switch(c){47 case '{':48 case '[':49 case '(':50 s.push(Integer.valueOf(c));51 break;52 case '}'://当遇到'}'它的时候，那么栈顶元素必然是'{'与之对应，否则就是非法的53 if(!s.isEmpty() && ((Integer)s.pop()).intValue() == '{')54 break;55 else56 return false;57 case ']'://当遇到']'它的时候，那么栈顶元素必然是'['与之对应，否则就是非法的58 if(!s.isEmpty() && ((Integer)s.pop()).intValue() == '[')59 break;60 else61 return false;62 case ')'://当遇到')'它的时候，那么栈顶元素必然是'('与之对应，否则就是非法的63 if(!s.isEmpty() && ((Integer)s.pop()).intValue() == '(')64 break;65 else66 return false;67 }68 }69 70 if(s.isEmpty()) return true;71 return false;72 }73 74 75 public static void main(String[] args) {76 77 ApplicationOfStack app = new ApplicationOfStack();78 // Stack stack = app.baseConversion(2007);79 // //输出372780 // while(!stack.isEmpty()){81 // System.out.print(stack.pop());82 // }83 84 System.out.println(app.bracketMatch("[{()}]"));//true85 86 }87 88 89 } 4.3.3 迷宫求解
每个单元格类Cell以及解法：
1 package com.datastructure.chapter04.demo; 2 3 import com.datastructure.chapter04.impl.StackSLinked; 4 import com.datastructure.chapter04.interfaces.Stack; 5 6 /** 7 * @ClassName: Cell 8 * @Description:每个单元格 9 * @author 10 * @date 2018年3月17日 下午10:50:56 11 * 12 */ 13 public class Cell { 14 15 int x = 0;//单元所在行 16 17 int y = 0;//单元所在列 18 19 boolean visited = false;//是否访问过 20 21 char c = ' ';//是墙('1')、可通路('0')或期待到终点的路径 22 23 public Cell(){} 24 25 public Cell(int x,int y,char c,boolean visited) { 26 this.x = x; this.y = y; 27 this.c = c; this.visited = visited; 28 } 29 30 31 public void mazeExit(char[][] maze,int sx,int sy,int ex,int ey){ 32 33 Cell[][] cells = createMaze(maze);//创建初始化迷宫; 34 printMaze(cells);//打印迷宫 35 36 Stack stack = new StackSLinked();//构造堆栈 37 38 Cell startCell = cells[sx][sy]; 39 Cell endCell = cells[ex][ey]; 40 41 stack.push(startCell);//起点入栈 42 43 startCell.visited = true; 44 45 while(!stack.isEmpty()){ 46 Cell current = (Cell) stack.peek(); 47 48 if(current == endCell){ //路径找到 49 while(!stack.isEmpty()){ 50 Cell cell = (Cell) stack.pop();//沿着原路返回，将路径上的单元设置为* 51 cell.c = '*'; 52 //堆栈中与cell相邻的单元才是路径的组成部分，除此之外 53 //堆栈中还有记录下来但是未继续向下探索的单元， 54 //这些单元直接出栈 55 while(!stack.isEmpty() && !isAdjoinCell((Cell)stack.peek(),cell)) 56 stack.pop(); 57 58 } 59 System.out.println("找到从起点到终点的路劲."); 60 printMaze(cells); 61 return ; 62 } else { //如果当前位置不是终点 63 int x = current.x; 64 int y = current.y; 65 int count = 0; 66 if(isValidWayCell(cells[x+1][y])){ //向下 67 stack.push(cells[x+1][y]); 68 cells[x+1][y].visited = true; 69 count++; 70 } 71 72 if(isValidWayCell(cells[x][y+1])){ //向右 73 stack.push(cells[x][y+1]); 74 cells[x][y+1].visited = true; 75 count++; 76 } 77 78 if(isValidWayCell(cells[x-1][y])){ //向上 79 stack.push(cells[x-1][y]); 80 cells[x-1][y].visited = true; 81 count++; 82 } 83 84 if(isValidWayCell(cells[x][y-1])){ //向左 85 stack.push(cells[x][y-1]); 86 cells[x][y-1].visited = true; 87 count++; 88 } 89 if(count == 0) stack.pop();//如果是死点，出栈 90 } 91 } 92 System.out.println("没有从起点到终点的路径"); 93 } 94 95 96 /** 97 * @Title: isValidWayCell 98 * @Description: 判断这个单元格是不是墙，是不是已经入栈过的 99 * @param @param cell100 * @param @return 101 * @return boolean 102 * @throws 103 */104 private boolean isValidWayCell(Cell cell) {105 return cell.c=='0' && !cell.visited;106 }107 108 /** 109 * @Title: isAdjoinCell 110 * @Description: 判断是否是相邻的单元格111 * @param @param peek112 * @param @param cell113 * @param @return 114 * @return boolean 115 * @throws 116 */117 private boolean isAdjoinCell(Cell cell1, Cell cell2) {118 119 if(cell1.x == cell2.x && Math.abs(cell1.y-cell2.y)<2) return true;120 if(cell1.y == cell2.y && Math.abs(cell1.x-cell2.x)<2) return true;121 122 return false;123 }124 125 private void printMaze(Cell[][] cells) {126 for (int x = 0; x < cells.length; x++) {127 for (int y = 0; y < cells[x].length; y++) {128 System.out.print(cells[x][y].c);129 }130 System.out.println();131 }132 }133 134 135 private Cell[][] createMaze(char[][] maze) {136 137 Cell[][] cells = new Cell[maze.length][];138 for (int x = 0; x < maze.length; x++) {139 char[] row = maze[x];140 cells[x] = new Cell[row.length];141 for(int y=0;y
结果：
