栈及其基本应用

2019-07-12T03:36:00

是一种操作受限的线性表,只支持从一端插入和删除。后进先出是它的最大特点。栈既可用数组也可用链表实现,前者叫顺序栈,后者叫链栈,无论哪种,出入栈操作的时间复杂度都是 O(1)。从功能上说,数组和链表都可代替栈,但特定的数据结构是对特定场景的抽象,尽管数组和链表操作灵活,但它们暴露了太多接口,使用时不可控因素增多,自然也就更容易出错。当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性时,就应首选栈这种数据结构。

现实生活中的栈

我们平时放盘子的时候,都是从下往上一个一个放;取的时候从上往下一个一个取,不能从中间任意抽出,这种先进后出的结构便是栈。

顺序栈的实现

class ArrayBasedStack {
    Object[] items;
    int capacity;
    int size;

    public ArrayBasedStack(int capacity) {
        this.items = new Object[capacity];
        this.capacity = capacity;
        this.size = 0;
    }

    // 入栈
    public void push(Object item) {
        // 动态扩容
        if (this.capacity == this.size) {
            this.capacity = this.capacity << 1;
            Object[] newItems = new Object[this.capacity];
            System.arraycopy(items, 0, newItems, 0, this.size);
            /*
            for (int i = 0; i < this.size; i++) {
                newItems[i] = this.items[i];
            }
            */
            this.items = newItems;
        }
        this.items[this.size++] = item;
    }

    // 出栈
    public Object pop() {
        return this.size == 0 ? null : this.items[--this.size];
    }
}

链式栈的实现

class SinglyLinkedListBasedStack {
    SinglyLinkedListNode head;
    int size;

    public void push(Object item) {
        SinglyLinkedListNode current = new SinglyLinkedListNode(item);
        current.next = this.head.next;
        this.head.next = current;
        this.size++;
    }

    public Object pop() {
        SinglyLinkedListNode current = this.head.next;
        if (current != null) {
            this.head.next = this.head.next.next;
        }
        this.size--;
        return current;
    }
}

class SinglyLinkedListNode {
    SinglyLinkedListNode next;
    Object item;

    public SinglyLinkedListNode(Object item) {
        this.item = item;
    }
}

出入栈的时空复杂度分析

对于链式栈,push 操作实际上是链表头插,时间复杂度为 O(1)。pop 操作是删除第一个有效节点,时间复杂度同样为 O(1)。两个操作都未使用额外空间,因此空间复杂度为 O(1)。

对于顺序栈,push 操作在链表满时需要数据搬移,时间复杂度 O(n),空间复杂度 O(n),这是最坏情况。最好情况是数组未满,直接将 item 放入 size 位置,时空复杂度都是 O(1)。pop 操作直接返回 size-1 位置,时空复杂度都是 O(1)。

我们发现,顺序栈的 push 操作,大多数情况下可在 O(1) 时间完成,只有少数情况需要 O(n) 时间,并且它们之间存在时间先后关系,具体是,每 n-1 次 O(1) 操作跟随 1 次 O(n) 操作。在 算法的时空复杂度分析 这篇文章中,我们介绍过,遇到上述情况,在分析平均复杂度时,应使用摊还分析代替平均加权,得到均摊复杂度,并且通常情况下,均摊复杂度等于最好情况复杂度。本例中,将 n 个数据搬移均摊到 n 次上,相当于一次只需一次搬移,均摊复杂度为 O(1),这也更符合较长时间的性能测量。

// 顺序栈 push 操作的时间复杂度
// 第一行为次数
// 第二行为每次的时间复杂度
|-  n  -| 1 |- n-1 -| 1 |- n-1 -|
1,1,...,1,n,1,1,...,1,n,1,1,...,1,...

栈的常规应用

处理函数调用

我们知道,操作系统给每个线程分配了一块独立的内存空间,这块内存空间被组织成栈,用来存储函数调用时的临时变量。每进入一个函数,操作系统便将临时变量作为栈帧入栈,当调用结束返回后,再将该栈帧出栈。通过模拟以下代码的执行过程,可以得到函数调用栈的结构。

int main() {
   int a = 1;
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   return 0;
}

int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}

下图显示了执行到 add 函数时,函数调用栈的栈帧分布情况。

|  ·  |-----
|  ·  |  |
|  ·  |
|sum=0| add
|  x=3|
|  y=5|  |
|  ·  |-----
|  ·  |  |
|  ·  |
|res=0| main
|ret=0|
|  a=1|  |
-----------

为什么函数调用要用 “栈” 来保存临时变量呢?用其他数据结构不行吗?

其实,我们不一定非要用栈来保存临时变量,只不过如果这个函数调用符合后进先出的特性,用栈这种数据结构是最顺理成章的选择。

从调用函数进入被调用函数,对于数据来说,变化的是什么呢?是作用域。所以从根本上,只要能保证每进入一个新的函数,都是一个新的作用域就可以。而要实现它,用栈就非常方便。在进入被调用函数的时候,分配一段栈空间给这个函数的变量,在函数结束的时候,将栈顶复位,正好回到调用函数的作用域内。

浏览器的前进后退

思路:

  1. 初始化两个栈 X 和 Y,把首次浏览的页面压入 X
  2. 当点击后退时,依次从 X 出栈,并将其压入 Y 中
  3. 当点击前进时,依次从 Y 出栈,并将其压入 X 中
  4. 打开新页面时,应清空前进栈 Y
  5. 当 X 中无数据时,则说明没有页面可以后退了
  6. 当 Y 中无数据时,则说明没用页面可以前进了

举例:

  • 打开 A,B,C 三个页面,X 和 Y 的栈帧如下
|C|        | |
|B|        | |
|A|        | |
---        ---
 X          Y
  • 点击两次后退,从 C 退 B 再退到 A 页面
| |        | |
| |        |B|
|A|        |C|
---        ---
 X          Y
  • 点击前进,回到 B 页面
| |        | |
|B|        | |
|A|        |C|
---        ---
 X          Y
  • 打开新页面 D,从逻辑上讲,D 时最新页面,不存在更前面的页面了,需要清空 Y
|D|        | |
|B|        | |
|A|        | |
---        ---
 X          Y

括号匹配

问题:

假设表达式中允许三种括号:圆括号、方括号和大括号。编写一个算法,判断表达式中的各种左括号是否与右括号匹配。例如,输入 2+(3+4)_2+{[3]}-8,输出匹配正确;输入 2+(3+4_[2)+{[3]}-8,输出匹配错误。

思路:

初始化一个栈,从左到右扫描表达式。扫描到左括号时入栈。扫描到右括号时,栈顶弹出,若能匹配,则继续扫描,否则匹配失败。当表达式扫描结束后,若栈为空,则匹配成功,否则匹配失败。

复杂度:

时间复杂度 O(n),空间复杂度 O(n)。

实现:

public boolean braceMatching(String expression) {
    ArrayBasedStack<Character> stack = new ArrayBasedStack<>(8);
    for (int i = 0; i < expression.length(); i++) {
        char c = expression.charAt(i);
        switch (c) {
            case '(':
            case '[':
            case '{':
                stack.push(c);
                break;
            case ')':
                if (stack.pop() != '(') {
                    return false;
                }
                break;
            case ']':
                if (stack.pop() != '[') {
                    return false;
                }
                break;
            case '}':
                if (stack.pop() != '{') {
                    return false;
                }
                break;
        }
    }
    if (stack.size != 0) {
        return false;
    }
    return true;
}

算术表达式求值

问题:

输入算术表达式,输出其运算结果。为了简化问题,我们只考虑 +-*/ 四种运算,他们的优先级规则如下:

  1. 先乘除,后加减
  2. 从左算到右
  3. 先括号内,再括号外

算符优先法

思路:

  1. 设置两个工作栈,一个存储操作数,另一个存储操作符
  2. 自左向右扫描算术表达式,遇到操作数直接入操作数栈
  3. 若遇到操作符,则根据算符优先规则决定下一步操作:若优先级高于栈顶操作符则入栈。否则,弹出栈顶算符,并从操作数栈弹出两个操作数计算,将计算结果入操作数栈。继续与栈顶操作符比较优先级,若相等或低于,则再计算,直至大于之,此时方可将操作符入栈
  4. 左括号一定入栈,且优先级低于后续任何算符,即优先级高于括号前,低于括号中。右括号一定出栈计算,直至遇到左括号,即低于括号中
  5. 扫描完毕后,由于剩余算符的优先级相同,直接依次出栈计算,结果入操作数栈,当操作符栈空时,计算结束

复杂度:

时间复杂度 O(n),空间复杂度 O(n)。

实现:

public class StackReview {
    public static void main(String[] args) {
        String arithmeticExpression = "2-6/(1+3*2-1)+(4+4)*5+1";
        System.out.println(arithmeticExpression + " = " + new StackReview().calculate(arithmeticExpression));
    }

    public double calculate(String arithmeticExpression) {
        SinglyLinkedListBasedStack<Double> operands = new SinglyLinkedListBasedStack<>();
        SinglyLinkedListBasedStack<Character> operators = new SinglyLinkedListBasedStack<>();
        for (int i = 0; i < arithmeticExpression.length(); i++) {
            char c = arithmeticExpression.charAt(i);
            switch (c) {
                case '(':
                    operators.push(c);
                    break;
                case '+':
                case '-':
                case '*':
                case '/':
                    while (operators.size > 0 && !this.isGreater(c, operators.getTop())) {
                        operands.push(calSubExpress(operands.pop(), operands.pop(), operators.pop()));
                    }
                    operators.push(c);
                    break;
                case ')':
                    while (operators.getTop() != '(') {
                        operands.push(calSubExpress(operands.pop(), operands.pop(), operators.pop()));
                    }
                    // '()' 匹配完毕,'(' 出栈
                    operators.pop();
                    break;
                default:
                    operands.push((double) (c - '0'));
                    break;
            }
        }
        // 剩余算符优先级相同,直接依次出栈
        while (operators.size > 0) {
            operands.push(calSubExpress(operands.pop(), operands.pop(), operators.pop()));
        }
        return operands.pop();
    }

    public boolean isGreater(char operator1, char operator2) {
        if (operator1 == '/' || operator2 == '(') {
            // 自左向右,/ 比 * 优先级高。括号里面必须先算
            return true;
        } else if (operator1 == '-' && operator2 == '+') {
            // 自左向右,- 比 + 优先级高
            return true;
        } else if (operator1 == '*' && (operator2 == '+' || operator2 == '-')) {
            return true;
        }
        return false;
    }

    public double calSubExpress(double operand1, double operand2, char operator) {
        double result = 0;
        switch (operator) {
            case '+':
                // 第二个数在前,因为它先入栈
                result = operand2 + operand1;
                break;
            case '-':
                result = operand2 - operand1;
                break;
            case '*':
                result = operand2 * operand1;
                break;
            case '/':
                result = operand2 / operand1;
                break;
        }
        return result;
    }
}

后缀表达式法

步骤:

  1. 将中缀表达式转为后缀
  2. 根据后缀表达式求值

后缀的定义:

后缀表达式,指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。

举例:

  1. 前缀表达式:操作符在操作数的前面,比如 +-543
  2. 中缀表达式:操作符在操作数的中间,这也是人类最容易识别的算术表达式 3+4-5
  3. 后缀表达式:操作符在操作数的后面,比如 34+5-

中缀转后缀:

  1. 设置两个栈,一个储存算符,另一个储存后缀表达式
  2. 自左向右扫描中缀表达式,遇到数字直接入后缀表达式栈
  3. 遇到操作符,比较其与算符栈顶的优先级:

    1. 若不高于栈顶算符优先级,则栈顶出栈并入后缀表达式栈,继续比较后续栈顶符号,直到遇到低于自己的符号,此时入操作符栈
    2. 高于栈顶算符优先级,直接入操作符栈
    3. 左括号直接入操作符栈
    4. 右括号不入栈,且依次弹出栈内操作符并入后缀表达式栈,直到遇到左括号,将左括号也出栈
  4. 扫描完毕后,将操作符栈依次弹出并压入后缀表达式栈
  5. 逆序输出后缀表达式栈

根据后缀表达式求值:

  1. 设置一个操作数栈
  2. 从左到右扫描后缀表达式,遇到操作数入栈
  3. 遇到算符便从栈中弹出两个操作数计算,结果入栈
  4. 直到算符处理完毕,最后入栈的操作数便是表达式的值

复杂度:

时间复杂度 O(n),空间复杂度 O(n)。

实现:

public class StackReview {
    public static void main(String[] args) {
        String arithmeticExpression = "2-6/(1+3*2-1)+(4+4)*5+1";
        StackReview stackReview = new StackReview();
        StringBuilder suffixExpression = stackReview.InfixToSuffix(arithmeticExpression);
        System.out.println(arithmeticExpression + " = " + stackReview.calculateWithSuffixExpression(suffixExpression));
    }

    public double calculateWithSuffixExpression(StringBuilder suffixExpression) {
        ArrayBasedStack<Double> operands = new ArrayBasedStack<>(8);
        for (int i = suffixExpression.length() - 1; i >= 0; i--) {
            char c = suffixExpression.charAt(i);
            switch (c) {
                case '+':
                case '-':
                case '*':
                case '/':
                    operands.push(this.calSubExpress(operands.pop(), operands.pop(), c));
                    break;
                default:
                    operands.push((double) c - '0');
            }
        }
        return operands.pop();
    }

    public StringBuilder InfixToSuffix(String arithmeticExpression) {
        ArrayBasedStack<Character> operators = new ArrayBasedStack<>(8);
        ArrayBasedStack<Character> suffixExpression = new ArrayBasedStack<>(8);
        for (int i = 0; i < arithmeticExpression.length(); i++) {
            char c = arithmeticExpression.charAt(i);
            switch (arithmeticExpression.charAt(i)) {
                case '(':
                    operators.push(c);
                    break;
                case '+':
                case '-':
                case '*':
                case '/':
                    while (operators.size > 0 && !this.isGreater(c, operators.getTop())) {
                        suffixExpression.push(operators.pop());
                    }
                    operators.push(c);
                    break;
                case ')':
                    while (operators.size > 0 && operators.getTop() != '(') {
                        suffixExpression.push(operators.pop());
                    }
                    operators.pop();
                    break;
                default:
                    suffixExpression.push(c);
            }
        }
        while (operators.size > 0) {
            suffixExpression.push(operators.pop());
        }
        StringBuilder expression = new StringBuilder();
        while (suffixExpression.size > 0) {
            expression.append(suffixExpression.pop());
        }
        return expression;
    }

    public boolean isGreater(char operator1, char operator2) {
        if (operator1 == '/' || operator2 == '(') {
            // 自左向右,/ 比 * 优先级高。括号里面必须先算
            return true;
        } else if (operator1 == '-' && operator2 == '+') {
            // 自左向右,- 比 + 优先级高
            return true;
        } else if (operator1 == '*' && (operator2 == '+' || operator2 == '-')) {
            return true;
        }
        return false;
    }

    public double calSubExpress(double operand1, double operand2, char operator) {
        double result = 0;
        switch (operator) {
            case '+':
                // 第二个数在前,因为它先入栈
                result = operand2 + operand1;
                break;
            case '-':
                result = operand2 - operand1;
                break;
            case '*':
                result = operand2 * operand1;
                break;
            case '/':
                result = operand2 / operand1;
                break;
        }
        return result;
    }
}

JVM 中的栈

JVM 的内存结构大概分为:

  • 堆(Heap):线程共享。所有的对象实例以及数组都要在堆上分配。回收器主要管理的对象
  • 方法区(Method Area):线程共享。存储类信息、常量、静态变量、即时编译器编译后的代码
  • 方法栈(JVM Stack):线程私有。存储局部变量表、操作栈、动态链接、方法出口,对象指针
  • 本地方法栈(Native Method Stack):线程私有。为虚拟机使用到的 Native 方法服务。如 Java 使用 c 或者 c++ 编写的接口服务时,代码在此区运行
  • 程序计数器(Program Counter Register):线程私有。有些文章也翻译成 PC 寄存器(PC Register),同一个东西。它可以看作是当前线程所执行的字节码的行号指示器。指向下一条要执行的指令

参考文献

当前页面是本站的「Baidu MIP」版。发表评论请点击:完整版 »