java数据结构中栈怎么应用

本篇内容主要讲解“java数据结构中栈怎么应用”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“java数据结构中栈怎么应用”吧!

声明一个栈接口SStack

package ch05; public interface SStack <T>{    boolean isEmpty();  // 判断栈是否为空    void push(T x);// 元素x入栈    T pop();// 出栈，返回栈顶元素    T peek();// 返回栈顶元素，但不出栈}

 2. 定义顺序栈类SeqStack<T>，包括数据元素的对象数组和栈顶元素下标两个私有成员变量，构造方法可实例化容量为size大小的空顺序栈，调用类中成员方法实现顺序栈的入栈、出栈、获取栈顶元素等操作，重写toString()方法获取顺序栈的字符串描述。

package ch05; public class SeqStack <T> implements SStack<T>{    Object[] element;    int top;    // 构造方法，创建一个空栈，存储容量大小size    public SeqStack(int size){        element=new Object[size];        top=-1;    }    // 判断栈是否为空    @Override    public boolean isEmpty() {        return top==-1;    }     // 元素x入栈    @Override    public void push(T x) {        if (x==null){            return;        }        // 若栈满，则扩充栈容量        if (this.top==element.length-1){            Object[] temp=this.element;            element=new Object[temp.length*2];            for (int i=0;i<temp.length;i++){                element[i]=temp[i];            }        }        //入栈        this.element[++top]=x;    }     // 出栈，返回栈顶元素    @Override    public T pop() {        if (top!=-1){            return (T) this.element[this.top--];        }        return null;    }    // 返回栈顶元素，但不出栈    @Override    public T peek() {        if (top!=-1){            return (T) this.element[this.top];        }        return null;    }    // 返回顺序栈中所有元素的描述字符串，形式为"（,）"，覆盖Object类的toString()方法    public String toString(){// 自栈顶输出到栈底        String str="";        if (top>=0){            str="(";            for (int i=top;i>=0;i--){                str+=element[i]+",";            }            str=str.substring(0,str.length()-1);            str+=")";        }else {//空栈            str="()";        }        return str;    }}

定义结点类node<T>，包括数据域和地址域两个成员变量，构造方法实例化结点，重写toString()方法获取结点的字符串描述。

package ch05; public class Node <T>{    public T data;    public Node<T> next;     public Node(T data, Node<T> next) {        this.data = data;        this.next = next;    }    public Node(){        this(null,null);    }}

  定义链式栈类LinkedStack<T>：

package ch05; public class LinkedStack<T> implements SStack<T>{    private Node<T> top;     public LinkedStack() {        top=new Node<>();    }     @Override    public boolean isEmpty() {        return top.next==null ? true:false;    }     @Override    public void push(T x) {        if (x==null){            return;        }        //生成新结点        Node<T> q=new Node<>(x,null);        q.next=top.next;        top.next=q;    }     @Override    public T pop() {        T elem=null;        if (top.next!=null){            elem=top.next.data;            top.next=top.next.next;        }        return elem;    }     @Override    public T peek() {        T elem=null;        if (top.next!=null){            elem=top.next.data;        }        return elem;    }    // 返回顺序栈中所有元素的描述字符串，形式为"（,）"，覆盖Object类的toString()方法    public String toString(){        String str="";        Node<T> p=top.next;        if (p!=null){            str="(";            while (p!=null){                str+=p.data+",";                p=p.next;            }            str=str.substring(0,str.length()-1);            str+=")";        }else {            str="()";        }        return str;    }}

 5.括号匹配

package ch07; import java.util.Scanner; public class Bracket {// 括号匹配public static String isMatched(String infix) {SeqStack<Character> stack = new SeqStack<Character>(infix.length());for (int i = 0; i < infix.length(); i++) {char ch = infix.charAt(i);switch (ch) {case '(':stack.push(ch);break;case ')':if (stack.isEmpty() || !stack.pop().equals('(')) {return "expect (";}}}return stack.isEmpty() ? "" : "expect )";} // 测试括号匹配算法public static void main(String[] args) {// 括号匹配Scanner r = new Scanner(System.in);System.out.print("输入括号表达式：");String infix = r.nextLine();System.out.println(isMatched(infix));}}

表达式求值（后缀表达式）：

package ch05; import java.util.Scanner; public class ExpressionPoland {    // 括号匹配    public static String isMatched(String infix) {        SeqStack<Character> stack = new SeqStack<Character>(infix.length());        for (int i = 0; i < infix.length(); i++) {            char ch = infix.charAt(i);            switch (ch) {                case '(':                    stack.push(ch);                    break;                case ')':                    if (stack.isEmpty() || !stack.pop().equals('(')) {                        return "expect (";                    }            }        }        return stack.isEmpty() ? "" : "expect )";    }    // 将中缀表达式转换为后缀表达式    public static StringBuffer toPostfix(String infix){        SeqStack<Character> stack=new SeqStack<Character>(infix.length());        StringBuffer postfix=new StringBuffer(infix.length()*2);        int i=0;        System.out.println("\n求后缀表达式过程：");        System.out.println("字符"+"\tstack\t\tpostfix");        while(i<infix.length()){ // 对表达式中的每个字符进行处理            char ch=infix.charAt(i); // 第i个字符            System.out.print(ch+"\t"); // 输出第i个字符            switch(ch){ // 判断字符类别                // +、-运算符                case '+':                case '-':                    // 当栈不空且栈顶运算符优先级高时，包括+、-、*、/                    while(!stack.isEmpty() && !stack.peek().equals('(')){ // 栈中的'('优先级最低                        postfix.append(stack.pop()+" ");  // 将出栈的运算符追加到后缀表达式中（空格间隔）                    }                    stack.push(ch); // 第i个字符入栈                    i++;                    break;                case '*':                case '/':                    // 当栈不空且栈顶运算符优先级高时，包括*、/                    while(!stack.isEmpty() && (stack.peek().equals('*') || stack.peek().equals('/'))){                        postfix.append(stack.pop()+" "); // 将出栈的运算符追加到后缀表达式中（空格间隔）                    }                    stack.push(ch); // 第i个字符入栈                    i++;                    break;                case '(':                    stack.push(ch); // '('入栈                    i++;                    break;                case ')':                    Character out=stack.pop();                    while(out!=null && !out.equals('(')){ // 若干运算符出栈，直到'('出栈                        postfix.append(out+" ");  // 将出栈的运算符追加到后缀表达式中（空格间隔）                        out=stack.pop();                    }                    i++;                    break;                default:                    while(i<infix.length() && ch>='0' && ch<='9'){ // 获取运算的整数                        postfix.append(ch); // 将数字追加到后缀表达式中                        i++;                        if(i<infix.length()){                            ch=infix.charAt(i); // 下一位字符                        }                    }                    postfix.append(" ");  // 运算数以空格间隔            }            System.out.printf("%-18s",stack.toString()); // 输出每个运算符或运算数处理后栈中的内容            System.out.println(postfix);  // 输出每个运算符或运算数处理后的后缀表达式        }        while(!stack.isEmpty()){ // 栈中运算符全部出栈            postfix.append(stack.pop());        }        return postfix;    }     // 计算后缀表达式的值    public static int toValue(StringBuffer postfix){        LinkedStack<Integer> stack=new LinkedStack<Integer>();        int value=0;        System.out.println("\n计算过程：");        for(int i=0;i<postfix.length();i++){            char ch=postfix.charAt(i);            if(ch>='0' && ch<='9'){                String s="";                while(ch!=' '){// 求运算数                    s+=ch;                    i++;                    ch=postfix.charAt(i);                }                stack.push(Integer.parseInt(s)); // 将运算数入栈            }else{                if(ch!=' '){                    int y=stack.pop(); // 第二个运算数                    int x=stack.pop(); // 第一个运算数                    switch(ch){                        case '+':                            value=x+y;                            break;                        case '-':                            value=x-y;                            break;                        case '*':                            value=x*y;                            break;                        case '/':                            value=x/y;                            break;                    }//switch                    // 输出计算表达式                    if(y>=0){                        System.out.println(x+(ch+"")+y+"="+value);                    }else{                        System.out.println(x+(ch+"")+"("+y+")"+"="+value);                    }                    // 计算结果入栈                    stack.push(value);                }            }        }        return stack.pop(); // 返回栈中计算的最终结果    }     // 测试表达式求值算法    public static void main(String[] args) {        Scanner r=new Scanner(System.in);        // 表达式求值        System.out.print("输入表达式：");        String infix = r.nextLine();        String match=isMatched(infix);        if(match.equals("")){// 括号匹配            StringBuffer postfix=toPostfix(infix);            System.out.println("\n后缀表达式:"+postfix);            System.out.println("\n计算结果："+toValue(postfix));        }else{// 括号不匹配            System.out.println("表达式错误："+match);        }    }}

运行结果如下：

到此，相信大家对“java数据结构中栈怎么应用”有了更深的了解，不妨来实际操作一番吧！这里是编程网网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！