java 數(shù)據(jù)結(jié)構(gòu)中棧結(jié)構(gòu)應(yīng)用的兩個(gè)實(shí)例
1、單詞逆序。
要求從控制臺(tái)讀入一串字符，按回車(chē)結(jié)束輸入，同時(shí)顯示其逆序字符串。
對(duì)于顛倒順序的操作，用棧來(lái)解決是很方便的。具體思想是把字符串中的每一個(gè)字符按順序存入棧中，然后再一個(gè)一個(gè)的從棧中取出。這時(shí)就是按照逆序取出的字符串。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
// reverse.java // stack used to reverse a string // to run this program: C>java ReverseApp import java.io.*; // for I/O //////////////////////////////////////////////////////////////// class StackX//定義了棧的基本結(jié)構(gòu)和操作 { private int maxSize;//棧最大值 private char[] stackArray;//棧內(nèi)用數(shù)組存儲(chǔ)數(shù)據(jù) private int top;//當(dāng)前棧頂標(biāo)號(hào)，從0開(kāi)始 //-------------------------------------------------------------- public StackX(int max) // constructor { maxSize = max; stackArray = new char[maxSize]; top = -1; } //-------------------------------------------------------------- public void push(char j) // put item on top of stack { stackArray[++top] = j; } //-------------------------------------------------------------- public char pop() // take item from top of stack { return stackArray[top--]; } //-------------------------------------------------------------- public char peek() // peek at top of stack { return stackArray[top]; } //-------------------------------------------------------------- public boolean isEmpty() // true if stack is empty { return (top == -1); } //-------------------------------------------------------------- } // end class StackX //////////////////////////////////////////////////////////////// class Reverser//封裝了單詞逆序的操作 { private String input; // input string private String output; // output string //-------------------------------------------------------------- public Reverser(String in) // constructor { input = in; } //-------------------------------------------------------------- public String doRev() // reverse the string { int stackSize = input.length(); // get max stack size StackX theStack = new StackX(stackSize); // make stack for(int j=0; j<input.length(); j++) { char ch = input.charAt(j); // get a char from input theStack.push(ch); // push it } output = ""; while( !theStack.isEmpty() ) { char ch = theStack.pop(); // pop a char, output = output + ch; // append to output } return output; } // end doRev() //-------------------------------------------------------------- } // end class Reverser //////////////////////////////////////////////////////////////// class ReverseApp { public static void main(String[] args) throws IOException { String input, output; while(true) { System.out.print("Enter a string: "); System.out.flush(); input = getString(); // read a string from kbd if( input.equals("") ) // 若沒(méi)有輸入字符串直接按回車(chē)，則結(jié)束 break; // make a Reverser Reverser theReverser = new Reverser(input); output = theReverser.doRev(); // use it System.out.println("Reversed: " + output); } // end while System.out.println("this is end"); } // end main() //-------------------------------------------------------------- public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } //-------------------------------------------------------------- } // end class ReverseApp //////////////////////////////////////////////////////////////// |
2.分隔符匹配
有些分割符在編程中一定是成對(duì)出現(xiàn)的，例如（），{}，和[]等。如果發(fā)現(xiàn)有未匹配的分隔符，編譯器會(huì)報(bào)錯(cuò)。因?yàn)槠ヅ洳僮鞑扇【徒瓌t，后輸入的分割符優(yōu)先匹配，具有“后進(jìn)先出”的特點(diǎn)。這個(gè)匹配操作可以用棧來(lái)實(shí)現(xiàn)。
具體操作是在輸入過(guò)程中，如果遇到左匹配符，則將左匹配符壓入棧中。如果遇到右匹配符，則從棧中取出一個(gè)數(shù)據(jù)，分析其與右匹配符是否相匹配。若匹配，則繼續(xù)進(jìn)行，若不匹配，則報(bào)錯(cuò)終止。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
// brackets.java // stacks used to check matching brackets // to run this program: C>java bracketsApp import java.io.*; // for I/O //////////////////////////////////////////////////////////////// class StackX { private int maxSize; private char[] stackArray; private int top; //-------------------------------------------------------------- public StackX(int s) // constructor { maxSize = s; stackArray = new char[maxSize]; top = -1; } //-------------------------------------------------------------- public void push(char j) // put item on top of stack { stackArray[++top] = j; } //-------------------------------------------------------------- public char pop() // take item from top of stack { return stackArray[top--]; } //-------------------------------------------------------------- public char peek() // peek at top of stack { return stackArray[top]; } //-------------------------------------------------------------- public boolean isEmpty() // true if stack is empty { return (top == -1); } //-------------------------------------------------------------- } // end class StackX //////////////////////////////////////////////////////////////// class BracketChecker { private String input; // input string //-------------------------------------------------------------- public BracketChecker(String in) // constructor { input = in; } //-------------------------------------------------------------- public void check() { int stackSize = input.length(); // get max stack size StackX theStack = new StackX(stackSize); // make stack for(int j=0; j<input.length(); j++) // get chars in turn { char ch = input.charAt(j); // get char switch(ch) { case '{': // opening symbols case '[': case '(': theStack.push(ch); // push them break; case '}': // closing symbols case ']': case ')': if( !theStack.isEmpty() ) // if stack not empty, { char chx = theStack.pop(); // pop and check if( (ch=='}' && chx!='{') || (ch==']' && chx!='[') || (ch==')' && chx!='(') )//分隔符不匹配 System.out.println("Error: "+ch+" at "+j); } else // prematurely empty System.out.println("Error: "+ch+" at "+j); break; default: // no action on other characters break; } // end switch } // end for // at this point, all characters have been processed if( !theStack.isEmpty() ) System.out.println("Error: missing right delimiter"); } // end check() //-------------------------------------------------------------- } // end class BracketChecker //////////////////////////////////////////////////////////////// class BracketsApp { public static void main(String[] args) throws IOException { String input; while(true) { System.out.print( "Enter string containing delimiters: "); System.out.flush(); input = getString(); // read a string from kbd if( input.equals("") ) // quit if [Enter] break; // make a BracketChecker BracketChecker theChecker = new BracketChecker(input); theChecker.check(); // check brackets } // end while } // end main() //-------------------------------------------------------------- public static String getString() throws IOException { InputStreamReader isr = new InputStreamReader(System.in); BufferedReader br = new BufferedReader(isr); String s = br.readLine(); return s; } //-------------------------------------------------------------- } // end class BracketsApp //////////////////////////////////////////////////////////////// |
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
原文鏈接：http://blog.csdn.net/xiaokang123456kao/article/details/54089360
