AI_第一部分 数据结构与算法（7.栈）

第四阶段我们进行深度学习(AI)，本部分（第一部分）主要是对底层的数据结构与算法部分进行详尽的讲解，通过本部分的学习主要达到以下两方面的效果：

1.对开发中常见的算法能应用自如，让你在跳槽找工作中“算法题”不再是阻碍你“钱途”的拦路虎。

2.我们不需要调参数的调参攻城狮，我们要做正真的自己的AI模型。

3.本部分预计40篇左右。

今天我们聊聊栈这种数据结构。一提到栈你想到的是什么呢？先进后出？还是？我们今天从一下几方面来聊聊栈这种数据结构

第一、如何理解栈？

我们先举一个简单的生活中的例子：每次你收拾吃饭饭的盘子的时候，都是从下往上一个个的放，然后洗盘子的时候从上面依次去下清洗。没有人会说不我就直接清洗最后一个盘子，生活经验告诉我们这样做是不可取的，所谓的空中花园也是别人家的。这种后进先出的这种操作行为就是为栈这种数据结构量身定做。

从栈的特性上讲，栈是一种“操作受限的”线性表，只允许在一端插入和删除数据，如果还不是很清楚什么是线性表的可以参看前面的文章，这里就不做过多的解释了。

我们通过图来再感性的认识一下这个数据结构：

第二、如何创建一个栈，来实现栈的基本的操作功能呢？

我们使用的开发工具呢是python，so，今天我们就使用python来实现一个栈的所有功能，对外提供服务。

    class Stack(object):
        def __init__(self, size)
            self.size = size
            self.items = [None] * int(self.size)    # 初始化栈空间大小
        def is_empty(self)
            if len(self.items) == 0:
                return True
            else:
                return False
        def is_full(self)
            if len(self.items) == int(self.size):
                return True
            else:
                return False
        def push(self, data)
            if self.is_full():
                return False
            else:
                self.items.append(data)
                return True
        def pop(self)
            if self.is_empty():
                 return False
            else:
                self.items.pop()
               return True
a = Stack(10)  # 实例化一个有10个单元的栈空间
if a.push(3):
    print('入栈元素：[%s] 成功'， 3)
else：
    print('入栈元素：[%s]失败'， 3)

以上就是使用python实现的一个简单的具有固定容量的栈，当然有兴趣的小伙伴可以在此基础上扩展，支持动态扩容的操作哦。这个也是我当时去面试的一道笔试题目，请大家认真体会。

第三、栈在实际开发中的一些举例：

3.1.函数调用栈

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种数据结构，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为栈帧入栈，当被调用函数执行完成，返回退出后，将这个函数对应的栈帧出栈。

3.2.在表达式求值中的应用

求解：23+2*1 + 4 - 2/1 对于我们来说很容易，不过计算机不认识啊，它只是认识0和1，如何让计算机也能像人一样计算这些数据呢？其实，编译器就是通过两个栈来实现的，其中一个保留操作数的栈，一个保存运算符的栈，从左到右依次遍历表达式，当遇到数字，就入操作数栈，当遇到运算符就与运算符栈顶的元素比较如果运算符栈顶元素的运算优先级高，就当前运算符入栈，若相同或者低则从运算符栈中取出栈顶运算符，从操作数栈的栈顶中取出两个操作数，然后进行计算，再把计算完成的结果压入操作数栈，继续比较，直到操作数栈中剩一个数为止。

好了，本期关于栈的分享到此结束，下次开始我们分享队列有关的内容，你有任何问题，请留言或者后台与我取得联系，在时间允许的情况下回及时回复你的问题，谢谢理解。

如果你觉得公众号的内容不错，可以推荐于身边的朋友，你的每次肯定和受益都会成为我前进的动力，一起加油！

注意：1.欢迎大家把自己的答案在最下面进行留言，或者后台留言。

2.此系列练习我会给出c语言的代码，以及pyhton代码。