栈学不会咋办嘛

写篇博客之前我已经鸽了好久，因为只几天一直在折腾github和一些插件，正规的学习也鸽了好久，今天又温习了一下链表感觉也有好多坑要填，暂时就先不填了，感觉需要填好多，所以暂时就先鸽了吧。这次写博客我老老实实的加上了date标签，因为昨天晚上用github action自动部署的时候之前的更新记录全给我推平了，所以这篇博客以前的更新时间全是昨天晚上。还有想要吐槽的地方是用ssh验证的时候一直都部署失败，折腾了几个小时耐心到达极点的情况下果断选择了token。token大法好。还有之前为了破解腾讯的防盗链也花了不少时间。这真是一个非常折磨人的过程。腾讯抠到连蹭个外链都不行了吗。

什么是栈

栈是一种线性数据结构,存储以及查找数据时只能访问栈的一端。形象点来说栈类似于自助餐厅中的一叠盘子，新盘子呢在最上面，去的时候也是从上面取。最后放上去的盘子是最先被取走的盘子，因此栈被称为后进先出(LIFO,last in/first out)结构。栈必须有一个盘子的时候才能取出盘子，只有空间还够的时候（比如说盘子我还能加，不要停下来啊），才能加上一个盘子。因此`可以改变栈的状态和检测栈的状态来操作定义栈，这些操作包括：

clean()-------清空栈
isEmpty()------判断栈是否为空
push(el)------将le元素放到栈的顶部
pop()-------弹出栈顶元素
topEI-------获取栈顶部元素，但不删除该元素

插入

删除

这些都是比较简单的实现，对于栈来说可操作的地方只有栈顶，当然栈的应用比较常见的一个就是程序中匹配分隔符，当然我们常用的浏览器的前进和后退也是用栈实现的。

关于括号匹配

很久之前写过一篇，容许我献上我拙劣的源代码

#include < bits/stdc++.h>
using namespace std;
string str;
int sum=0;
int main(int argc, char const *argv[])
{
    cin>>str;
    int len=str.size();
    stack <char> ss;
    char ch;
    for (int i = 0; i <len ; ++i)
    {

        ch=str[i];
        if (ch=='(')

        {
            sum++;
            ss.push(ch);
        }else{
            if (ch==')')
            {
                if (ss.empty())
                {
                    cout<<"NO";
                    return 0;
                }
                ss.pop();
            }
        }
    }
    if (ss.empty()&&sum!=0)
    {
        cout<<"YES";
    }else cout<<"NO";
    return 0;
}

总体来看实现还是非常简单的

那么现在我们来看看具体的实现是什么样子的

栈既可以用数组实现，也可以用链表来实现。用数组实现的栈，叫作顺序栈，用链表实现的栈，叫作链栈。这里我们用py实现一下，ps:py半吊子出家的某人

示例：顺序栈

class Stack():
  
    def __init__(self,size):
        """初始化"""
        self.size = size
        self.num = 0
        self.stack = []
  
    def getSize(self):
        """获取栈的长度"""
        return self.num
  
    def print_all(self):
        """输出栈元素"""
        for s in self.stack:
            print s
    
    def append_stack(self,value):
        """入栈"""
        if self.num >= self.size:
            print("the stack is full")
            return
        else:
            self.stack.append(value)
            self.num += 1
   
    def pop_stack(self):
        """ 出栈"""
        if self.num is None:
            print("the stack is empty")
            return
        else:
            self.stack.remove(self.stack[-1])

复杂度分析

空间复杂度

无论是顺序栈还是链栈，存储数据只需要一个大小为n的数组。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度为O(1)。

注：存储数据需要一个大小为n的数组，并不是指空间复杂度就为O(n)。因为，这 n 个空间是必须的，无法省掉。
我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要的额外的存储空间。

时间复杂度

不管顺序栈还是链栈，入栈、出栈只涉及栈顶个别数据的操作，所以复杂度为O(1)。

支持动态扩容的顺序栈的入栈、出栈时间复杂度分析

对于出栈操作来说，不会涉及内存的重新申请和数据的搬移，所以出栈的时间复杂度仍然是 O(1)。但是，对于入栈操作来说，情况就不一样了。当栈中有空闲空间时，入栈操作的时间复杂度为 O(1)。但当空间不够时，就需要重新申请内存和数据搬移，所以时间复杂度就变成了 O(n)。

也就是说，对于入栈操作来说，最好情况时间复杂度是 O(1)，最坏情况时间复杂度是 O(n)。而平均时间复杂度，由摊还分析法分析可知为 O(1)。

啊突然想起来栈还有一个应用

如果两个数非常非常大，甚至超过了long long，或者是超级超级大的数【雾】。我们可以用高精度算法或者你熟悉java的BigInteger。那么问题来了，高精度好难，java完全不熟悉咋办。没毛病老铁，高精度俺也不会写。不熟悉java？咱还有解！！！！如果说整型变量完全放不下。我们可以用栈来解决

把非常大的变量看成一串数字
分别放到两个栈中
然后重栈中弹出数，进行加法操作
解决

给出伪代码

addingLargeNumber（）
读第一个数字，并将这个数对应的数存放到一个栈中
读第二个数字，并将这个数对应的数存放到另一个栈中
Carry=0;
while(至少一个栈不为空)
    从每个非空的栈中弹出一个数，并将这个数字与Carry相加
    讲个位数的结果放入栈中;
    将进位放进Carry中;
如果进位不为0；将其放入结果栈中;
从结果栈中弹出结果并显示;