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余7 15 * 250/8=31余2 16 * 31/8=3余7 17 * 3/8=0余3 18 * 所以8进制结果3727 19 * @param @param i 20 * @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 //输出3727 38 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余7 15 * 250/8=31余2 16 * 31/8=3余7 17 * 3/8=0余3 18 * 所以8进制结果3727 19 * @param @param i 20 * @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 str 37 * @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 else 56 return false; 57 case ']'://当遇到']'它的时候，那么栈顶元素必然是'['与之对应，否则就是非法的 58 if(!s.isEmpty() && ((Integer)s.pop()).intValue() == '[') 59 break; 60 else 61 return false; 62 case ')'://当遇到')'它的时候，那么栈顶元素必然是'('与之对应，否则就是非法的 63 if(!s.isEmpty() && ((Integer)s.pop()).intValue() == '(') 64 break; 65 else 66 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 // //输出3727 80 // while(!stack.isEmpty()){ 81 // System.out.print(stack.pop()); 82 // } 83 84 System.out.println(app.bracketMatch("[{()}]"));//true 85 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 cell 100 * @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 peek 112 * @param @param cell 113 * @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<row.length;y++) 142 cells[x][y] = new Cell(x,y,maze[x][y],false); 143 } 144 return cells; 145 } 146 147 148 public static void main(String[] args) { 149 Cell cell = new Cell(); 150 151 char[][] maze = { 152 {'1','1','1','1','1','1','1','1','1','1'}, 153 {'1','0','0','1','1','1','0','0','1','1'}, 154 {'1','0','0','1','1','0','0','1','0','1'}, 155 {'1','0','0','0','0','0','0','1','0','1'}, 156 {'1','0','0','0','0','1','1','0','0','1'}, 157 {'1','0','0','1','1','0','0','1','0','1'}, 158 {'1','0','0','0','0','1','0','1','0','1'}, 159 {'1','0','1','1','0','0','0','1','0','1'}, 160 {'1','1','0','0','0','0','1','0','0','1'}, 161 {'1','1','1','1','1','1','1','1','1','1'}, 162 }; 163 cell.mazeExit(maze , 1, 7, 3, 1); 164 165 } 166 }
结果：
