栈

栈模型

栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端叫做栈的顶（top），对栈的基本操作有 push(进栈)和 pop(出栈),前者相当于插入，后者则是删除最后插入的元素。

栈的另一个名字是 LIFO（先进后出）表。

普通的清空栈的操作和判断是否空栈的测试都是栈的操作指令系统的一部分，我们对栈能做的基本上也就是 push 和 pop 操作。

注：该图描述的模型只象征着 push 是输入操作，pop 是输出操作

下图表示进行若干操作后的一个抽象的栈。一般的模型是，存在某个元素位于栈顶，而该元素是唯一可见元素。

栈的实现

因为栈是一个表，因此能够实现表的方法都可以实现栈，例如 vector

刷题时我们可以直接使用 std::stack

#include <stack>
#include <iostream>
#include <string>

int main() {
    
    // 创建不同类型的栈
    std::stack<int> int_stack;
    std::stack<std::string> string_stack;
    std::stack<double> double_stack;
    
    int_stack.push(10);
    int_stack.push(20);
    int_stack.push(30);
    int_stack.push(40);
    int_stack.push(50);
    
    std::cout << "栈的大小: " << int_stack.size() << std::endl;
    std::cout << "栈顶元素: " << int_stack.top() << std::endl;
    
    while (!int_stack.empty()) {
        std::cout << "弹出: " << int_stack.top() << std::endl;
        int_stack.pop();
    }
    
    string_stack.push("苹果");
    string_stack.push("香蕉");
    string_stack.push("橙子");
    string_stack.push("葡萄");
    
    std::cout << "栈的大小: " << string_stack.size() << std::endl;
    std::cout << "栈顶元素: " << string_stack.top() << std::endl;
    
    while (!string_stack.empty()) {
        std::cout << "弹出: " << string_stack.top() << std::endl;
        string_stack.pop();
    }
    
    double_stack.push(3.14);
    double_stack.push(2.718);
    double_stack.push(1.414);
    
    std::cout << "栈的大小: " << double_stack.size() << std::endl;
    
    // 演示栈的其他操作
    std::stack<int> demo_stack;
    
    std::cout << "栈是否为空: " << (demo_stack.empty() ? "是" : "否") << std::endl;
    
    demo_stack.push(100);
    demo_stack.push(200);
    demo_stack.push(300);
    
    std::cout << "压入3个元素后，栈的大小: " << demo_stack.size() << std::endl;
    std::cout << "栈顶元素: " << demo_stack.top() << std::endl;
    
    demo_stack.pop();
    std::cout << "弹出1个元素后，栈的大小: " << demo_stack.size() << std::endl;
    std::cout << "新的栈顶元素: " << demo_stack.top() << std::endl;

    return 0;
}

栈的应用

栈在现实中应用场景很多，大家在刷题时就可以注意到，很多题目都可以用栈来解决的。下面我们来说一个比较常用的情景，数字表达式的求值。

不知道大家是否还记得那句口令，先乘除，后加减，从左算到右，有括号的话就先算括号里面的。

这是我们做小学数学所用到的。四则运算中括号也是其中的一部分，先乘除后加减使运算变的复杂，加上括号后甚之，那么我们有什么办法可以让其变的更好处理呢？

波兰数学家Jan Łukasiewicz想到了一种不需要括号的后缀表达式，我们也将它称之为逆波兰表示。

不用数学家名字命名的原因有些尴尬，居然是因为他的名字太复杂了，所以用了国籍来表示而不是姓名。所以各位小伙伴以后给孩子起名字的时候不要太复杂啊。

扬·武卡谢维奇（波兰语：Jan Łukasiewicz，1878 年 12 月 21 日**乌克兰利沃夫 - 1956 年 2 月 13 日爱尔兰都柏林），波兰数学家，主要致力于数理逻辑**的研究。著名的波兰表示法逆波兰表示法就是他的研究成果。

中缀表达式转为后缀表达式

我们通过一个例子，来说明如何将中缀表达式转为后缀表达式。

例

中缀:9 + ( 3 - 1 ) * 3 + 10 / 2

后缀:9 3 1 - 3 * + 10 2 / +

规则

1.从左到右遍历中缀表达式的每个数字和符号，若是数字就输出（直接成为后缀表达式的一部分，不进入栈）

2.若是符合则判断其与栈顶符号的优先级，是右括号或低于栈顶元素，则栈顶元素依次出栈并输出，等出栈完毕，当前元素入栈。

3.遵循以上两条直到输出后缀表达式为止。

老样子大家直接看动图吧简单粗暴，清晰易懂

后缀表达式计算结果

中缀:9 + ( 3 - 1 ) * 3 + 10 / 2=20

后缀:9 3 1 - 3 * + 10 2 / +

后缀表达式的值也为 20，那么我们来了解一下计算机是如何将后缀表达式计算为 20 的。

规则：

1.从左到右遍历表达式的每个数字和符号，如果是数字就进栈

2.如果是符号就将栈顶的两个数字出栈，进行运算，并将结果入栈，一直到获得最终结果。

下面大家 继续看动图吧。

注：为了用动图把逻辑整的清晰明了，十几秒的动图，就要整半个多小时，改进好几遍。如果觉得图片对你有帮助的话就点个赞和在看吧。