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

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

1、单词逆序。

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

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

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

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

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