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

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