hello~ 今天就更了哦~ 来一波奇袭，嘿嘿。

依旧叠甲：

我们学了树，可能对于很多的算法题目来说，已经很好用了，基本上简单一点的算法题，用哈希表、树和数组就可以打遍天下无敌手了，但是我们仍有必要要学习，栈和队列，理由很简单，在理解了栈和队列的情况下，我们在学习一些别的计算机知识会更容易一些。

栈（stack）

我们先从栈讲起，其核心就是一个符合FILO（First In Last Out 先进后出）的特殊数组，其中这个先进后出可以理解成把子弹一颗颗压到弹夹里，但是射击时第一颗子弹是最后一个压进去的，最后一个子弹是第一个压出去的。

但是我们毕竟学的是C++且作为学习阶段没有必要现在去专门的用new啊、size_t啊，去搓出来一个stack，而且搓出来的东西能否在各种场景下使用，用户调用完出现的报错究竟是代码实现问题还是设计问题，这个工程量相对很大。且如果搓一个很简单的stack也没什么意义，因为本质上你实现的是一个不能自由插入删除的数组而已，反而可能会背离我们栈的初衷——更高效的实现算法。绝对！！！不是！！！我要偷懒！！！

栈 stack 的基本操作

push()	入栈 / 压栈：将一个元素 item 添加到栈的顶部。	std::stack::push()
pop()	出栈 / 弹栈：移除栈顶部的元素。注意：此操作通常不返回被移除的元素。	std::stack::pop()
top()	获取栈顶元素：返回栈顶部元素的值，但不移除它。	std::stack::top()
empty()	判空：检查栈是否为空。如果为空，返回 true。	std::stack::empty()
size()	获取大小：返回栈中元素的数量。	std::stack::size()

stack算法

1.括号匹配 (Parentheses Matching)

如果给定了一串字符串，判断该串的括号有几个，括号的使用方式对不对（会不会出现‘)(’的问题）？如果一个个判断出现“（()）”的情况下可能会报错，或者很难处理，这时候我们可以用栈来做匹配

bool isMatched(const string& s) {
    stack<char> st;
    const string left  = "([{";
    const string right = ")]}";
    for (char c : s) {
        if (left.find(c) != string::npos) {          // 左括号
            st.push(c);
        } else if (right.find(c) != string::npos) {  // 右括号
            if (st.empty()) return false;
            char t = st.top(); st.pop();
            if (left.find(t) != right.find(c)) return false;
        }
    }
    return st.empty();
}

2.表达式求值 (Expression Evaluation)

你有想过计算机是怎么理解“2+7/（8-1）”吗？如果对于人类来讲应该是先算小括号，再算除法，最后从左到右相加相减，但是计算机会是这样理解的吗？答案是：不，计算机其实理解四则运算是前缀表达式（波兰表示法）或者后缀表达式（逆波兰表示法）

参考一下这张图

stack<double> vals;
stack<char>   ops;

int prec(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    if (op == '^')              return 3;
    return 0;
}

void apply() {
    double b = vals.top(); vals.pop();
    double a = vals.top(); vals.pop();
    char op = ops.top(); ops.pop();
    switch (op) {
        case '+': vals.push(a + b); break;
        case '-': vals.push(a - b); break;
        case '*': vals.push(a * b); break;
        case '/': vals.push(a / b); break;
        case '^': vals.push(pow(a, b)); break;
    }
}

double evaluate(const string& s) {
    while (!vals.empty()) vals.pop();
    while (!ops.empty())  ops.pop();
    for (int i = 0; i < (int)s.size(); ) {
        if (isspace(s[i])) { ++i; continue; }
        if (s[i] == '(') { ops.push('('); ++i; continue; }
        if (s[i] == ')') {
            while (ops.top() != '(') apply();
            ops.pop(); ++i; continue;
        }
        if (isdigit(s[i]) || s[i] == '.') {          // 读一个完整数字
            double v; istringstream iss(s.substr(i));
            iss >> v; i += iss.tellg();
            vals.push(v);
            continue;
        }
        // 运算符
        char op = s[i++];
        while (!ops.empty() && prec(ops.top()) >= prec(op)) apply();
        ops.push(op);
    }
    while (!ops.empty()) apply();
    return vals.top();
}

3.汉诺塔 (Tower of Hanoi)

如果深入学习过递归或者你们大学中初学C或C++的期末考试压轴题一般就是汉诺塔递归或者链表手搓，对于没有了解过汉诺塔的人，相比或多或少的在视频或者现实生活中玩过或者见过这个玩具，（如下图）

这个过程用递归会比较好理解，左边的是资源柱，中间的是辅助柱，右边的目标柱，一个环只能在更大的环上面，我们要把最下面的红色环放到最右边，需要把它上面的所有环给放到中间的辅助柱上然后移动，对于每一个环都是这样的流程，除了最上面的小环可以直接移到目标柱，这也就是为什么和栈，和递归的匹配度更高，（即拆解成了最小子问题和最优子结构）

struct Frame {
    int n;
    char from, aux, to;
    bool done;   // false 表示还没处理第一步
};

void hanoi_iter(int n) {
    stack<Frame> st;
    st.push({n, 'A', 'B', 'C', false});
    while (!st.empty()) {
        Frame f = st.top(); st.pop();
        if (f.n == 0) continue;
        if (!f.done) {
            // 把三步倒序压回去
            st.push({f.n - 1, f.aux, f.from, f.to, false});
            st.push({f.n, f.from, f.aux, f.to, true});   // 标记已处理
            st.push({f.n - 1, f.from, f.to, f.aux, false});
        } else {
            cout << "Move disk " << f.n << " from " << f.from << " to " << f.to << '\n';
        }
    }
}

（这样处理其实很麻烦，事实上直接用递归就好了）

void hanoi(int n, char from, char aux, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, aux);
    cout << "Move disk " << n << " from " << from << " to " << to << '\n';
    hanoi(n - 1, aux, from, to);
}

队列（queue）

队列 queue 的基本操作

enqueue()	入队：将一个元素 item 添加到队列的末尾（队尾）。
dequeue()	出队：移除队列开头（队首）的元素。注意：此操作通常不返回被移除的元素。
front()	获取队首元素：返回队列开头元素的值，但不移除它。
empty()	判空：检查队列是否为空。如果为空，返回 true。
size()	获取大小：返回队列中元素的数量。

queue算法

 1.广度优先搜索 (Breadth-First Search, BFS)

这个不过多赘述，直接去看我第一篇学树的博客即可。

2.模拟 (Simulation)

我们的模拟指的是根据题目描述结合一些数据结构与算法来模拟题目描述情况的一种题目类型，最简单的就是用printf、cout、for、while、去画一些图案，但是复杂一点的可能需要复杂的数据结构支持，比如模拟曼哈顿距离，银行排队之类的。因为题目不固定所以给出“不完美约瑟夫问题”

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    queue<int> q;
    for (int i = 1; i <= n; ++i) q.push(i);      //  所有人入队
    while (q.size() > 1) {
        for (int i = 1; i < k; ++i) {            //  把前 k-1 个放回队尾
            q.push(q.front());
            q.pop();
        }
        q.pop();                                 //  第 k 个人出局
    }
    cout << q.front();                           // 最后幸存者
}

Ciallo～ (∠・ω< )⌒★

当然栈有双栈共享成一个栈，队列也有循环队列，但是anyway，应用比较少，想学的话可以自己了解，今天就学这么多吧。

bye bye