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

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

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