C/C++教程

4 栈(stack)

本文主要是介绍4 栈(stack),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

4 栈

4.1 实际需求

​ 科学计算器就是用到了栈的原理

在这里插入图片描述

4.2 介绍

  • 英文名为:stack

  • 栈是一个先进后出(First in last out)的有序列表

  • 栈是 限制线性表,元素的插入和删除只能在线性表的同一端进行,允许插入和删除的一端称为变化的一端,是栈顶,另外一端为固定的一端,称为栈底。

  • 根据栈的定义,最先放入栈中的元素在栈底,最后放入栈中的元素在栈顶。最先弹出的元素在栈顶,最后弹出的元素在栈底。

  • 压栈(push)和弹栈(pop)的原理图

在这里插入图片描述

4.3 栈的经典应应用场景

  • 子程序的调用:在调用子程序之前,先将下个指令的地址存入到堆栈中,直到子程序执行完再将地址取出,回到原来的程序之中
  • 处理递归调用:与子程序调用的原理类似,只不过是除了存储下一个指令的地址之外,也将参数,局部变量等数据存入到堆栈中
  • 表达式的转换和求值[中缀表达式转换为后缀表达式]
  • 二叉树的遍历
  • 图形的深度优先(depth-first)搜索法

4.4 栈的实现

4.1 使用数组

class MyStack {
    private int capacity;
    int[] array;
    int pointer = -1;
    public MyStack() { }
    public MyStack(int capacity) {
        this.capacity = capacity;
        this.array = new int[capacity];
    }

    // 压栈的方法(push)
    public void push(int num) {
        if (pointer == capacity - 1) {
            throw new RuntimeException("栈已满,压栈失败");
        } else {
            array[++pointer] = num;
        }

    }

    // 弹栈的方法(pop)
    public void pop() {
        if(pointer == -1) {
            throw new RuntimeException("栈已空,弹栈失败");
        } else {
            array[pointer--] = 0;
        }
    }

    // 遍历栈的方法
    public void printStack(){
        System.out.println("栈中现存的元素为:");
        for (int i = pointer; i >= 0 ; i--) {
            System.out.printf("%d\t", array[i]);
        }
    }
}

4.2 使用单向链表

class StackByList {
    ListNode header = new ListNode(-1);
    int capacity;

    public StackByList() { }
    public StackByList(int capacity) {
        this.capacity = capacity;
    }

    // 获取当前栈中元素的个数
    public int getSize() {
        ListNode p = header;
        int count  = 0;
        while(p.next != null) {
            p = p.next;
            count++;
        }
        return count;
    }

    // 往栈中添加元素的方法
    public void push(ListNode listNode) {
        ListNode p = header;
        if (this.getSize() == capacity)
            throw new RuntimeException("栈已满,无法添加更多的元素");
        listNode.next = p.next;
        p.next = listNode;
    }

    // 移除栈中元素的方法
    public void pop() {
        ListNode p = header;
        if (p.next == null)
            throw new RuntimeException("栈已空,弹栈失败");
        p.next = p.next.next;
    }

    // 打印栈中元素的方法
    public void printStack() {
        ListNode p = header;
        if (p == null || p.next == null)
            System.out.println("当前栈中没有元素");
        p = p.next;
        while (p != null) {
            System.out.printf("%d\t", p.value);
            p = p.next;
        }
    }

}

class ListNode {
    int value;
    ListNode next;

    public ListNode(int value) {
        this.value = value;
    }
    public ListNode(int value, ListNode next) {
        this.value = value;
        this.next = next;
    }

    public ListNode() { }
}

4.4 使用栈完成计算器的实现

4.4.1 思路分析

  • 通过一个指针来扫描这个字符串,遍历我们的表达式

  • 扫描的过程中:

    • 扫描到数字就把它放到数栈中
    • 扫描到是一个符号
      • 如果符号栈为空,就直接入栈
      • 如果符号栈有操作符,当前操作符的优先级小于或者等于栈中的操作符的优先级,就需要从数栈中pop两个数,从符号栈中pop一个符号,进行计算,将得到结果,将结果push入数栈,将当前的符号push进操作符栈;如果当前的操作符的优先级大于栈中操作符的优先级,就直接将操作符压入栈中即可,不需要进行计算
  • 表达式扫描完毕之后,顺序从数栈和符号栈中pop出相应的元素进行运算

  • 最后数栈中只有一个数据,就是这个表达式的结果

4.4.2 代码实现

class NumsComputer{
    // 存操作符的栈
    IntStack operaStack = new IntStack(5);
    // 存操作数的栈
    IntStack numsStack = new IntStack(10);
    // 构造方法
    public NumsComputer() { }
    // 遍历字符串的方法
    public void scanString(String string) {
        char[] chars = string.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] >= 48 && chars[i] <= 57) numsStack.push(chars[i] - '0'); // 将字符型数据转换为整数型存入
            // 在将操作符压入栈中的时候,需要抽象成一个方法
            else if (operaStack.pointer == -1) operaStack.push(chars[i]);   // 符号栈中元素为空
            else pushOperator(chars[i]);
        }
    }

    // 运算方法
    public int compute(){
        while (operaStack.pointer != -1) {
            operate(operaStack, numsStack);
        }
        int result = numsStack.pop();
        return result;
    }

    // 获取符号优先级的方法
    public static int getPriority(int c) {
        if (c == '*' || c == '/') {
            return 1;
        } else return 0;
    }

    // 操作符号压栈的方法
    public void pushOperator(char c) {
        // 如果当前运算符的优先级小于或者等于栈中的优先级
        if (getPriority('c') <= getPriority(operaStack.array[operaStack.pointer])){
            operaStack.push(c);
        } else { operaStack.push(c); } // 当前符号优先级大于栈顶的符号优先级
    }
    // 弹栈进行计算的方法
    public static void operate(IntStack operaStack, IntStack numsStack) {
        // 从数栈中弹出两个元素
        int a = numsStack.pop();
        int b = numsStack.pop();
        // 从运算符栈中弹出一个元素
        int c = operaStack.pop();
        int result = 0;
        switch (c) {
            case '+': result = b + a; break;
            case '-': result = b - a; break;
            case '*': result = b * a; break;
            case '/': result = b / a; break;
        }
        numsStack.push(result);
    }
}

class IntStack {
    private int capacity;
    int[] array;
    int pointer = -1;

    public IntStack() {
    }

    // 获取栈中元素个数
    public int getSize() {
        int count = 0;
        while (array[count] != 0)
            count++;
        return count;
    }

    public IntStack(int capacity) {
        this.capacity = capacity;
        this.array = new int[capacity];
    }

    // 压栈的方法(push)
    public void push(int c) {
        if (++pointer == capacity) {
            throw new RuntimeException("栈已满,压栈失败");
        }
        array[pointer] = c;

    }

    // 弹栈的方法(pop)
    public int pop() {
        if (pointer == -1) {
            throw new RuntimeException("栈已空,弹栈失败");
        } else {
            int c = array[pointer];
            array[pointer--] = 0;
            return c;
        }
    }

    // 遍历栈的方法
    public void printStack() {
        System.out.println("栈中现存的元素为:");
        for (int i = pointer; i >= 0; i--) {
            System.out.print(array[i] + "\t");
        }
    }
}

4.5 三种表达式

4.5.1 前缀表达式

1)概述

  • 前缀表达式又称为波兰表达式
  • 前缀表达式的运算符位于操作数之前
  • 举例:(3 + 4) * 5 - 6 对应的前缀表达式为- * + 3 4 5 6

2)计算机求值

​ 从右至左扫描表达式,遇到数字的时候将数字压入栈中,遇到运算符时,弹出栈顶的两个数,用运算符对他们做相应的计算(栈顶元素和次顶元素),并将结果并入栈中,重复上述过程直到表达式最左端,最后运算的到的值即为表达式的结果。

  • 从右至左扫描,将6、5、4、3压入堆栈
  • 遇到 + 运算符,因此弹出3、4,计算3 + 4的值,将结果7压入栈中
  • 接下来时 * 运算,弹出7 和 5 计算出7 * 5,将结果35压入栈中
  • 最后时 - 运算符,计算出35 - 6的值,得到最终的结果

4.5.2 中缀表达式

1)概述

  • 中缀表达式就是常见的运算表达式,例如(3 + 4) * 5 - 6
  • 中缀表达式的求职是人们最熟悉的,但是中缀表达式对于计算机却是非常棘手。因此在计算中缀表达式的结果时,往往会将中缀表达式转换为其他表达式来操作,一般为后缀表达式。

4.5.3 后缀表达式

1)概述

  • 后缀表达式又称为逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后
  • 举例:(3 + 4) * 5 -6对应的后缀表达式为3 4 + 5 * 6 -

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-fH6ygEAC-1619919934940)(E:\JavaSpace\上课截图\逆波兰表达式.png)]

  1. 计算机求值
  • 从左至右扫描表达式,将3 4压入栈中
  • 遇到+运算符,因此弹出 4 和 3 ,计算出3 + 4的值,再将运算结果7压入栈中
  • 将 5 压入栈中
  • 遇到*运算符,因此将 5 和 7 弹出栈,计算出5 * 7的值,将 35 压入栈中
  • 将 6 压入栈中
  • 最后是 -运算,计算出35 - 6的值,29 即为计算的最终结果

4.6 逆波兰计算器的实现

4.6.1 需求

  • 输入一个后缀表达式,使用栈(stack)计算其结果
  • 支持小括号和多位整数

4.6.2 思路分析

见于4.5.3 2)计算机求值

4.6.3 代码实现

class PolandNotation {
    // 接收用户输入的表达式
    private String expression = null;

    // 创建数栈
    Stack<Integer> numStack = new Stack<>();

    public PolandNotation(String expression) {
        this.expression = expression;
    }

    //扫描表达式的方法
    public void compute() {
        // 将表达式的值转变为一个char数组
        char[] chars = expression.toCharArray();
        int i = 0;
        // 对整个char数组进行遍历
        while (i < chars.length) {
            // 如果扫描的是一个符号
            if (chars[i] < 48 && chars[i] > 32) {
                numStack.push(calculate(chars[i], numStack));
                i++;
            } else if (chars[i] == 32) { i++; } // 扫描到的是一个空格
            else {
                String numString = "";
                while(i < chars.length && chars[i] != 32) {
                    numString = numString + chars[i];
                    i++;
                }
                int num = Integer.parseInt(numString);
                numStack.push(num);
            }
        }

        // 只需要将此时栈中的元素弹出来即可
        int result = numStack.pop();
        System.out.println(result);
    }

    // 弹栈计算的方法
    public int calculate(char operator, Stack<Integer> numStack) {
        // 栈中弹出两个元素
        int num1 = numStack.pop();
        int num2 = numStack.pop();
        int result = 0;
        switch (operator) {
            case '+': result = num2 + num1; break;
            case '-': result = num2 - num1; break;
            case '*': result = num2 * num1; break;
            case '/': result = num2 / num1; break;
        }
        return result;
    }
}

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

1)算法流程

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

在这里插入图片描述

2)实现代码

public char[] transform(String expression){
        // 将这个中缀表达式变为一个char数组
        char[] expressChars = expression.toCharArray();
        // 初始化运算符栈
        Stack<Character> operaStack = new Stack<>();
        // 初始化队列
        CycleQueue numQueue = new CycleQueue(50);
        // 扫描中缀表达式
        int i = 0;
        while (i < expressChars.length) {
            // 如果为扫描到为一个符号
            if (expressChars[i] < 48 && expressChars[i] != ' '){
                // 如果这个符号是左括号或者符号栈为空
                if (expressChars[i] == 40 || operaStack.empty()){
                    operaStack.push(expressChars[i++]);
                } // 符号未右括号的时候将符号栈里的元素弹入到数栈之中
                else if (expressChars[i] == 41) {
                    while (true) {
                        char temp = operaStack.pop();
                        // 碰到左括号后就跳出循环
                        if (temp == 40) break;
                        else {
                            numQueue.add(temp);
                            // 这里往数栈中添加元素之后再添加空格
                            numQueue.add(' ');
                        }
                    }
                    i++;
                }
                // 判断优先级,如果当前符号的优先级大于栈顶符号的优先级,直接入栈
                else if (getPriority(expressChars[i]) > getPriority(operaStack.peek())) {
                    operaStack.push(expressChars[i]);
                    i++;
                } else {
                    // 当前运算符的优先级小于或者等于栈顶
                    while (operaStack.size() != 0 && getPriority(expressChars[i]) <= getPriority(operaStack.peek())) {
                        numQueue.add(operaStack.pop());
                        numQueue.add(' ');
                    }
                    operaStack.push(expressChars[i]);
                    i++;
                }
            } else if (expressChars[i] == 32){
                // 扫描的是一个空格
                i++;
            } else {
                // 扫描的是一个数
                while (i < expressChars.length && expressChars[i] != 32 && expressChars[i] != ')'){
                    numQueue.add(expressChars[i]);
                    i++;
                }
                numQueue.add(' ');
            }
        }
        //将操作符号栈中的元素放到队列中
        while (operaStack.size() != 0) {
            numQueue.add(operaStack.pop());
            numQueue.add(' ');
        }

        // 将队列的元素取出来放到数组中
        return numQueue.toArray();
    }

这篇关于4 栈(stack)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!