侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

数据结构--栈(java实现)

林贤钦
2020-05-01 / 0 评论 / 10 点赞 / 762 阅读 / 0 字
温馨提示:
本文最后更新于 2020-05-09,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

栈(Stack)

  • 栈是一个先入后出(FILO-First In Last Out)的有序列表
  • 栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表,允许插入和删除的一端,为变化的一段,成为栈顶(top),另一端为固定的一段,成为栈底(Bottom)
  • 根据定义可知,最先放入栈中元素在栈底,最后放入元素的在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的最后删除

栈的应用场景:

  1. 子程序的调用:在跳往子程序前,会将下一个指令的地址存入堆栈中,直到子程序执行完后再将地址取出,以回到原来的程序中
  2. 处理递归调用:和子程序的调用类似,只是除了存储下一个指令的地址外,也将参数,区域变量等数据存入堆栈中。
  3. 表达式的转换[中缀表达式转后缀表达式]与求值
  4. 二叉树的遍历
  5. 图形的深度优先搜索法

顺序存储栈的基本操作以及算法实现

基本操作:初始化、判断是否为空、求栈深、读取栈顶元素、出栈/入栈、栈置空等。

数组模拟栈

相关数据
private int maxSize; //栈的大小
private int []stack; //栈的数据
private int top=-1;  //top指向栈顶
数组模拟栈

创建栈的时候必须确定数组的大小,当然如果用链表模拟自然不用,也就没有栈的大小这个了

//构造器
public ArrayStack(int maxSize){
    this.maxSize = maxSize;
    stack = new int[this.maxSize];
}
判断栈空和栈满
  • 栈满 当top等于数组大小-1即top指向数组的最后一个位置
  • 当top等于-1即top指向数组的第一个位置的前一个,即不存在数据
//栈满 
public boolean isFull(){
    return top ==maxSize-1;
}
//栈空
public boolean isEmpty(){
    return top==-1;
}
入栈push

如果栈没满,先top++在加入数据即可

//入栈 push
public void push (int value){
    //先判断栈是否满
    if (isFull()) {
        System.out.println("栈满");
        return;
    }
    stack[++top]=value;
}
出栈pop

如果栈非空,先取出数组,然后top--

//出栈
public int pop(){
    //先判断栈是否为空
    if (isEmpty()){
        //抛出异常
        throw  new RuntimeException("栈空,没有数据~~~~");
    }
    int value = stack[top--];
    return value;
}
遍历栈

从top往下遍历数组

public void list(){
    if (isEmpty()) {
        System.out.println("栈空,没有数据~~~~~~~~~");
        return;
    }
    for (int i = top; i <=0 ; i++) {
        System.out.println("stack["+i+"]="+stack[i]);
    }
}
查看栈顶元素

top不做任何修改

public int peek() {
    return stack[top];
}
查看栈的深度
public int size(){
    return top;
}

链表模拟栈

相关数据
//初始化头节点,头节点不放任何数据
private Node head =new Node(0,"") ;
栈空
//栈空
public boolean isEmpty(){
    return head.next==null;
}
入栈

这里有两种思路,

  1. 第一种直接每次都插在头节点head后面,然后head.next插到新增的位置,对应的出栈就是把这个取出来,然后接回去
  2. 第二种就是每次都加在链表的最后,取出来也是取链表的最后一个数据
public void push (Node node){
    //插在头节点后面,
    Node temp = head.next;
    head.next =node;
    node.next =temp;
}
出栈
public Node pop(){
    if (isEmpty()){
        throw new RuntimeException("栈为空");
    }else{
        Node temp = head.next;//这是要取出的数据
        head.next=head.next.next;
        return temp;
    }
}
遍历栈
public void list(){
    Node temp = head.next;
    while (temp!=null){
        System.out.println(temp);//打印栈
        temp=temp.next;
    }
}
查看栈顶元素
public Node peek(){
    return head.next;
}
查看栈的深度
public int size(){
    int count=0;
    if(head.next=null){
        return count;
    }
    temp=head.next;
    while(true){
        if(temp==null){
            break;
        }
        count++;
        temp=temp.next;
    }
    return count;
}

应用实例:

将中缀表达式转换成后缀表达式

中缀表达式

中缀表达式是符合人类直觉的一种表达方式,其特点是操作符(二元操作符)在中间,操作数在两侧。

例如 3 + 4 , 5 - 6 * 7, (5 - 6) *7等。括号的存在会影响计算步骤的执行。

后缀表达式(逆波兰表达式)

逆波兰表达式是一种十分有用的表达式,它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。

例如(a+b)(c+d)转换为ab+cd+

将中缀表达式转换为后缀表达式

转换步骤如下:

  1. 初始化两个栈:运算符栈s1和储存中间结果的栈s2;
  2. 从左至右扫描中缀表达式;
  3. 遇到操作数时,将其压s2;
  4. 遇到运算符时,比较其与s1栈顶运算符的优先级:
    1. 如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;
    2. 否则,若优先级比栈顶运算符的高,也将运算符压入s1;
    3. 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4-1)与s1中新的栈顶运算符相比较;
  5. 遇到括号时:
    1. 如果是左括号“(”,则直接压入s1;
    2. 如果是右括号“)”,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃;
  6. 重复步骤2至5,直到表达式的最右边;
  7. 将s1中剩余的运算符依次弹出并压入s2;
  8. 依次弹出s2中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式

例如:1+((2+3)×4)-5具体过程,如下表

扫描到的元素s2(栈底->栈顶)s1 (栈底->栈顶)说明
11数字,直接入栈
+1+s1为空,运算符直接入栈
(1+ (左括号,直接入栈
(1+ ( (同上
21 2+ ( (数字
+1 2+ ( ( +s1栈顶为左括号,运算符直接入栈
31 2 3+ ( ( +数字
)1 2 3 ++ (右括号,弹出运算符直至遇到左括号
×1 2 3 ++ ( ×s1栈顶为左括号,运算符直接入栈
41 2 3 + 4+ ( ×数字
)1 2 3 + 4 ×+右括号,弹出运算符直至遇到左括号
-1 2 3 + 4 × +--与+优先级相同,因此弹出+,再压入-
51 2 3 + 4 × + 5-数字
到达最右端1 2 3 + 4 × + 5 -s1中剩余的运算符

因此结果为“1 2 3 + 4 × + 5 -”

代码实现

1、main方法的代码解释

步骤有

1.1 将中缀表达式转换成对应的list集合

1.2 将中缀表达式list集合转换成后缀表达式list集合

1.3 计算结果

    public static void main(String[] args) {
        String expression = "1+((2+3)*4)-5";
        //将中缀表达式转换成对应的list集合
        List<String > inffixExpressionList = toInffixExpressionList(expression);
        System.out.println("中缀表达式对应的list=======》"+inffixExpressionList);
        //将中缀表达式list集合转换成后缀表达式list集合
        List<String> suffixExpression =parseSuffixExpressionList(inffixExpressionList);
        System.out.println("后缀表达式对应的list=======》"+suffixExpression);
        //
        int res = calculate(suffixExpression);
        System.out.println("计算的结果是:" + res);
    }
2、将中缀表达式转换成对应的list集合
private static List<String> toInffixExpressionList(String expression) {
    List<String> list = new ArrayList<>();
    int i=0;//用于遍历
    String str;
    char c ;///遍历到每一个字符,就放入c
    do{
        //如果c是一个数字,就加入list
        if ((c=expression.charAt(i))<48||(c=expression.charAt(i))>57){
            list.add(""+c);
            i++;
        }else {
            //如果是一个数,需要考虑多位数
            str="";
            while (i< expression.length()&&(c=expression.charAt(i))>=48&&(c=expression.charAt(i))<=57){
                str +=c;
                i++;
            }
            list.add(str);
        }
    }while (i<expression.length());
    return list;
}
3、将中缀表达式list集合转换成后缀表达式list集合
private static List<String> parseSuffixExpressionList(List<String> inffixExpressionList) {
    Stack<String> s1 = new Stack<>();//符号栈
    List<String> s2 = new ArrayList<>();// 存储中间结果的list
    inffixExpressionList.stream().forEach(item->{
        //如果是一个数,加入s2
        if (item.matches("\\d+")){
            s2.add(item);
        }else if ( item.equals("(")){
            s1.push(item);
        }else if (item.equals(")")){
            //如果是右括号,则依次弹出s1栈顶的运算符,并压入s2中,直到遇到左括号为止
            while (!s1.peek().equals("(")){
                s2.add(s1.pop());
            }
            s1.pop();//这个是左括号
        }else {
            //当item的优先级小于等于s1栈顶的运算符,将s1栈顶的运算符弹出并且加入s2中,再次比较直到大于
            while (s1.size()!=0&& Operation.getValue(s1.peek())>=Operation.getValue(item)){
                s2.add(s1.pop());
            }
            //还需要将item压入栈中
            s1.push(item);
        }
    });
    while (s1.size()!=0){
        s2.add(s1.pop());
    }
    return s2;
}
4、计算结果
private static int calculate(List<String> list) {
    Stack<String> stack = new Stack<>();
    //遍历list
    list.stream().forEach(item->{
        //这里用正则表达式来取出数
        if (item.matches("\\d+")) {//匹配多位数
            //入栈
            stack.push(item);
        }else {
            //pop 出两个数并运算,在入栈
            int num2 = Integer.parseInt(stack.pop());
            int num1 = Integer.parseInt(stack.pop());
            int res = 0;
            if (item.equals("+")){
                res=num1+num2;
            }else if (item.equals("-")){
                res=num1-num2;
            }else if (item.equals("*")){
                res=num1*num2;
            }else if (item.equals("/")){
                res=num1/num2;
            }else {
                throw  new RuntimeException("运算符有误");
            }
            //把res入栈
            stack.push(""+res);
        }
    });
    return Integer.parseInt(stack.pop());
}
5、其中的运算符优先级简单定义
class Operation{
    private  static int ADD = 1;
    private  static int SUB = 1;
    private  static int MUL = 2;
    private  static int DIV = 2;
    public static int getValue(String oper){
        int result = 0;
        switch (oper){
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("不存在该运算符");
                break;
        }
        return result;
    }
}
10

评论区