详谈栈的实现and几个算法实现

    对于栈的概念以及图解，在之前的文章中已经写过了，而代码却没有多少，恐理解肤浅，故代码献上，以求真知~（重新看数据结构算法C那本书，还有好些个经典算法。。。比如迷宫求解和汉诺塔，争取一一实现）

<span style="font-family:KaiTi_GB2312;"><strong>1.栈的顺序存储实现：

/**

    * 堆栈在使用过程中所需的最大空间很难估计，

    * 因此，一般来说在构造堆栈时不应设定堆栈的最大容量。

    * 一种合理的做法和线性表的实现类似，

    * 先为堆栈分配一个基本容量，

    * 然后在实际的使用过程中，

    * 当堆栈的空间不够时再倍增存储空间，这个过程所需的时间均摊到每个

    * 数据元素时间为Θ (1)，不会影响操作实现的时间复杂度。

*/

public class StackTest {

    public static void main(String args[]) {

        Stack stack = new Stack(10); //make new Stack

        stack.push(10);

        stack.push(20);

        stack.push(30);

        stack.push(30);

        while(!stack.isEmpty()){

            int value = stack.pop();

            System.out.println(value);

            System.out.println();

        }

    }

}


class Stack{

    private int maxSize;

    private int[] stackArray;

    private int top; //栈顶元素

    public Stack(int s){

        maxSize = s;

        stackArray = new int[maxSize];

        top = -1;

    }

    //返回堆栈的大小

    public int getSize(){

        return top + 1;

    }


    //判断堆栈是否为空

    public boolean isEmpty(){

        return top < 0;

    }


/**

    * push()方法中将top值增加1，

    * 使它指向原顶端数据项上面的一个位置，

    * 并在这个位置上存储一个数据项。

    * 再次提醒，

    * top是在插入数据项之前递增的。

    * @param i

*/


    //入栈

    public void push(int i){

        stackArray[++top] = i;

    }


/**

    * pop()方法返回top标识的数据项值，然后top - 1

    * 这个方法有效的从栈中移除数据项，虽然数据项仍然存在数组中

    * (直到有新的数据项压入栈中覆盖这个数据项)，但不能再访问了

    * @return

*/

    //出栈

    public int pop(){

        return stackArray[top--];

    }

}

2.1单词逆序
  
public class NumInverte {

public static void main(String args[]){
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入要操作的数的数量");
        int stackSize = scanner.nextInt();
        Stack stack = new Stack(stackSize);
        System.out.println("输入数字");
        for(int i = 0;i <= stack.getSize();i++){
            i = scanner.nextInt();
            stack.push(i);
        }
        System.out.println("数字逆序后输出");
        while(!stack.isEmpty()) {
            System.out.println(stack.pop() + " ");
        }
    }
}
2.2后缀表达式
形如：
//计算6 5 2 3 + 8 * + 3 + *    ( (2 + 3) * 8 + 5 + 3 ) * 6
这个记法叫做后缀或者逆波兰记法，计算这个问题的最佳算法是使用栈。
计算一个后缀表达式的时间是O(N)，因为对输入的每个元素的处理都是由一些栈操作组成从而花费常数时间。
注意：当一个表达式以后缀记号给出时，没有必要知道任何优先规则比中缀表达式更容易计算，不用优先考虑规则和括弧，表达式中的操作数和操作符就足以完成任务。
后缀表达式的计算规则：
从左到右扫描整个表达式，把每个操作符应用到其之前的两个操作数，并计算结果。
import java.util.Stack;
//计算6 5 2 3 + 8 * + 3 + *    ( (2 + 3) * 8 + 5 + 3 ) * 6
/**
 * 计算后缀表达式，假定操作数都是常量
 * */
public class PostfixEvaluator {
 /** 栈 */
 private Stack<Integer> stack;
 /** 创建一个新栈 */
 public PostfixEvaluator() {
  stack = new Stack<Integer>();
 }
 /**
  * 从左到右扫描表达式，以此标识出每个符号（操作数或操作符）。如果是操作数， 则把它压入栈中。如果是操作符，则从栈中弹出两个元素，
  * 并把该操作符应用在这两个元素上，然后把操作结果压入栈中。 当到达表达式的末尾时，栈中所剩域的元素就是该表达式的计算结果。
  * @param expr 后缀表达式
  * @return int 后缀表达式的值
  * */
 public int evaluate(String expr){
  int op1 , op2 , result = 0;
  String operator;
  //将字符串分解. \\s匹配任何空白字符，包括空格、制表符、换页符等。
  String[] takeoperator = expr.split("\\s");
  for(int i = 0 ; i < takeoperator.length ; i++){
   System.out.print(takeoperator[i]+" ");//输出
   operator = takeoperator[i];
   if(isOperator(operator)){//判断是操作符，则出栈两个操作数  
                op2 = (stack.pop()).intValue();  
                op1 = (stack.pop()).intValue();  
                result = evalSingleOp (operator.charAt(0),op1,op2);//计算结果  
                stack.push(new Integer(result));//把计算结果压入栈中  
            }else {  
                stack.push(new Integer(Integer.parseInt(operator)));//压入操作数
            }
  }
  return result;
 }
 /**
  * 计算
  *
  * @param1 op1 第一个操作数
  * @prama2 op2第二个操作数
  * @return 计算的结果
  * */
 private int evalSingleOp(char operator, int op1, int op2) {
  int result = 0;
  switch (operator) {
  case '+':
   result = op1 + op2;
   break;
  case '-':
   result = op1 - op2;
   break;
  case '*':
   result = op1 * op2;
   break;
  case '/':
   result = op1 / op2;
   break;
  }
  return result;
 }
 /**
  * 判断是否为操作符
  *
  * @param token
  * @return boolean
  * */
 private boolean isOperator(String operator) {
  return operator.equals("+") || operator.equals("-")
      || operator.equals("*") || operator.equals("/");
 }
}
/*测试类
import java.util.Scanner;
public class PostfixEvaluatorTest {
 public static void main(String[] args) {
  String expression, again;
  int result;
  try {
   @SuppressWarnings("resource")
   Scanner in = new Scanner(System.in);
   do {
    PostfixEvaluator evaluator = new PostfixEvaluator();
    System.out.println("请输入一个后缀表达式");
    expression = in.nextLine();
    result = evaluator.evaluate(expression);
    System.out.println();
    System.out.println("计算结果为：" + result);
    System.out.println("计算另外一个表达式[Y/N]?：");
    again = in.nextLine();
    if (again.equalsIgnoreCase("n")) {
     System.out.println("计算退出！");
    }
    System.out.println();
   } while (again.equalsIgnoreCase("y"));
  } catch (Exception e) {
   e.printStackTrace();
   System.out.println("输入异常，请正确输入后缀表达式，并以空格区分");
  }
 }
}
下面对一些用的并不熟练的方法做下记录：
1.charAt(int index)
    返回指定所引出的char值。索引范围从0 -- length() -1。序列的第一个char值在索引0处，第二个索引在1处，以此类推。
2.intValue()
    将Integer类型转化为int类型
    这时候就不得不提到另一个方法：valueOf()，是将基本数据类型转化为String的static方法，有多个重载方法。
    String.valueOf(boolean b) : 将 boolean 变量 b 转换成字符串
    String.valueOf(char c) : 将 char 变量 c 转换成字符串
    String.valueOf(char[] data) : 将 char 数组 data 转换成字符串
    String.valueOf(char[] data, int offset, int count) :
    将 char 数组 data 中 由 data[offset] 开始取 count 个元素 转换成字符串
    String.valueOf(double d) : 将 double 变量 d 转换成字符串
    String.valueOf(float f) : 将 float 变量 f 转换成字符串
    String.valueOf(int i) : 将 int 变量 i 转换成字符串
    String.valueOf(long l) : 将 long 变量 l 转换成字符串
    String.valueOf(Object obj) : 将 obj 对象转换成 字符串, 等于 obj.toString() 
</strong></span>

原文：http://blog.csdn.net/qq_21394609/article/details/44871259