java中的堆和栈是什么数据结构(java栈的应用数据结构)

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

本文主要讲解“如何在java数据结构中应用栈”。感兴趣的朋友不妨看看。本文介绍的方法简单、快速、实用。让边肖带你学习“如何在java数据结构中应用栈”!

1.声明堆栈接口堆栈

packagech05

publicinterfaceSStackT {

booleanisEmpty();//确定堆栈是否为空。

void push(Tx);//元素X放在堆栈上

tpop();//弹出并返回堆栈的顶部元素。

tpeek();//返回栈顶元素,但不弹出栈。

}2.定义顺序堆栈类SeqStackT,它包括两个私有成员变量:数据元素的对象数组和顶部元素的下标。构造方法可以用大小实例化空的顺序栈,调用类中的成员方法实现顺序栈的堆叠、堆叠和获取顶部元素的操作,重写toString()方法获取顺序栈的字符串描述。

packagech05

public class seqstacktimplements packt {

object[]元素;

inttop

//构造方法,创建一个空堆栈,存储容量大小

public seqstack(int size){ 0

element=NewObject[size];

top=-1;

}

//确定堆栈是否为空。

@覆盖

public booleanisempty(){ 0

return top==-1;

}

//元素X放在堆栈上

@覆盖

public void push(Tx){ 0

if(x==null){ 0

返回;

}

//如果堆栈已满,请扩展堆栈容量。

if(this . top==element . length-1){ 0

object[]temp=this . element;

element=NewObject[temp . length * 2];

for(inti=0;itemp.lengthI){ 0

元素[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;
    }
}

3.定义结点类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);
    }
}

4.  定义链式栈类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));
	}
}

6.表达式求值(后缀表达式):

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数据结构中栈怎么应用

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

内容来源网络,如有侵权,联系删除,本文地址:https://www.230890.com/zhan/155204.html

(0)

相关推荐

  • 吉吉国王是什么梗,嘉吉公司的嘉吉优势是什么

    技术吉吉国王是什么梗,嘉吉公司的嘉吉优势是什么供应链管理 供应链管理概念的产生和发展与信息技术的应用密不可分吉吉国王是什么梗。可以说没有当今高速发展的信息技术,供应链管理就不可能实施。 加强物流 对于嘉吉公司来说,

    生活 2021年10月29日
  • 使用Ubuntu自带远程桌面

    技术使用Ubuntu自带远程桌面 使用Ubuntu自带远程桌面背景
    工作总偶尔需要使用到图形界面调试,对于不支持x11转发的程序无法依靠ssh -X实现,需要借助远程桌面工具。
    常用的平台包括 向日葵

    礼包 2021年11月7日
  • 山药鸡蛋饼的做法,山药糯米粉鸡蛋怎样做好吃

    技术山药鸡蛋饼的做法,山药糯米粉鸡蛋怎样做好吃你好非常感谢你提的问题山药鸡蛋饼的做法,是我的回答希望可以解决你的问题,首先我们先准备一些山药,糯米,黑芝麻,红枣,红糖,鸡蛋。然后把山药给清洗干净,再清洗干净以后我们把山药

    生活 2021年10月24日
  • 石蕊的化学式,紫色石蕊溶液与稀盐酸反应方程式

    技术石蕊的化学式,紫色石蕊溶液与稀盐酸反应方程式紫色石蕊作为酸碱指示剂的原因是电离平衡原理石蕊的化学式,不是化学方程式。石蕊是蓝紫色粉末,它是一个比较复杂的化合物。是从植物中提取得到的蓝色色素,能部分地溶解于水而显蓝色。

    生活 2021年10月28日
  • 苹果Mac从睡眠模式唤醒后 Wi-Fi 无法连接如何解决

    技术苹果Mac从睡眠模式唤醒后 Wi-Fi 无法连接如何解决 苹果Mac从睡眠模式唤醒后 Wi-Fi 无法连接如何解决苹果Mac从睡眠模式唤醒后 Wi-Fi 无法连接如何解决如果您的 Mac 在从睡眠模

    礼包 2021年11月14日
  • 如何在费奥里启动板上将BSP应用程序配置为切片

    技术怎么将BSP应用配置成Fiori Launchpad上的一个tile本篇内容介绍了“怎么将BSP应用配置成Fiori Launchpad上的一个tile”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,

    攻略 2021年12月24日