数据结构(二)栈

xeonds

2021.09.24 01:09:41

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. 后缀表达式计算

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

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

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

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

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