java 數(shù)據(jù)結(jié)構(gòu)中棧結(jié)構(gòu)應(yīng)用的兩個(gè)實(shí)例

更新時(shí)間：2017年06月02日 11:08:29 作者：想作會(huì)飛的魚

這篇文章主要介紹了java 數(shù)據(jù)結(jié)構(gòu)中棧結(jié)構(gòu)應(yīng)用的兩個(gè)實(shí)例的相關(guān)資料,需要的朋友可以參考下

java 數(shù)據(jù)結(jié)構(gòu)中棧結(jié)構(gòu)應(yīng)用的兩個(gè)實(shí)例

1、單詞逆序。

要求從控制臺(tái)讀入一串字符，按回車結(jié)束輸入，同時(shí)顯示其逆序字符串。

對(duì)于顛倒順序的操作，用棧來解決是很方便的。具體思想是把字符串中的每一個(gè)字符按順序存入棧中，然后再一個(gè)一個(gè)的從棧中取出。這時(shí)就是按照逆序取出的字符串。

// 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開始 
//-------------------------------------------------------------- 
  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("") )    // 若沒有輸入字符串直接按回車，則結(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è)匹配操作可以用棧來實(shí)現(xiàn)。

具體操作是在輸入過程中，如果遇到左匹配符，則將左匹配符壓入棧中。如果遇到右匹配符，則從棧中取出一個(gè)數(shù)據(jù)，分析其與右匹配符是否相匹配。若匹配，則繼續(xù)進(jìn)行，若不匹配，則報(bào)錯(cuò)終止。

// 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ì)本站的支持！

您可能感興趣的文章: