数据结构（二）栈

0x01.简介

栈（stack）是一种数据结构。它遵循的原则是FILO（First In Last Out），也就是先进后出。类比现实的例子，就是子弹上膛，最先压进去弹夹的子弹一般是最后一个被打出去的。

0x02.性质

反转队列

将一个队列的元素压入栈，再依次出栈，就能得到原队列的逆序队列。所以栈可以用于产生逆序队列。

出栈顺序

一个有n个元素的队列，按照一定顺序出入栈，得到另一个顺序的列表。试问顺序是否可以取到全排列$A_n^n$呢？

显然不能。

要得到一个新队列，那必然要进行$2n$次操作，即$n$次入栈和$n$次出栈。而这些操作共有$C_{2n}^n=\frac{(2n)!}{n!^2}$种组合，因而生成的新队列并没有$n!$那么多。

那么，判断队列是否可由栈生成自然也是重点。最简单的办法就是在草稿纸上模拟一个栈，从生成的新队列的第一个元素开始，反推出入栈操作即可。

将入栈和出栈记作I和O。我们来分析一个例子，比如1 3 5 4 2，遇到1我们就可以推得操作是IO，3的话，因为前面有2，所以得先入2才能入3，所以是IIO。此时栈中有元素2。接下来的5和3同理，操作是IIO，到此为止我们完成了5次I，3次O，栈中还有4 2，所以我们需要OO，得到最终的队列：1 3 5 4 2。

如何用程序实现这种判断呢？可以先生成一个大小为$n!$的map<队列，bool>，随后根据上面的数学过程穷举结果，并将结果对应的index标记为true然后用查表法得到结果。

当然，如果懒得写生成器，也可以用图灵机完成判断。

def fun(data):
    I,cnt=0,len(data)
    a,b=[i+1 for i in range(cnt)],[]
    
    for i in data:
        while TRUE:
            if I==cnt: break
            b.push(tmp=a.pop_front)
            I+=1
            if tmp==i: break
        if b.pop!=i: return FALSE
    return TRUE

这程序模拟了我们上面的手动判断步骤，通过一个队列和一个栈实现。

0x03.实现

用C语言实现。在C++中已经有STL中的stack，无需重复实现。

/* 数据结构定义 */
struct node{
    elemtype data;
    struct node * next;
}Node;

typedef struct stack{
    Node * top;
    int size;
}Stack;

/* 操作定义 */
bool init(Stack * ptr);
bool push(Stack * ptr, elemtype data);
bool pop(Stack * ptr, elemtype * data);
bool isEmpty(Stack * ptr);

0x04.应用

作为一种数据结构，由于栈LIFO的特性，它有很重要的应用。

比如利用短除法进行进制转换的时候，得到的数是从高位开始的，这种时候就适合用栈存储每一步的结果，最后直接出栈，就能得到正序的结果。

再比如括号匹配的检验。左括号一定是要和右括号匹配的，而栈中任一时刻，I操作次数一定是大于等于O操作次数，且最新的I对应最新的O。因此，利用栈，我们就能很容易检验匹配：遇到左括号就入栈，遇到右括号就出栈，如果不匹配返回false，最终返回true即可。

在二叉树的遍历中，我们也用栈进行状态记录。在图的深度优先搜索中，同样用栈记录状态。

栈不仅在数据结构上有很多应用，而且在语言和系统层面也有重要应用。

比如子程序的实现：jmp进入子程序地址之前，应该先把下一条指令的地址push到地址堆栈中，在完成子程序后再push返回主程序。高级语言中的函数调用大抵也是如此。

再比如递归程序的实现。和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。

这里特别说一下栈在表达式求值的应用。

表达式计算与栈

栈可以把中缀表达式转换成后缀表达式，而且利用栈可以很容易地计算后缀表达式的值。

1. 后缀表达式计算

过程很简单，只需要线性时间。对后缀表达式从左往右处理：遇到数字就压栈，遇到运算符就弹出两个数，把结果压栈，直到处理完成只剩一个数，即表达式的运算结果。

2. 中缀表达式转后缀表达式

这需要一个栈，它用于存储操作符。遇到操作数直接输出，遇到符号就入栈。遇到右括号则出栈，直到遇到左括号为止，停止出栈。注意，括号不输出，只弹栈。

在以上条件下，遇到其他符号则弹出栈元素直到发现优先级更低的元素为止。例如，乘除优先级大于加减。

最后，输入结束后，弹栈直到空栈为止。