简介

如果理解了 vector，再学习接下来的栈和队列就会比较轻松。

STL 栈 ( std::stack ) 是一种后进先出 (Last In, First Out) 的容器适配器，仅支持查询或删除最后一个加入的元素（栈顶元素），不支持随机访问，且为了保证数据的严格有序性，不支持迭代器。

概念不好理解，但是总结出 stack 重要的 3 个方法，其实就对应着简单的数组操作。

  • push : 在数组末尾插入元素
  • top: 获取数组末尾的元素
  • pop: 删除末尾的元素

为了帮助理解，可以用 vector 模拟栈的行为。

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  5. template <typename T>
  6. class stack {
  7.    private:
  8.     vector<int> data;
  10.    public:
  11.     void push(T value) {
  12.         data.push_back(value);
  13.     }
  15.     T top() {
  16.         return data.back();
  17.     }
  19.     void pop() {
  20.         data.pop_back();
  21.     }
  23.     bool empty() {
  24.         return data.size() == 0;
  25.     }
  26. };
  28. int main() {
  29.     stack<int> s;
  31.     for (int i = 0; i < 5; ++i) {
  32.         s.push(i);
  33.     }
  35.     while (!s.empty()) {
  36.         cout << s.top() << ' ';  // Output: 4 3 2 1 0
  37.         s.pop();
  38.     }
  40.     return 0;
  41. }

使用

导入 <stack> 头文件，体验一下 STL 提供的栈：（其实和自己写的也没什么区别）

  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. using namespace std;
  6. int main() {
  7.     stack<int> s;
  9.     for (int i = 0; i < 5; ++i) {
  10.         s.push(i);
  11.     }
  13.     while (!s.empty()) {
  14.         cout << s.top() << ' ';
  15.         s.pop();
  16.     }
  18.     return 0;
  19. }

综合案例

利用 逆波兰表达式 求解表达式

  1. #include <iostream>
  2. #include <stack>
  3. #include <string>
  4. #include <vector>
  5. using namespace std;
  7. void calc(stack<int> &nums, stack<char> &ops) {
  8.     int y = nums.top();
  9.     nums.pop();
  11.     int x = nums.top();
  12.     nums.pop();
  14.     char op = ops.top();
  15.     ops.pop();
  17.     if (op == '+')
  18.         nums.push(x + y);
  19.     else if (op == '-')
  20.         nums.push(x - y);
  21.     else if (op == '*')
  22.         nums.push(x * y);
  23.     else
  24.         nums.push(x / y);
  25. }
  27. // 运算符优先级
  28. int p(char op) {
  29.     if (op == '*' || op == '/') return 1;
  30.     return 0;  // + -
  31. }
  33. int main() {
  34.     // string s = "9 + (3 - 1) * 3 + 10 / 2";
  35.     string s = "1+(2*3-6/4*(2-1))*5";
  36.     stack<int> nums;
  37.     stack<char> ops;
  38.     int i = 0, n = s.size();
  39.     while (i < n) {
  40.         if (s[i] == ' ') {
  41.             ++i;
  42.             continue;
  43.         }
  44.         if (isdigit(s[i])) {
  45.             int num = s[i++] - '0';
  46.             while (i < n && isdigit(s[i])) {
  47.                 num = num * 10 + s[i++] - '0';
  48.             }
  49.             nums.push(num);
  50.         } else if (s[i] == '(') {
  51.             ops.push(s[i++]);
  52.         } else if (s[i] == ')') {
  53.             while (ops.top() != '(') {
  54.                 calc(nums, ops);
  55.             }
  56.             ops.pop();  // pop '('
  57.             ++i;
  58.         } else {
  59.             if (ops.empty() || ops.top() == '(') {
  60.                 ops.push(s[i++]);
  61.             } else {
  62.                 while (!ops.empty() && ops.top() != '(' && p(s[i]) <= p(ops.top())) {
  63.                     calc(nums, ops);
  64.                 }
  65.                 ops.push(s[i++]);
  66.             }
  67.         }
  68.     }
  70.     while (!ops.empty()) {
  71.         calc(nums, ops);
  72.     }
  74.     cout << nums.top() << endl;
  76.     return 0;
  77. }

思路二：递归处理括号

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. // string s = "9+(3-1)*3+10/2";
  5. char s[1000];
  6. int i = 0, len;
  8. // priority
  9. int level(char op) {
  10.     if (op == '*' || op == '/') return 2;
  11.     return 1;
  12. }
  14. void pop(stack<int> &nums, stack<char> &ops) {
  15.     int y = nums.top();
  16.     nums.pop();
  17.     int x = nums.top();
  18.     nums.pop();
  19.     char op = ops.top();
  20.     ops.pop();
  21.     if (op == '+')
  22.         nums.push(x + y);
  23.     else if (op == '-')
  24.         nums.push(x - y);
  25.     else if (op == '*')
  26.         nums.push(x * y);
  27.     else
  28.         nums.push(x / y);
  29. }
  31. int calc() {
  33.     // number stack
  34.     stack<int> nums;
  36.     // operator stack
  37.     stack<char> ops;
  39.     while (i < len && s[i] != ')') {
  40.         if (isdigit(s[i])) {
  41.             int num = s[i] - '0';
  42.             while (isdigit(s[++i])) {
  43.                 num = num * 10 + s[i] - '0';
  44.             }
  45.             nums.push(num);
  46.         } else if (s[i] == '(') {
  47.             ++i;  // skip '('
  48.             int sub = calc();
  49.             nums.push(sub);
  50.             ++i;  // skip ')'
  51.         } else {
  52.             while (!ops.empty() && level(s[i]) <= level(ops.top()))
  53.                 pop(nums, ops);
  54.             ops.push(s[i]);
  55.             ++i;  // skip current operator
  56.         }
  57.     }
  59.     while (!ops.empty())
  60.         pop(nums, ops);
  62.     return nums.top();
  63. }
  65. int main() {
  66.     cin >> s;
  67.     len = strlen(s);
  68.     cout << calc() << endl;
  69.     return 0;
  70. }