栈的两种实现方法及用于算数运算

栈是一种先进后出的数据结构，这一系列的实现过程中涉及到了泛型。

泛型：集合类的抽象数据类型的一个关键特性就是我们应该可以用他们存储任意类型的数据，Java就有一种特别的机制能够实现这一点。它被称为泛型，也叫作参数化类型在每份API中，类名后的<Item>记号将Item定义为一个类型参数，它是一个象征性的占位符，表示用例将会使用的某种数据类型。可以将Stack<Item>理解为某种元素的栈。在实现Stack时我们并不知道Item的具体类型，但是用例可以用我们的栈处理任意类型的数据。因为在创建栈的时候，用例会提供一种具体的数据类型：我们可以讲Item替换为任意引用数据类型（只要是Item出现的地方）。

例如下边的用例中我们创建的整型（Integer）Stack<Integer>s = new Stack<Integer>(10)的栈，我们也可以通过这样的方式创建其他类型的栈。

1、顺序结构实现代码：

package stack;

public class Stack<Item> { //声明为泛型
    /*----------循环实现-----------*/
    private Item[] data;
    private int top;
    public Stack(int n) {
        data = (Item[])new Object[n];//数组转换为泛型,初始化栈容量为n
        top = -1; //作为栈顶，-1表示栈空
    }
    
    public void push(Item item) {//入栈
        if(top == data.length-1){//top的值和数组的下标一致，如过top值和数组的最大容量相等,栈满
            resize(2*data.length);
            data[++top] = item;
        }else{
            top = top + 1; //栈顶+1
            data[top] = item;//元素入栈
        }    
    }
    
    public Item pop() {//出栈
        if(top == -1){
            System.out.println("栈为空！没有元素可出栈");
            return null; //如果栈为空返回null
        }
        else{
            Item item = data[top]; //如果栈不空，返回栈顶元素，然后栈顶-1
            data[top]  = null;//避免对象游离
            top = top -1;
            if(top > 0 && top == (data.length-1) / 4) {
                resize(data.length/2);
            }
            return item;
        }
        
    }
    
    public boolean isEmpty() {//判断是否栈空
        return top == -1? true:false;
    }
    
    public int size() { //返回栈的长度
        return top+1;
    }
    
    public void clear() {//清空栈
        top = -1;
    }
    
    public void resize(int max) {
        //将大小为top<=max的栈移动到新的大小为max的数组中
        Item[] temp = (Item[])new Object[max];
        for(int i = 0; i <= top; i++) {
            temp[i] = data[i];
        }
        data = temp;
    }
public static void main(String[] args) {
        Stack<Integer>s = new Stack<Integer>(10);
        for(int i = 1; i <= 10; i++) {
            s.push(i);
        }
        for(int i = 1; i <= 10; i++) {
            System.out.print(s.pop() + " ");
        }
        
    }
}

输出结果

10 9 8 7 6 5 4 3 2 1 

2、链式结构实现

package stack;

import java.util.Iterator;

public class Stack<Item> { //声明为泛型
    /*----------链表实现-------------*/
    private Node first;//栈顶（最近添加的元素）
    private int N; //元素数量
    private class Node{//定义了节点嵌套类
        Item item;
        Node next;
    }
    public boolean isEmpty() {
        return first == null?true:false;
    }
    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
    public Item pop() {
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }
    public int size() {
        return N;
    }
    public static void main(String[] args) {
        Stack<Integer>s = new Stack<Integer>();
        for(int i = 1; i <= 10; i++) {
            s.push(i);
        }
        System.out.println("栈长度为:" + s.size());
        System.out.print("出栈：");
        for(int i = 1; i <= 10; i++) {
            System.out.print(s.pop() + " ");
        }
    }
}

输出结果

栈长度为:10
出栈：10 9 8 7 6 5 4 3 2 1 

3、算数求表达式值《算法》(第4版)

例如：表达式( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) )，怎么样才能够计算一个字符串表达式的值，有一个很简单的算法，是E.W.Dijkstra发明的，即用两个栈（一个用来存运算符、一个用来存操作数）。
表达式一般由括号、运算符、操作符（数字）组成。我们可以通过以下步骤，从左到右依次将表达式分解开并入栈
（1）将操作数压入操作数栈
（2）将运算符压入运算符栈
（3）忽略左括号
（4）在遇到右括号时，弹出一个运算符，弹出所需的操作数，并将运算符和操作数的运算结果压入操作数栈。
实现代码：

package stack;

public class Demo {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Stack<String> ops = new Stack<String>();//运算符栈
        Stack<Double> vars = new Stack<Double>();//数据栈
        String s = "(1+((2+3)*(4*5)))";
        for(int i = 0; i < s.length(); i++) {
            String s1 = s.substring(i, i+1);//截取字符串的每一个字符
            if(s1.equals("(")) ; //如果为左括号则忽略
            /*-----如果为运算符则压入运算符栈-----*/
            else if(s1.equals("+")) ops.push(s1);
            else if(s1.equals("-")) ops.push(s1);
            else if(s1.equals("*")) ops.push(s1);
            else if(s1.equals("/")) ops.push(s1);
            //else if(s1.equals("sqrt")) ops.push(s1);//用这种方式截取，不能得到sqrt
            else if(s1.equals(")")) {//如果为字符为")",弹出运算符和操作数，计算结果并压入数据栈
                String op = ops.pop(); //弹出运算符
                double v = vars.pop(); //弹出第一个操作数
                if (op.equals("+")) v = vars.pop() + v; //弹出第二个操作数和进行相应运算
                else if(op.equals("-")) v = vars.pop() - v;
                else if(op.equals("*")) v =vars.pop() * v;
                else if(op.equals("/")) v =vars.pop() / v;
                //else if(op.equals("sqrt")) v =Math.sqrt(v);
                vars.push(v);  //将计算结果压入数据栈
            }
            else vars.push(Double.parseDouble(s1)); //如果既不是运算符也不是括号，将他作为double类型压入数据栈
        }
        System.out.println(vars.pop());
    }

}

输出结果：101.0
充分理解了栈的特性（先进后出），那么这段代码以及具体过程就好解释了