Skip to content

Latest commit

 

History

History
388 lines (296 loc) · 9.89 KB

3.stack.md

File metadata and controls

388 lines (296 loc) · 9.89 KB

栈

栈和队列的出入操作一样，都是逻辑上的移动

只不过换成栈顶指针上移或者下移

深入理解栈结构

引入 ：栈适合解决什么问题？

LEETCODE 20 括号匹配问题

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

推导为何要用栈来解决

难点是三种括号，我们不妨变成一种括号来思考，只有()的话问题就变成了:

  1. 任意一个位置num( >= num)
  2. 最后一个位置num( = num)
  3. 所以只需记录lnum和rnum的数量即可
bool is_vaild(char *s) {
    int lnum = 0, rnum = 0;
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        switch(s[i]) {
            case '(' : lnum += 1; break;
            case ')' : rnum += 1; break;
            defaut : return false;
        }
        if (lnum >= rnum) continue;
        return fasle;
    }
    return (lnum == rnum);
}

优化

但是到这里发现其实不用两个变量，只要一个变量记录lnum和rnum的差值即可。

有(来了就num += 1，)来了就 num -= 1 每个位置num >= 0, 最后num == 0

对比栈的操作，是不是正好对应了入栈：

栈顶指针 += 1；出栈栈顶指针 -= 1，并且指针 >= 0. 所以一对 () 正好对应了一个完整的事件：

即+1 == 事件发生了， -1 == 事件解决了 大事件和小事件之间又相互嵌套，

即(())可以看做事件与事件之间的完全包含关系

（外面的()看作是大问题，里面的()看成是小问题，需要先解决小问题再解决大问题）这才是本质的思维方式

将大事件拆成若干小事件，小事件解决了最后才解决大事件。 即先发生的事件后被解决，这不就是对应了栈的LIFO么。

由括号的等价变换，得到了一个新的数据结构

所以栈可以解决具有完全包含关系的问题

例子：为什么系统栈可以处理程序？

因为程序的调用也是具有包含关系的

还可以处理表达式

借助vector实现一个栈

// 借助vector实现一个栈
//
class Stack {
public :
    Stack() {}
    void push(int x) {
        data.push_back(x);
        return ;
    }
    void pop() {
        if (empty()) return ;
        data.pop_back();
        return ;
    }
    bool empty() {
        return data.size() == 0;
    }
    int size() {
        return data.size();
    }
    void output() {
        cout << "output : " << endl;
        for (int i = data.size() - 1; i >=0; i--) {
            cout << " " << data[i] << endl;
        }
        return ;
    }

private :
    vector<int> data;
};

int main() {
    Stack s;
    string op;
    int val;
    while (cin >> op) {
        if (op == "push") {
            cin >> val;
            s.push(val);
        } else if (op == "pop") {
            s.pop();
        } else if (op == "size") {
            cout << "size : " << s.size() << endl;
        } else if (op == "output") {
            s.output();
        }
    }
    return 0;
}

用栈顶指针和传统数组实现一个栈

#include <iostream>
#include <vector>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;

// 封装传统的数组 + 指针实现一个栈
// 这里令栈顶指针初值为 -1
// 这样top永远就能指向当前栈顶的元素
// 方便操作
class Stack {
public :
    Stack(int n = 100) {
        top = -1;
        data = new int [n];
    }
    void push(int x) {
        top += 1;
        data[top] = x;
        return ;
    }
    void pop() {
        if (empty()) return ;
        top -= 1;
        return ;
    }
    bool empty() {
        return top == -1;
    }
    int size() {
        return top + 1;
    }
    void output() {
        cout << "output : " << endl;
        for (int i = top; i >= 0; i--) {
            cout << " " << data[i] << endl;
        }
        return ;
    }

private :
    int top;
    int *data;
};

int main() {
    Stack s;
    string op;
    int val;
    while (cin >> op) {
        if (op == "push") {
            cin >> val;
            s.push(val);
        } else if (op == "pop") {
            s.pop();
        } else if (op == "size") {
            cout << "size : " << s.size() << endl;
        } else if (op == "output") {
            s.output();
        }
    }
    return 0;
}

Example:

  1. 函数的系统栈。mian函数最先被执行，最后才结束，中间我们自己写的函数就是小事件。

  2. 递归函数:

  • 语义信息
  • 边界
  • 递归过程

递归一定是向着问题规模更小的问题的，当前递归过程一定是包含了若干没有交集子问题的大问题

题外话: 树的结构，节点是集合，它的子节点是没有交集的真子集，所以也可以用递归。树本身就是具有完全包含关系的一种结构

回到本题，形如({)} 的是不行的，也就是部分包含关系。所以必须是完全包含关系，只需一个栈，如果是左括号就入， 右括号就比较和栈顶元素是否匹配，匹配就弹，不匹配就return false。

栈的应用

场景一：OS中的线程栈

​ 一个进程可以包含多个线程，在这个由若干线程组成的线程空间中，我们定义的诸多函数中的变量，就是存放在线程空间即线程栈中的。入栈和弹栈的顺序和数据被定义的顺序有关。

上一节的线程池就是在线程空间中的

image-20221129162410689

程序的局部变量就都是存在系统栈（线程栈）中的

可以用ulimit -a来查看线程栈的大小，为

❯ ulimit -a
-t: cpu time (seconds)              unlimited
-f: file size (blocks)              unlimited
-d: data seg size (kbytes)          unlimited
-s: stack size (kbytes)             8176
-c: core file size (blocks)         0
-v: address space (kbytes)          unlimited
-l: locked-in-memory size (kbytes)  unlimited
-u: processes                       1333
-n: file descriptors                256

即8MB，也就是int型数组最多开200w个，超过了就爆栈了。

另外多线程是非常占据系统空间的，一个线程就要8MB，1024个就是8GB了

场景二：表达式求值

image-20221129163433937

​

image-20221129163606520

上图是一个乘法表达式，为什么叫乘法表达式呢，明明他也有加法

因为乘法是最后计算的（计算时优先级最低的运算符）

括号里的加法是先行进行计算的

具有完全包含的事件关系

实际上递归解决问题和用栈来解决问题是没区别的，递归函数的调用要通过系统栈来实现。而用栈相当于我们自性模拟系统栈在计算时，优先级越低的操作符越往后算。因为计算表达式的值是一个又一个具有相同解决方式的字问题，所以可以用递归或者栈的思想来解决。

实现技巧：设置计算运算符优先级：

伪代码思路：

input: string a;
function calc(string a, int left, int right) {
    for (operators in a) {
    	if (piror(current_operator) <= piror(pre_operator)) pre_operator = current_operator; 
        // renew the lowest operator
	}
    for (nums in a) num = nums;
    // now we get num and operators
    // all we have to do is to divide them into two sub_expressions and calculate them
    return calc(sub_expression);
    return calc(another sub_expression);
    calculate expression value: 
    	return nums * nums or nums / nums or nums - nums or nums + nums;
}

实现技巧：计算运算符优先级：

switch (s[i]) {
            case '+':
            case '-': cur_pri = temp + 1; break;
            case '*':
            case '/': cur_pri = temp + 2; break;
        // 乘除比加减优先级高
            case '(': temp += 100; break;
        // 遇到左括号优先级就*100， 括号内优先级最高
            case ')': temp -= 100; break;
        // 遇到右括号优先级就回去
        }
        if (cur_pri < pri) pri = cur_pri, pos = i;

完整代码：

int calc(char *s, int l, int r) {
    // op 是最低优先级运算符位置
    // pri 是最高优先级
    // cur_pri 是当前运算符的优先级
    // temp 是由括号增加的优先级
    int op = -1, pri = 10000 - 1, cur_pri, temp = 0;
    for (int i = l; i <= r; i++) {
        cur_pri = 10000;
        switch (s[i]) {
            case '+' :
            case '-' : cur_pri = 1 + temp; break;
            case '*' :
            case '/' : cur_pri = 2 + temp; break;
            case '(' : temp += 100; break;
            case ')' : temp -= 100; break;
        }
        if (cur_pri <= pri) {
            pri = cur_pri;
            op = i;
        }
    }
    // 字符串转整形
    if (op == -1) {
        int num = 0;
        for (int i = l; i <= r; i++) {
            if (s[i] < '0' || s[i] > '9') continue;
            // atoi
            num = num * 10 + (s[i] - '0');
        }
        return num;
    }
    // 分治 + 递归进行运算符的提取
    int a = calc(s, l, op - 1);
    int b = calc(s, op + 1, r);
    switch (s[op]) {
        case '+' : return a + b;
        case '-' : return a - b;
        case '*' : return a * b;
        case '/' : return a / b;
    }
    return 0;
}

int main() {
    char s[100];
    while (~scanf("%[^\n]s", s)) {
        getchar();
        printf("%s = %d\n", s, calc(s, 0, strlen(s) - 1));
    }
    return 0;
}