java 数据结构中栈结构应用的两个实例

java 数据结构中栈结构应用的两个实例

java 数据结构中栈结构应用的两个实例

1、单词逆序。

要求从控制台读入一串字符，按回车结束输入，同时显示其逆序字符串。

对于颠倒顺序的操作，用栈来解决是很方便的。具体思想是把字符串中的每一个字符按顺序存入栈中，然后再一个一个的从栈中取出。这时就是按照逆序取出的字符串。  &nbsphttp://;

// reverse.java

// stack used to reverse a string

// to run this program: C>java ReverseApp

import java.io.*; // for I/O

////////////////////////////////////////////////////////////////

class StackX//定义了栈的基本结构和操作

{

private int maxSize;//栈最大值

private char[] stackArray;//栈内用数组存储数据

private int top;//当前栈顶标号，从0开始

//--------------------------------------------------------------

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;GEfhUpiWf // 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

{

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("") ) // 若没有输入字符串直接按回车，则结束

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;

}

//----------------------------------GEfhUpiWf----------------------------

} // end class ReverseApp

////////////////////////////////////////////////////////////////

2.分隔符匹配

有些分割符在编程中一定是成对出现的，例如（），{}，和[]等。如果发现有未匹配的分隔符，编译器会报错。因为匹配操作采取就近原则，后输入的分割符优先匹配，具有“后进先出”的特点。这个匹配操作可以用栈来实现。

具体操作是在输入过程中，如果遇到左匹配符，则将左匹配符压入栈中。如果遇到右匹配符，则从栈中取出一个数据，分析其与右匹配符是否相匹配。若匹配，则继续进行，若不匹配，则报错终止。

// 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

{

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

////////////////////////////////////////////////////////////////

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

{

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("") ) // 若没有输入字符串直接按回车，则结束

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;

}

//----------------------------------GEfhUpiWf----------------------------

} // end class ReverseApp

////////////////////////////////////////////////////////////////

2.分隔符匹配

有些分割符在编程中一定是成对出现的，例如（），{}，和[]等。如果发现有未匹配的分隔符，编译器会报错。因为匹配操作采取就近原则，后输入的分割符优先匹配，具有“后进先出”的特点。这个匹配操作可以用栈来实现。

具体操作是在输入过程中，如果遇到左匹配符，则将左匹配符压入栈中。如果遇到右匹配符，则从栈中取出一个数据，分析其与右匹配符是否相匹配。若匹配，则继续进行，若不匹配，则报错终止。

// 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

{

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

////////////////////////////////////////////////////////////////

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

{

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

////////////////////////////////////////////////////////////////

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。