首页 > 代码库 > Java数据结构与算法(3) - 栈(栈和转置)

Java数据结构与算法(3) - 栈(栈和转置)

栈的基本特性是后进先出,最简单的用途是用于转置,还有其他诸如括号匹配,中序表达式(A+B*(C-D/(E+F)) --> ABCDEF+/-*+)和后续表达式(345+*612+/- --> 3*(4+5)-6/(1+2))互换等高级用法。

示例代码:

package chap04.Reverse;import java.io.*; // for I/Oclass StackX {    private int maxSize;    private char[] stackArray;    private int top;    public StackX(int max) {        maxSize = max;        stackArray = new char[maxSize];        top = -1;    }    public void push(char j) {        stackArray[++top] = j;    }    public char pop() {        return stackArray[top--];    }    public char peek() {        return stackArray[top];    }    public boolean isEmpty() {        return (top == -1);    }        public boolean isFull() {        return (top == maxSize - 1);    }}  class Reverser {    private String input;      private String output;      public Reverser(String in) {        input = in;    }    // 转置    public String doRev() {        int stackSize = input.length();          StackX theStack = new StackX(stackSize);          for (int j = 0; j < input.length(); j++) {            char ch = input.charAt(j);              theStack.push(ch);          }        output = "";        while (!theStack.isEmpty()) {            char ch = theStack.pop();              output = output + ch;          }        return output;    }  }  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 = getString1();              if (input.equals("")) {                  break;            }            Reverser theReverser = new Reverser(input);            output = theReverser.doRev();             System.out.println("Reversed: " + output);        }     }     public static String getString1() throws IOException {        InputStreamReader isr = new InputStreamReader(System.in);        BufferedReader br = new BufferedReader(isr);        String s = br.readLine();        return s;    }} 

 

Java数据结构与算法(3) - 栈(栈和转置)